共计 3564 个字符，预计需要花费 9 分钟才能阅读完成。
1. 概述
前面说到了数组，利用连续的内存空间来存储相同类型的数据，其最大的特点是支持下标随机访问，但是删除和插入的效率很低。今天来看另一种很基础的数据结构——链表。链表不需要使用连续的内存空间，它使用指针将不连续的内存块连接起来，形成一种链式结构。
2. 单链表
首先来看看单链表，存储数据的内存块叫做节点，每个节点保存了一个 next 指针，指向下一个节点的内存地址，结合下图你就很容易看明白了：其中有两个节点指针比较的特殊，首先是链表头节点的指针，它指向了链表的第一个节点的地址，利用它我们可以遍历得到整个链表。其次是尾结点的指针，它指向了 null，表示链表结束。
不难看出，单链表的最大特点便是使用指针来连接不连续的节点，这样我们不用担心扩容的问题了，并且，链表的插入和删除操作也非常的高效，只需要改变指针的指向即可。结合上图不难理解，单链表能够在 O(1) 复杂度内删除和添加元素，这就比数组高效很多。但是，如果我们要查找链表数据怎么办呢？链表的内存不是连续的，不能像数组那样根据下标访问，所以只能通过遍历链表来查找，时间复杂度为 O(n)。下面是单链表的代码示例：
public class SingleLinkedList {
private Node head = null;// 链表的头节点
// 根据值查找节点
public Node findByValue(int value) {
Node p = head;
while (p != null && p.getData() != value)
p = p.next;
return p;
}
// 根据下标查找节点
public Node findByIndex(int index) {
Node p = head;
int flag = 0;
while (p != null){
if (flag == index)
return p;
flag ++;
p = p.next;
}
return null;
}
// 插入节点到链表头部
public void insertToHead(Node node){
if (head == null) head = node;
else {
node.next = head;
head = node;
}
}
public void insertToHead(int value){
this.insertToHead(new Node(value));
}
// 插入节点到链表末尾
public void insert(Node node){
if (head == null){
head = node;
return;
}
Node p = head;
while (p.next != null) p = p.next;
p.next = node;
}
public void insert(int value){
this.insert(new Node(value));
}
// 在某个节点之后插入节点
public void insertAfter(Node p, Node newNode){
if (p == null) return;
newNode.next = p.next;
p.next = newNode;
}
public void insertAfter(Node p, int value){
this.insertAfter(p, new Node(value));
}
// 在某个节点之前插入节点
public void insertBefore(Node p, Node newNode){
if (p == null) return;
if (p == head){
insertToHead(newNode);
return;
}
// 寻找节点 p 前面的节点
Node pBefore = head;
while (pBefore != null && pBefore.next != p){
pBefore = pBefore.next;
}
if (pBefore == null) return;
newNode.next = pBefore.next;
pBefore.next = newNode;
}
public void insertBefore(Node p, int value){
insertBefore(p, new Node(value));
}
// 删除节点
public void deleteByNode(Node p){
if (p == null || head == null) return;
if (p == head){
head = head.next;
return;
}
Node pBefore = head;
while (pBefore != null && pBefore.next != p){
pBefore = pBefore.next;
}
if (pBefore == null) return;
pBefore.next = pBefore.next.next;
}
// 根据值删除节点
public void deleteByValue(int value){
Node node = this.findByValue(value);
if (node == null) return;
this.deleteByNode(node);
}
// 打印链表的所有节点值
public void print(){
Node p = head;
while (p != null){
System.out.print(p.getData() + ” “);
p = p.next;
}
System.out.println();
}
// 定义链表节点
public static class Node{
private int data;
private Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
public int getData() {
return data;
}
}
}
3. 循环链表
循环链表和单链表的唯一区别便是链表的尾结点指针并不是指向 null，而是指向了头节点，这样便形成了一个环形的链表结构：
4. 双向链表
双向链表，顾名思义，就是链表不只是存储了指向下一个节点的 next 指针，还存储了一个指向前一个节点的 prev 指针，如下图：为什么要使用这种具有两个指针的链表呢？主要是为了解决链表删除和插入操作的效率问题。
在单链表中，要删除一个节点，必须找到其前面的节点，这样就要遍历链表，时间开销较高。但是在双向链表中，由于每个节点都保存了指向前一个节点的指针，这样我们能够在 O(1) 的时间复杂度内删除节点。
插入操作也类似，比如要在节点 p 之前插入一个节点，那么也必须遍历单链表找到 p 节点前面的那个节点。但是双向链表可以直接利用前驱指针 prev 找到前一个节点，非常的高效。
这也是双向链表在实际开发中用的更多的原因，虽然每个节点存储了两个指针，空间开销更大，这就是一种典型的用空间换时间的思想。
下面是双向链表的代码示例：
public class DoubleLinkedList {
private Node head = null;// 链表的头节点
// 在某个节点之前插入节点，这里方能体现出双向链表的优势
public void insertBefore(Node p, Node newNode) {
if (p == null) return;
if(p == head) {
this.insertToHead(newNode);
return;
}
newNode.prev = p.prev;
p.prev.next = newNode;
newNode.next = p;
p.prev = newNode;
}
public void insertBefore(Node p, int value) {
this.insertBefore(p, new Node(value));
}
// 删除某个节点
public void deleteByNode(Node node) {
if(node == null || head == null) return;
if (node == head) {
head = head.next;
if(head != null) head.prev = null;
return;
}
Node prev = node.prev;
Node next = node.next;
prev.next = next;
if(next != null) next.prev = prev;
}
// 根据值删除节点
public void deleteByValue(int value) {
Node node = this.findByValue(value);
if (node == null) return;
this.deleteByNode(node);
}
// 定义链表节点
public static class Node{
private int data;
private Node prev;// 链表的前驱指针
private Node next;// 链表的后继指针
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
public int getData() {
return data;
}
}
}
