数据结构期末复习 第二章线性表知识点加代码

第二章线性表通常涉及计算机科学的基础数据结构，它是数据结构中最基本的一种，包括数组、链表等。下面是几个重要的线性表知识点：

1. **数组（Array）**：
- 定义：固定大小的一组有序元素集合，通过索引来访问。
- 知识点：动态数组（如ArrayList），静态数组（如一维字符数组char[]），插入和删除操作的效率（一般情况下，插入/删除在数组头部快，尾部慢）。

List<Integer> array = new ArrayList<>();
array.add(1); // 插入元素
array.remove(0); // 删除第一个元素

2. **单链表（Linked List）**：
- 定义：由节点组成，每个节点包含数据和指向下一个节点的指针。
- 知识点：顺序查找速度快，插入和删除操作可以在常数时间内完成（对于头节点）；但是访问任意位置需要从头开始遍历。

ListNode linkedList = new ListNode(1);
linkedList.next = new ListNode(2); // 插入节点

LinkedListNode current = linkedList;
while (current.next != null) {
    current = current.next; // 遍历列表
}
current.next = new ListNode(3); // 在特定位置插入

3. **双向链表（Double Linked List）**：
- 每个节点有两个指针，分别指向前一个和后一个节点。
- 插入和删除操作比单链表更方便，因为可以双向移动。

4. **栈（Stack）和队列（Queue）**：
- 栈是一种特殊类型的线性表，只允许在一端进行插入和删除（后进先出LIFO）。
- 队列则是另一端进行插入（先进先出FIFO）。

Stack<Integer> stack = new Stack<>();
stack.push(1); // 入栈
int topElement = stack.pop(); // 出栈

Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // 入队
int frontElement = queue.poll(); // 出队