什么是链表
链表是一种线性结构，也是最基础的动态数据结构。我们在实现动态数组、栈以及队列时，底层都是依托的静态数组，靠resize来解决固定容量的问题，而链表是真正的动态数据结构。学习链表这种数据结构，能够更深入的理解引用（或者指针）以及递归。其中链表分为单链链表和双链链表，本文中所介绍的是单链链表。
链表中的数据是存储在一个个的节点中，如下这是一个最基本的节点结构：
class Node { E e; Node next; // 节点中持有下一个节点的引用 } 我们可以将链表想象成火车，每一节车厢就是一个节点，乘客乘坐在火车的车厢中，就相当于元素存储在链表的节点中。火车的每一节车厢都连接着下一节车厢，就像链表中的节点都会持有下一个节点的引用。火车的最后一节车厢没有连接任何车厢，就像链表中末尾的节点指向null一样：
链表优缺点：
- 优点：真正的动态结构，不需要处理固定容量的问题，从中间插入、删除节点很方便，相较于数组要灵活
- 缺点：丧失了随机访问的能力，不能像数组那种直接通过索引访问
废话不多说，我们开始来编写链表这个数据结构吧，首先来实现链表中的节点结构以及链表的一些简单方法，代码如下：
/** * @program: Data-Structure * @description: 链表数据结构实现 * @author: 01 * @create: 2018-11-08 15:37 **/ public class LinkedList<E> { /** * 链表中的节点结构 */ private class Node { E e; Node next; public Node() { this(null, null); } public Node(E e) { this(e, null); } public Node(E e, Node next) { this.e = e; this.next = next; } @Override public String toString() { return e.toString(); } } /** * 头节点 */ private Node head; /** * 链表中元素的个数 */ private int size; public LinkedList() { this.head = null; this.size = 0; } /** * 获取链表中的元素个数 * * @return 元素个数 */ public int getSize() { return size; } /** * 链表是否为空 * * @return 为空返回true，否则返回false */ public boolean isEmpty() { return size == 0; } } 在链表中添加元素
我们在为数组添加元素时，最方便的添加方式就是从数组后面进行添加，因为size总是指向数组最后一个元素+1的位置，所以利用size变量我们可以很轻易的完成元素的添加。
而在链表中则相反，我们在链表头添加新的元素最方便，因为链表内维护了一个head变量，即链表的头部，我们只需要将新的元素放入一个新的节点中，然后将新节点内的next变量指向head，最后把head指向这个新节点就完成了元素的添加：
我们来实现这个在链表头添加新的元素的方法，代码如下：
/** * 在链表头添加新的元素e * * @param e 新的元素 */ public void addFirst(E e) { Node node = new Node(e); node.next = head; head = node; // 以上三句代码完全可以直接使用以下一句代码完成， // 但为了让逻辑更清晰所以这里特地将代码分解了 // head = new Node(e, head); size++; } 然后我们来看看如何在链表中指定的位置插入新的节点，虽然这在链表中不是一个常用的操作，但是有些链表相关的题目会涉及到这种操作，所以我们还是得了解一下。例如我们现在要往“索引”为2的位置插入一个新的节点，该如何实现：
虽然链表中没有真正的索引，但是为了实现在指定的位置插入新的节点，我们得引用索引这个概念。如上图中，把链表头看作是索引0，下一个节点看作索引1，以此类推。然后我们还需要有一个prev变量，通过循环移动这个变量去寻找指定的“索引” - 1 的位置，找到之后将新节点的next指向prev的next，prev的next再指向新的节点，即可完成这个插入节点的逻辑，所以关键点就是找到要添加的节点的前一个节点：
具体的实现代码如下：
/** * 在链表的index(0-based)位置添加新的元素e * * @param index 元素添加的位置 * @param e 新的元素 */ public void add(int index, E e) { // 检查索引是否合法 if (index < 0 || index > size) { throw new IllegalArgumentException("Add failed. Illegal index."); } // 链表头添加需特殊处理 if (index == 0) { addFirst(e); } else { Node prev = head; // 移动prev到index - 1的位置 for (int i = 0; i < index - 1; i++) { prev = prev.next; } Node node = new Node(e); node.next = prev.next; prev.next = node; // 同样，以上三句代码可以一句代码完成 // prev.next = new Node(e, prev.next); size++; } } 基于以上这个方法，我们就可以轻易的实现在链表末尾添加新的元素：
/** * 在链表末尾添加新的元素e * * @param e 新的元素 */ public void addLast(E e) { add(size, e); } 使用链表的虚拟头节点
在上一小节中，我们实现向指定位置插入元素的代码里，需对链表头的位置特殊处理，因为链表头没有上一个节点。很多时候使用链表的都需要进行类似的特殊处理，并不是很优雅，所以本小节就是介绍如何优雅的解决这个问题。
之所以要进行特殊处理，主要原因还是head没有上一个节点，初始化prev的时候只能指向head，既然这样我们就给它前面加一个节点好了，这个节点不存储任何数据，仅作为一个虚拟节点。这也是编写链表结构时经常使用到的技巧，添加这么一个节点就可以统一链表的操作逻辑：
修改后的代码如下：
public class LinkedList<E> { ... /** * 虚拟头节点 */ private Node dummyHead; /** * 链表中元素的个数 */ private int size; public LinkedList() { this.dummyHead = new Node(null, null); this.size = 0; } /** * 在链表的index(0-based)位置添加新的元素e * * @param index 元素添加的位置 * @param e 新的元素 */ public void add(int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("Add failed. Illegal index."); } Node prev = dummyHead; // 移动prev到index前一个节点的位置 for (int i = 0; i < index; i++) { prev = prev.next; } Node node = new Node(e); node.next = prev.next; prev.next = node; // 同样，以上三句代码可以一句代码完成 // prev.next = new Node(e, prev.next); size++; } /** * 在链表头添加新的元素e * * @param e 新的元素 */ public void addFirst(E e) { add(0, e); } /** * 在链表末尾添加新的元素e * * @param e 新的元素 */ public void addLast(E e) { add(size, e); } } 链表的遍历、查询和修改
有了以上小节的基础，接下来我们实现链表的遍历、查询和修改就很简单了，代码如下：
/** * 获取链表的第index(0-based)个位置的元素 * * @param index * @return */ public E get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Get failed. Illegal index."); } Node cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.e; } /** * 获取链表中的第一个元素 * * @return */ public E getFirst() { return get(0); } /** * 获取链表中的最后一个元素 * * @return */ public E getLast() { return get(size - 1); } /** * 修改链表的第index(0-based)个位置的元素为e * * @param index * @param e */ public void set(int index, E e) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Set failed. Illegal index."); } Node cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } cur.e = e; } /** * 查找链表中是否包含元素e * * @param e * @return */ public boolean contain(E e) { Node cur = dummyHead.next; // 第一种遍历链表的方式 while (cur != null) { if (cur.e.equals(e)) { return true; } cur = cur.next; } return false; } @Override public String toString() { if (isEmpty()) { return "[]"; } StringBuilder sb = new StringBuilder(); sb.append(String.format("LinkedList: size = %d\n", size)); sb.append("["); Node cur = dummyHead.next; // 第二种遍历链表的方式 for (int i = 0; i < size; i++) { sb.append(cur.e).append(" -> "); cur = cur.next; } // 第三种遍历链表的方式 // for (Node cur = dummyHead.next; cur != null; cur = cur.next) { // sb.append(cur.e).append(" -> "); // } return sb.append("NULL]").toString(); } 从链表中删除元素
最后我们要实现的链表操作就是从链表中删除元素，删除元素就相当于是删除链表中的节点。例如我要删除”索引“为2的节点，同样的我们也需要使用一个prev变量循环移动到要删除的节点的前一个节点上，此时把prev的next拿出来就是待删除的节点。删除节点也很简单，拿出待删除的节点后，将prev的next指向待删除节点的next：
最后将待删除的节点指向一个null，让其脱离链表，这样就能够快速被垃圾回收，如此一来就完成了节点的删除：
具体的实现代码如下：
/** * 从链表中删除第index(0-based)个位置的元素，并返回删除的元素 * * @param index * @return 被删除的节点所存储的元素 */ public E remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("remove failed. Illegal index."); } Node prev = dummyHead; for (int i = 0; i < index; i++) { prev = prev.next; } Node delNode = prev.next; // 把引用改变一下就完成了删除 prev.next = delNode.next; delNode.next = null; size--; return delNode.e; } 基于以上这个方法，我们就可以很简单的实现如下两个方法：
/** * 删除链表中第一个元素 * * @return 被删除的元素 */ public E removeFirst() { return remove(0); } /** * 删除链表中最后一个元素 * * @return 被删除的元素 */ public E removeLast() { return remove(size - 1); } 最后我们来看一下我们实现的这个链表增删查改操作的时间复杂度：
addLast(e) // O(n) addFirst(e) // O(1) add(index, e) // O(n) removeLast() // O(n) removeFirst() // O(1) remove(index) // O(n) set(index, e) // O(n) get(index) // O(n) contain(e) // O(n) 使用链表实现栈
从链表的addFirst和removeFirst方法的时间复杂度可以看到，如果只对链表头进行增、删操作的复杂度是O(1)的，只查询链表头的元素复杂度也是O(1)的。这时我们就可以想到使用链表来实现栈，用链表实现的栈其入栈出栈等操作时间复杂度也都是O(1)的，具体的实现代码如下：
/** * @program: Data-Structure * @description: 基于链表实现栈数据结构 * @author: 01 * @create: 2018-11-08 23:38 **/ public class LinkedListStack<E> implements Stack<E> { private LinkedList<E> linkedList; public LinkedListStack() { this.linkedList = new LinkedList<>(); } @Override public int getSize() { return linkedList.getSize(); } @Override public boolean isEmpty() { return linkedList.isEmpty(); } @Override public void push(E e) { linkedList.addFirst(e); } @Override public E pop() { return linkedList.removeFirst(); } @Override public E peek() { return linkedList.getFirst(); } @Override public String toString() { if (isEmpty()) { return "[]"; } StringBuilder sb = new StringBuilder(); sb.append(String.format("LinkedListStack: size = %d\n", getSize())); sb.append("top ["); for (int i = 0; i < getSize(); i++) { sb.append(linkedList.get(i)); if (i != getSize() - 1) { sb.append(", "); } } return sb.append("]").toString(); } // 测试 public static void main(String[] args) { Stack<Integer> stack = new LinkedListStack<>(); for (int i = 0; i < 5; i++) { stack.push(i); System.out.println(stack); } stack.pop(); System.out.println(stack); } } 带有尾指针的链表：使用链表实现队列
上一小节我们基于链表很轻易的就实现了一个栈结构，本小节我们来看看如何使用链表实现队列结构，看看需要对链表进行哪些改进。
在编写代码之前，我们需要考虑到一个问题，在之前链表结构的实现代码中，只有一个head变量指向头节点，若我们直接使用这个链表实现队列的话，需要操作链尾的元素时，复杂度是O(n)的，因为需要遍历整个链表直到尾节点的位置。那么该如何避开遍历，在O(1)的复杂度下快速的找到尾节点呢？答案就是增加一个tail变量，让这个变量始终指向尾节点即可，这样我们操作尾节点的复杂度就是O(1)了。
除此之外，使用链表实现队列还有一个问题需要考虑，那就是从哪边入队元素，从哪边出队元素。我们之前编写的链表代码中，在链首添加元素是O(1)的，也是最简单方便的，所以我们要将链首作为入队的一端吗？答案是相反的，应该将链首作为出队的一端，链尾作为入队的一端。
因为我们实现的链表是单链结构，在这种情况下链首无论是作为入队还是出队的一端都是可以的，但是链尾不可以，链尾只能作为入队的一端。如果将链尾作为出队的一端，那么出队的复杂度将是O(n)的，需要遍历链表找到尾节点的上一个节点，然后将该节点的next指向null才能完成出队的操作。若是双链结构倒是无所谓，只需要通过tail变量就可以获取到上一个节点，不需要遍历链表去寻找。因此，我们需要将链首作为入队的一端，链尾作为出队的一端，这样无论是出队还是入队的时间复杂度都是O(1)。
具体的实现代码如下：
/** * @program: Data-Structure * @description: 基于链表实现的队列数据结构 * @author: 01 * @create: 2018-11-09 17:00 **/ public class LinkedListQueue<E> implements Queue<E> { private class Node { E e; Node next; public Node() { this(null, null); } public Node(E e) { this(e, null); } public Node(E e, Node next) { this.e = e; this.next = next; } @Override public String toString() { return e.toString(); } } /** * 头节点 */ private Node head; /** * 尾节点 */ private Node tail; /** * 表示队列中的元素个数 */ private int size; @Override public void enqueue(E e) { if (tail == null) { // 链表没有元素 tail = new Node(e); head = tail; } else { // 链尾入队元素 tail.next = new Node(e); tail = tail.next; } size++; } @Override public E dequeue() { if (isEmpty()) { throw new IllegalArgumentException("Can't dequeue from an empty queue."); } // 链首出队元素 Node retNode = head; head = head.next; retNode.next = null; if (head == null) { // 队列里没元素的话，尾节点需要置空 tail = null; } size--; return retNode.e; } @Override public E getFront() { if (isEmpty()) { throw new IllegalArgumentException("Queue is empty."); } return head.e; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public String toString() { if (isEmpty()) { return "[]"; } StringBuilder sb = new StringBuilder(); sb.append(String.format("LinkedListQueue: size = %d\n", getSize())); sb.append("front ["); Node cur = head; while (cur != null) { sb.append(cur.e).append(", "); cur = cur.next; } return sb.append("NULL] tail").toString(); } }