Java 双链表
- LinkedList内部使用双向链表实现，支持高效的插入和删除（特别是在两端）。
- 由于实现了Deque接口，因此可以作为双端队列使用。
- 随机访问性能较差，需要通过遍历实现。
1. 单链表
单链表（Singly Linked List）是一种基础但重要的线性数据结构（A->B->C）。
1.1 定义单链表节点类
最好定义为静态私有内部类。
// 单链表节点类
class ListNode<E> {E data; // 存储的数据ListNode<E> next; // 指向下一个节点的指针ListNode(E data) {this.data = data;this.next = null;}
}
1.2 定义单链表实现类
需要定义一个 head 指针。
// 单链表实现
public class SinglyLinkedList<E> {private ListNode<E> head; // 链表头节点private int size; // 链表大小public SinglyLinkedList() {head = null;size = 0;}
}
1.3 头部添加
/*** 假如原来是 B->C，head 指向 B* 现在向头部插入 A，变成 A->B->C，A 成为新的 head，A.next 需要指向 B，head 指向 A*/
public void addFirst(E data) {ListNode<E> newNode = new ListNode<>(data);newNode.next = head;head = newNode;size ++;
}
1.4 尾部添加
/*** 刚创建 SinglyLinkedList 的时候，head 是 null* 如果 head 是 null，新插入的节点成为新的 head，head 指向新节点* 否则，假设已有 A->B，现插入 C，那么 head 指向 A，需要从 head 开始遍历直到最后一个节点 B，将最后一个节点 B 的 next 指向新节点 C*/
public void addLast(E data) {ListNode<E> newNode = new ListNode<>(data);if(null == head) {head = newNode;} else {ListNode<E> current = head;while(null != current.next) {current = current.next;}current.next = newNode;}size ++;
}
1.5 头部移除
/*** 假设 SinglyLinkedList 是空的，那么 head 必然为 null，抛出一个 NoSuchElementException* 否则，假设已有 A->B->C，现在 head 指向 A，需要将 head 指向 B，并返回 A 值*/
public E removeFirst() {if(null == head) {throw new NoSuchElementException("空链表");}E data = head.data;head = head.next;size --;return data;
}
1.6 尾部移除
/*** 假设 SinglyLinkedList 是空的，那么 head 必然为 null，抛出一个 NoSuchElementException* 否则，假设已有 A->B->C，现在 head 指向 A，定义两个指针 pre、 cur，需要从 head 开始遍历直到倒数第一个节点 C，将倒数第二个节点 B.next 设为 null*/
public E removeLast() {if(null == head) {throw new NoSuchElementException("空链表");}ListNode<E> pre = null;ListNode<E> cur = head;while(null != cur.next) {pre = cur;cur = cur.next;}E data = cur.data;if(cur == head) { // 链表只有一个节点head = null;} else {pre.next = null;}size --;return data;
}
1.7 获取大小
public int size() {return size;
}
2. 双链表
双向链表（Doubly Linked List）是一种常见的线性数据结构（A<=>B<=>C），其中每个节点包含两个指针，分别指向前一个节点和后一个节点。
与单向链表相比，双向链表可以从任意一个节点访问前一个节点和后一个节点，但需要额外的空间来存储前驱指针。
2.1 定义双链表节点类
最好定义为静态私有内部类。
// 双链表节点类
class Node<E> {E data; // 存储的数据Node<E> next; // 后继节点Node<E> prev; // 前驱节点Node(E data) {this.data = data;this.prev = null;this.next = null;}Node(E data, Node<E> prev, Node<E> next) {this.data = data;this.prev = prev;this.next = next;}
}
2.2 定义双链表实现类
需要定义一个 head 指针，一个 tail 指针。
public class DoublyLinkedList<E> {private Node<E> head; // 头节点private Node<E> tail; // 尾节点private int size; // 链表长度public DoublyLinkedList() {this.head = null;this.tail = null;this.size = 0;}
}
2.3 获取大小
public int size() {return size;
}
2.4 判断为空
public boolean isEmpty() {return size == 0;
}
2.5 头部添加
/*** 假如原来是 B <=> C ，则 head 指向 B* 现在向头部插入 A，则 A.next 指向 B，B.prev 指向 A，最后 A 成为新的头部 head，A <=> B <=> C** 假如链表是空的，则 head 为 null，tail 为 null* 现在向头部插入 A，则 A 既是头部 head，也是尾部 tail*/
public void addFirst(E data) {Node<E> node = new Node<>(data);if(isEmpty()) {head = node;tail = node;} else {node.next = head;head.prev = node;head = node;}size ++;
}
2.6 尾部添加
/*** 假如原来是 A <=> B ，则 tail 指向 B* 现在向尾部插入 C，则 C.prev 指向 B，B.next 指向 C，最后 C 成为新的尾部 tail，A <=> B <=> C** 假如链表是空的，则 head 为 null，tail 为 null* 现在向头部插入 C，则 C 既是头部 head，也是尾部 tail*/
public void addLast(E data) {Node<E> node = new Node<>(data);if(isEmpty()) {head = node;tail = node;} else {tail.next = node;node.prev = tail;tail = node;}size ++;
}
2.7 获取指定位置节点
优化点：二分为向前遍历和向后遍历。
private Node getNode(int index) {if(index < 0 || index > size) {throw new IndexOutOfBoundsException("Invalid index: " + index);}Node<E> current;if(index < size / 2) {// 向后遍历current = head;for (int i = 0; i < index; i++) {current = current.next;}} else {// 向前遍历current = tail;for (int i = size - 1; i > index; i--) {current = current.prev;}}return current;
}
2.8 指定位置添加
public void add(int index, E data) {if(index < 0 || index > size) {throw new IndexOutOfBoundsException("Invalid index: " + index);}if(index == 0) {addFirst(data);} else if(index == size) {addLast(data);} else {Node<E> current = getNode(index);Node<E> node = new Node<>(data, current.prev, current);current.prev.next = node;current.prev = node;size ++;}
}
2.9 头部移除
public E removeFirst() {if(isEmpty()) {throw new NoSuchElementException("List is Empty.");}E data = head.data;if(head == tail) {head = tail = null;} else {head = head.next;head.prev = null;}size --;return data;
}
2.10 尾部移除
public E removeLast() {if(isEmpty()) {throw new NoSuchElementException("List is Empty.");}E data = tail.data;if(head == tail) {head = tail = null;} else {tail = tail.prev;tail.next = null;}size --;return data;
}
2.11 指定位置移除
public E remove(int index) {if(index < 0 || index >= size) {throw new IndexOutOfBoundsException("Invalid index: " + index);}E data;if(index == 0){data = this.removeFirst();} else if(index == size - 1) {data = this.removeLast();} else {Node<E> current = getNode(index);data = current.data;current.prev.next = current.next;current.next.prev = current.prev;current.prev = null;current.next = null;size --;}return data;
}
2.12 获取指定位置元素
public E get(int index) {Node<E> node = getNode(index);return node.data;
}
2.13 更新指定位置元素
public E set(int index, E data) {Node<E> node = getNode(index);E oldVal = node.data;node.data = data;return oldVal;
}
3. 栈
基于双链表实现。
4. 队列
基于双链表实现。
5. LinkedList
LinkedList 继承 AbstractSequentialList 类，实现了 List, Deque, Cloneable, Serializable 接口。其内部由双链表实现。
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, Serializable