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;
