线性结构深度解析 + Java Demo
线性结构是数据结构中最基础、应用最广泛的一类结构，核心特征是数据元素之间呈“一对一”的线性关系——除第一个（首元）和最后一个（尾元）元素外，每个元素有且仅有一个直接前驱和一个直接后继；首元无前驱，尾元无后继。根据存储方式，线性结构分为「顺序存储」（如数组）和「链式存储」（如链表）；根据操作限制，又可分为「普通线性结构」（数组、链表）和「受限线性结构」（栈、队列）。
目录
- 一、数组（顺序存储线性结构）
- 1. 核心定义
- 2. 核心特点
- 3. Java Demo：数组的基本操作
- 4. 输出结果
- 二、单链表（链式存储线性结构）
- 1. 核心定义
- 2. 核心特点
- 3. Java Demo：单链表的实现与操作
- 4. 输出结果
- 三、栈（受限线性结构：后进先出LIFO）
- 1. 核心定义
- 2. 核心特点
- 3. Java Demo：基于数组实现栈 + 内置LinkedList实现栈
- 4. 输出结果
- 四、队列（受限线性结构：先进先出FIFO）
- 1. 核心定义
- 2. 核心特点
- 3. Java Demo：循环队列实现 + 内置LinkedList实现队列
- 4. 输出结果
- 总结（核心要点回顾）
- 1. 线性结构核心特征
- 2. 各类线性结构选型指南
- 3. 工程实践建议
一、数组（顺序存储线性结构）
1. 核心定义
数组是将相同类型的元素存储在连续的内存空间中，通过「下标（索引）」直接访问元素的线性结构。Java中数组长度固定，一旦创建不可修改。
2. 核心特点
- 优点：随机访问效率极高（O(1)），内存连续，缓存友好；
- 缺点：插入/删除元素需移动后续元素（O(n)），长度固定，扩容需复制数组；
- 适用场景：频繁随机访问、元素数量固定/变化少的场景（如查找表、矩阵）。
3. Java Demo：数组的基本操作
import java.util.Arrays;
public class ArrayDemo {
public static void main(String[] args) {
// 1. 初始化数组（长度固定为5）
int[] arr = new int[5];
// 赋值：通过下标访问（O(1)）
arr[0] = 10;
arr[1] = 20;
arr[2] = 30;
arr[3] = 40;
arr[4] = 50;
System.out.println("初始化后数组：" + Arrays.toString(arr));
// 2. 随机访问（O(1)）
int target = arr[2];
System.out.println("访问下标2的元素：" + target); // 输出30
// 3. 插入元素（下标1处插入25，需移动后续元素，O(n)）
// Java数组长度固定，插入需创建新数组
int[] newArr = new int[arr.length + 1];
System.arraycopy(arr, 0, newArr, 0, 1); // 复制前1个元素
newArr[1] = 25; // 插入新元素
System.arraycopy(arr, 1, newArr, 2, arr.length - 1); // 复制剩余元素
arr = newArr;
System.out.println("插入后数组：" + Arrays.toString(arr)); // [10,25,20,30,40,50]
// 4. 删除元素（下标3处删除30，O(n)）
newArr = new int[arr.length - 1];
System.arraycopy(arr, 0, newArr, 0, 3);
System.arraycopy(arr, 4, newArr, 3, arr.length - 4);
arr = newArr;
System.out.println("删除后数组：" + Arrays.toString(arr)); // [10,25,20,40,50]
// 5. 遍历数组（O(n)）
System.out.print("遍历数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
4. 输出结果
初始化后数组：[10, 20, 30, 40, 50]
访问下标2的元素：30
插入后数组：[10, 25, 20, 30, 40, 50]
删除后数组：[10, 25, 20, 40, 50]
遍历数组：10 25 20 40 50
二、单链表（链式存储线性结构）
1. 核心定义
单链表由若干「节点」组成，每个节点包含「数据域」（存储元素）和「指针域」（指向后继节点），节点通过指针链接，内存无需连续。最后一个节点的指针域为null（尾节点）。
2. 核心特点
- 优点：长度动态，插入/删除仅需修改指针（找到节点后O(1)），无需连续内存；
- 缺点：随机访问慢（需从头遍历，O(n)），每个节点额外存储指针，内存开销略大；
- 适用场景：频繁插入/删除、元素数量动态变化的场景（如链表实现的栈/队列、LRU缓存）。
3. Java Demo：单链表的实现与操作
// 单链表节点类
class ListNode {
int val; // 数据域
ListNode next; // 指针域：指向后继节点
public ListNode(int val) {
this.val = val;
this.next = null;
}
}
public class SinglyLinkedListDemo {
private ListNode head; // 链表头节点
private int size; // 链表长度
// 初始化空链表
public SinglyLinkedListDemo() {
this.head = null;
this.size = 0;
}
// 1. 尾部添加元素（O(n)，可优化为带尾指针O(1)）
public void addLast(int val) {
ListNode newNode = new ListNode(val);
if (head == null) { // 空链表，头节点为新节点
head = newNode;
} else {
ListNode curr = head;
while (curr.next != null) { // 找到尾节点
curr = curr.next;
}
curr.next = newNode; // 尾节点指向新节点
}
size++;
}
// 2. 指定下标插入元素（O(n)，找到前驱节点后O(1)插入）
public void add(int index, int val) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("下标越界");
}
ListNode newNode = new ListNode(val);
if (index == 0) { // 插入到头节点
newNode.next = head;
head = newNode;
} else {
ListNode prev = head;
for (int i = 0; i < index - 1; i++) { // 找到前驱节点
prev = prev.next;
}
newNode.next = prev.next; // 新节点指向原后继
prev.next = newNode; // 前驱指向新节点
}
size++;
}
// 3. 删除指定下标的元素（O(n)）
public void remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("下标越界");
}
if (index == 0) { // 删除头节点
head = head.next;
} else {
ListNode prev = head;
for (int i = 0; i < index - 1; i++) { // 找到前驱节点
prev = prev.next;
}
prev.next = prev.next.next; // 前驱指向后继的后继，跳过待删除节点
}
size--;
}
// 4. 查找指定下标的元素（O(n)）
public int get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("下标越界");
}
ListNode curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr.val;
}
// 5. 遍历链表（O(n)）
public void traverse() {
ListNode curr = head;
System.out.print("链表遍历：");
while (curr != null) {
System.out.print(curr.val + " ");
curr = curr.next;
}
System.out.println();
}
public static void main(String[] args) {
SinglyLinkedListDemo list = new SinglyLinkedListDemo();
// 尾部添加
list.addLast(10);
list.addLast(20);
list.addLast(30);
list.traverse(); // 输出：链表遍历：10 20 30
// 指定下标插入
list.add(1, 15);
list.traverse(); // 输出：链表遍历：10 15 20 30
// 查找元素
int val = list.get(2);
System.out.println("下标2的元素：" + val); // 输出20
// 删除元素
list.remove(1);
list.traverse(); // 输出：链表遍历：10 20 30
System.out.println("链表长度：" + list.size); // 输出3
}
}
4. 输出结果
链表遍历：10 20 30
链表遍历：10 15 20 30
下标2的元素：20
链表遍历：10 20 30
链表长度：3
三、栈（受限线性结构：后进先出LIFO）
1. 核心定义
栈是仅允许在「栈顶」进行插入（push）和删除（pop）操作的受限线性结构，遵循「后进先出（LIFO）」原则。可基于数组或链表实现。
2. 核心特点
- 操作受限：仅栈顶可操作，无法访问中间元素；
- 核心操作：push（入栈）、pop（出栈，删除并返回栈顶）、peek（查看栈顶，不删除）；
- 优点：操作效率高（数组实现O(1)）；
- 适用场景：逆序处理、函数调用栈、表达式求值、括号匹配。
3. Java Demo：基于数组实现栈 + 内置LinkedList实现栈
// 基于数组实现栈
class ArrayStack {
private int[] stack; // 存储元素的数组
private int top; // 栈顶指针（指向栈顶元素的下一个位置）
private int capacity; // 栈容量
public ArrayStack(int capacity) {
this.capacity = capacity;
this.stack = new int[capacity];
this.top = 0; // 初始栈空，top=0
}
// 入栈（O(1)）
public void push(int val) {
if (top == capacity) {
throw new RuntimeException("栈满，无法入栈");
}
stack[top++] = val;
}
// 出栈（O(1)）
public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈空，无法出栈");
}
return stack[--top];
}
// 查看栈顶（O(1)）
public int peek() {
if (isEmpty()) {
throw new RuntimeException("栈空，无栈顶元素");
}
return stack[top - 1];
}
// 判断栈空
public boolean isEmpty() {
return top == 0;
}
// 获取栈大小
public int size() {
return top;
}
}
public class StackDemo {
public static void main(String[] args) {
// 1. 自定义数组栈
ArrayStack stack = new ArrayStack(5);
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("数组栈栈顶：" + stack.peek()); // 30
System.out.println("数组栈出栈：" + stack.pop()); // 30
System.out.println("数组栈大小：" + stack.size()); // 2
// 2. Java内置LinkedList实现栈（工程推荐）
java.util.Stack<Integer> builtInStack = new java.util.Stack<>();
builtInStack.push(100);
builtInStack.push(200);
builtInStack.push(300);
System.out.println("内置栈栈顶：" + builtInStack.peek()); // 300
System.out.println("内置栈出栈：" + builtInStack.pop()); // 300
System.out.println("内置栈是否为空：" + builtInStack.isEmpty()); // false
}
}
4. 输出结果
数组栈栈顶：30
数组栈出栈：30
数组栈大小：2
内置栈栈顶：300
内置栈出栈：300
内置栈是否为空：false
四、队列（受限线性结构：先进先出FIFO）
1. 核心定义
队列是仅允许在「队尾」插入（offer）、「队头」删除（poll）的受限线性结构，遵循「先进先出（FIFO）」原则。普通数组队列易出现「假溢出」，通常实现为「循环队列」优化。
2. 核心特点
- 操作受限：队尾入、队头出，无法访问中间元素；
- 核心操作：offer（入队）、poll（出队，删除并返回队头）、peek（查看队头）；
- 循环队列优点：复用数组空间，避免假溢出，操作效率O(1)；
- 适用场景：任务排队、消息队列、广度优先搜索（BFS）。
3. Java Demo：循环队列实现 + 内置LinkedList实现队列
// 基于数组的循环队列
class CircularQueue {
private int[] queue; // 存储元素的数组
private int front; // 队头指针（指向队头元素）
private int rear; // 队尾指针（指向队尾元素的下一个位置）
private int capacity; // 队列容量（实际可用=capacity-1，预留空位区分空/满）
private int size; // 队列当前大小
public CircularQueue(int capacity) {
this.capacity = capacity + 1; // 预留一个空位
this.queue = new int[this.capacity];
this.front = 0;
this.rear = 0;
this.size = 0;
}
// 入队（O(1)）
public boolean offer(int val) {
if (isFull()) {
return false; // 队列满，入队失败
}
queue[rear] = val;
rear = (rear + 1) % capacity; // 循环移动队尾指针
size++;
return true;
}
// 出队（O(1)）
public Integer poll() {
if (isEmpty()) {
return null; // 队列空，返回null
}
int val = queue[front];
front = (front + 1) % capacity; // 循环移动队头指针
size--;
return val;
}
// 查看队头（O(1)）
public Integer peek() {
if (isEmpty()) {
return null;
}
return queue[front];
}
// 判断队列满
public boolean isFull() {
return (rear + 1) % capacity == front;
}
// 判断队列空
public boolean isEmpty() {
return front == rear;
}
// 获取队列大小
public int size() {
return size;
}
}
public class QueueDemo {
public static void main(String[] args) {
// 1. 自定义循环队列
CircularQueue cq = new CircularQueue(5); // 实际可用容量5
cq.offer(10);
cq.offer(20);
cq.offer(30);
System.out.println("循环队列队头：" + cq.peek()); // 10
System.out.println("循环队列出队：" + cq.poll()); // 10
System.out.println("循环队列大小：" + cq.size()); // 2
cq.offer(40);
cq.offer(50);
cq.offer(60); // 容量5，入队成功
System.out.println("循环队列是否满：" + cq.isFull()); // true
// 2. Java内置LinkedList实现队列（工程推荐）
java.util.Queue<Integer> builtInQueue = new java.util.LinkedList<>();
builtInQueue.offer(100);
builtInQueue.offer(200);
builtInQueue.offer(300);
System.out.println("内置队列队头：" + builtInQueue.peek()); // 100
System.out.println("内置队列出队：" + builtInQueue.poll()); // 100
System.out.println("内置队列是否为空：" + builtInQueue.isEmpty()); // false
}
}
4. 输出结果
循环队列队头：10
循环队列出队：10
循环队列大小：2
循环队列是否满：true
内置队列队头：100
内置队列出队：100
内置队列是否为空：false
总结（核心要点回顾）
1. 线性结构核心特征
- 元素呈“一对一”线性关系，有序且前驱/后继唯一；
- 分为顺序存储（数组）和链式存储（链表），受限结构（栈、队列）基于两者实现。
2. 各类线性结构选型指南
| 结构 | 核心优点 | 核心缺点 | 典型适用场景 |
|---|---|---|---|
| 数组 | 随机访问O(1)，缓存友好 | 插入删除O(n)，长度固定 | 频繁查询、元素数量稳定（如查找表） |
| 单链表 | 插入删除O(1)，长度动态 | 随机访问O(n)，内存开销略大 | 频繁增删、元素数量动态（如LRU） |
| 栈 | 操作O(1)，后进先出 | 操作受限，无法访问中间元素 | 逆序处理、函数栈、括号匹配 |
| 队列 | 操作O(1)，先进先出 | 操作受限，无法访问中间元素 | 任务排队、消息队列、BFS |
3. 工程实践建议
- 优先使用Java内置集合（
ArrayList/LinkedList/Stack/Queue），避免重复造轮子； - 频繁随机访问选
ArrayList（数组实现），频繁增删选LinkedList（链表实现）； - 栈/队列优先用
LinkedList实现（避免数组扩容问题），高性能场景可自定义循环队列。
