链表

链表是一种非常重要的线性数据结构，我们在实现栈和队列时使用的是动态数组实现的，这个动态数组是针对用户而言是动态的，实际上底层是静态的，是通过resize()操作去解决容量问题的。而链表则是一种真正的动态数据结构，它是这么一种数据结构，我们把数据存储在一个节点(Node)中，一个节点一般包含两部分的内容，一个是存储的数据，一个是它要指向的下一个节点

  1. class Node {
  2.     private E e;
  3.     private Node next;
  4. }

一个节点指向一个节点，所以最后看起来就像是一个链，我们把这种数据结构称为链表
链表 - 图1
最后一个节点的下一个节点为NULL，表示后面没有节点了。它是一个真正的动态的数据结构，不需要处理容量的问题。但是它也有缺点，它没有数组那样快的查询能力，它要查询某个节点的数据，只能通过头结点一直寻找下来(后面我们将看到)，所以它的查询速度比数组慢。

链表实现

现在我们将实现这么一个结构，首先设计好节点类

  1. public class LinkedList<E> {
  2.     //我们将Node设置为LinkedList的私有内部类
  3.     private class Node<E> {
  4.         public E e;
  5.         public Node next;
  7.         public Node(E e, Node next) {
  8.             this.e = e;
  9.             this.next = next;
  10.         }
  12.         public Node(E e) {
  13.             this(e, null);
  14.         }
  16.         public Node() {
  17.             this(null, null);
  18.         }
  20.         @Override
  21.         public String toString() {
  22.             return e.toString();
  23.         }
  24.     }
  25. }

我们要想向链表中添加(或其他操作)元素，不可避免的要遍历链表(因为链表不能通过索引访问，只能通过前面的节点找到后面的节点)，而要遍历链表，我们就要将链表的头存储起来，这样才能遍历链表，我们将链表的头称为head
链表 - 图2
同时我们使用变量size来记录链表中元素的个数

  1. public class LinkedList<E> {
  2.     //为了节省篇幅，Node类不再展示，下同
  4.     //头结点
  5.     private Node head;
  6.     //链表中元素的个数
  7.     private int size;
  9.     public LinkedList() {
  10.         head = null;
  11.         size = 0;
  12.     }
  13. }

现在我们实现两个简单的方法getSize()和isEmpty()

  1. public int getSize() {
  2.     return size;
  3. }
  4. public boolean isEmpty() {
  5.     return size == 0;
  6. }

添加元素

向链表头添加元素

链表 - 图3
首先将要插入的新节点指向head，然后将head设置为新节点，实现如下

  1. public void addFirst(E e) {
  2.     //体会一下这条语句的意思
  3.     head = new Node(e,head);
  4.     size++;
  5. }

在链表的中间添加一个元素

链表 - 图4
比如现在往节点1后面插入一个元素，首先将新节点指向节点2，然后节点1指向新节点，实现如下

  1. public void add(int index, E e) {
  2.     if (index < 0 || index > size) {
  3.         throw new IllegalArgumentException("参数错误");
  4.     }
  5.     //如果是头结点需要单独处理
  6.     if (index == 0) {
  7.         addFirst(e);
  8.     }
  9.     //prev代表要插入位置的前一个节点
  10.     Node prev = head;
  11.     for (int i = 0; i < index - 1; i++) {
  12.         prev = prev.next;
  13.     }
  14.     prev.next = new Node(e, prev.next);
  15.     size++;
  16. }

向链表的尾部添加一个元素

直接复用上面的代码

  1. public void addLast(E e) {
  2.     add(size, e);
  3. }

虚拟头结点

我们在向链表中添加元素时，因为head前面没有节点，所以我们在添加元素时会对head进行单独的处理，为了不使head具有特殊性，我们在链表的最头部添加一个虚拟头结点，里面不存储元素，它的存在是为了使得操作链表方便
链表 - 图5
现在我们修改上面的head为dummyHead

  1. public class LinkedList<E> {
  4.     //虚拟结点
  5.     private Node dummyHead;
  6.     private int size;
  8.     public LinkedList() {
  9.         //这里修改了
  10.         dummyHead = new Node(null, null);
  11.         size = 0;
  12.     }
  14.     public int getSize() {
  15.         return size;
  16.     }
  17.     public boolean isEmpty() {
  18.         return size == 0;
  19.     }
  21.     //直接调用add方法
  22.     public void addFirst(E e) {
  23.         add(0,e);
  24.     }
  26.     public void add(int index, E e) {
  27.         if (index < 0 || index > size) {
  28.             throw new IllegalArgumentException("参数错误");
  29.         }
  31.         //不需要对head进行单独的处理了
  32.         //index - 1修改为了index
  33.         Node prev = dummyHead;
  34.         for (int i = 0; i < index; i++) {
  35.             prev = prev.next;
  36.         }
  37.         prev.next = new Node(e, prev.next);
  38.         size++;
  39.     }
  41.     public void addLast(E e) {
  42.         add(size, e);
  43.     }
  44. }

获得某个索引的值

实现的思路同add很像，不过这里我们找的不是前一个节点，而是当前的节点

  1. public E get(int index) {
  2.     if (index < 0 || index >= size) {
  3.         throw new IllegalArgumentException("参数错误");
  4.     }
  5.     //cur代表当前节点
  6.     Node cur = dummyHead.next;
  7.     for (int i = 0; i < index; i++) {
  8.         cur = cur.next;
  9.     }
  10.     return (E) cur.e;
  11. }

基于这个方法，我们可以很快的实现getFirst()和getLast()

  1. public E getFirst() {
  2.     return get(0);
  3. }
  4. public E getLast() {
  5.     return get(size - 1);
  6. }

更新某个索引的值

实现的思路完全是同get()方法，直接上代码

  1. public void set(int index, E e) {
  2.     if (index < 0 || index >= size) {
  3.         throw new IllegalArgumentException("参数错误");
  4.     }
  5.     Node cur = dummyHead.next;
  6.     for (int i = 0; i < index; i++) {
  7.         cur = cur.next;
  8.     }
  9.     cur.e = e;
  10. }

查找链表是否存在元素e

  1. public boolean contains(E e) {
  2.     //从当前节点开始，一直遍历到最后一个节点
  3.     for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
  4.         if (cur.e.equals(e)) {
  5.             return true;
  6.         }
  7.     }
  8.     return false;
  9. }

删除链表中的元素

链表 - 图6
上图已详细说明了操作的步骤，这里直接贴上代码实现

  1. public E remove(int index) {
  2.     if (index < 0 || index >= size) {
  3.         throw new IllegalArgumentException("参数错误");
  4.     }
  6.     //获得要删除节点的前一个节点
  7.     Node prev = dummyHead;
  8.     for (int i = 0; i < index; i++) {
  9.         prev = prev.next;
  10.     }
  12.     //图示的操作
  13.     Node delNode = prev.next;
  14.     prev.next = delNode.next;
  15.     delNode.next = null;
  16.     size--;
  17.     return (E) delNode.e;
  18. }

根据上面的方法，可以很快的实现removeFirst()和removeLast()方法

  1. public E removeFirst() {
  2.     return remove(0);
  3. }
  4. public E removeLast() {
  5.     return remove(size - 1);
  6. }

toString()

  1. @Override
  2. public String toString() {
  3.     StringBuilder res = new StringBuilder();
  5.     Node cur = dummyHead.next;
  6.     //你可以使用上面的for循环
  7.     while (cur != null) {
  8.         res.append(cur + "->");
  9.         cur = cur.next;
  10.     }
  11.     res.append("NULL");
  13.     return res.toString();
  14. }

全部代码

  1. public class LinkedList<E> {
  2.     private class Node<E> {
  3.         public E e;
  4.         public Node next;
  6.         public Node(E e, Node next) {
  7.             this.e = e;
  8.             this.next = next;
  9.         }
  11.         public Node(E e) {
  12.             this(e, null);
  13.         }
  15.         public Node() {
  16.             this(null, null);
  17.         }
  19.         @Override
  20.         public String toString() {
  21.             return e.toString();
  22.         }
  23.     }
  25.     private Node dummyHead;
  26.     private int size;
  28.     public LinkedList() {
  29.         dummyHead = new Node(null, null);
  30.         size = 0;
  31.     }
  33.     public int getSize() {
  34.         return size;
  35.     }
  36.     public boolean isEmpty() {
  37.         return size == 0;
  38.     }
  40.     public void addFirst(E e) {
  41.         add(0,e);
  42.     }
  44.     public void add(int index, E e) {
  45.         if (index < 0 || index > size) {
  46.             throw new IllegalArgumentException("参数错误");
  47.         }
  49.         Node prev = dummyHead;
  50.         for (int i = 0; i < index; i++) {
  51.             prev = prev.next;
  52.         }
  53.         prev.next = new Node(e, prev.next);
  54.         size++;
  55.     }
  57.     public void addLast(E e) {
  58.         add(size, e);
  59.     }
  61.     public E get(int index) {
  62.         if (index < 0 || index >= size) {
  63.             throw new IllegalArgumentException("参数错误");
  64.         }
  66.         Node cur = dummyHead.next;
  67.         for (int i = 0; i < index; i++) {
  68.             cur = cur.next;
  69.         }
  71.         return (E) cur.e;
  72.     }
  74.     public E getFirst() {
  75.         return get(0);
  76.     }
  77.     public E getLast() {
  78.         return get(size - 1);
  79.     }
  81.     public void set(int index, E e) {
  82.         if (index < 0 || index >= size) {
  83.             throw new IllegalArgumentException("参数错误");
  84.         }
  86.         Node cur = dummyHead.next;
  87.         for (int i = 0; i < index; i++) {
  88.             cur = cur.next;
  89.         }
  91.         cur.e = e;
  92.     }
  94.     public boolean contains(E e) {
  95.         for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
  96.             if (cur.e.equals(e)) {
  97.                 return true;
  98.             }
  99.         }
  101.         return false;
  102.     }
  104.     public E remove(int index) {
  105.         if (index < 0 || index >= size) {
  106.             throw new IllegalArgumentException("参数错误");
  107.         }
  109.         Node prev = dummyHead;
  110.         for (int i = 0; i < index; i++) {
  111.             prev = prev.next;
  112.         }
  114.         Node delNode = prev.next;
  115.         prev.next = delNode.next;
  116.         delNode.next = null;
  118.         size--;
  120.         return (E) delNode.e;
  121.     }
  123.     public E removeFirst() {
  124.         return remove(0);
  125.     }
  126.     public E removeLast() {
  127.         return remove(size - 1);
  128.     }
  130.     @Override
  131.     public String toString() {
  132.         StringBuilder res = new StringBuilder();
  134.         Node cur = dummyHead.next;
  135.         while (cur != null) {
  136.             res.append(cur + "->");
  137.             cur = cur.next;
  138.         }
  139.         res.append("NULL");
  141.         return res.toString();
  142.     }
  143. }

使用链表实现栈

由于链表的addFirst()和removeFirst()的操作都是O(1)，所以我们使用链表头作为栈顶，具体的实现逻辑如下

  1. public class LinkedListStack<E> implements Stack<E> {
  2.     private LinkedList<E> linkedList;
  4.     public LinkedListStack() {
  5.         linkedList = new LinkedList<>();
  6.     }
  8.     @Override
  9.     public void push(E e) {
  10.         linkedList.addFirst(e);
  11.     }
  13.     @Override
  14.     public E pop() {
  15.         return linkedList.removeFirst();
  16.     }
  18.     @Override
  19.     public boolean isEmpty() {
  20.         return linkedList.isEmpty();
  21.     }
  23.     @Override
  24.     public int getSize() {
  25.         return linkedList.getSize();
  26.     }
  28.     @Override
  29.     public E peek() {
  30.         return linkedList.getFirst();
  31.     }
  33.     @Override
  34.     public String toString() {
  35.         StringBuilder res = new StringBuilder();
  36.         res.append("Stack: top ");
  37.         res.append(linkedList);
  39.         return res.toString();
  40.     }
  41. }

使用链表实现队列

我们之前使用数组实现队列，由于它的dequeue操作是O(n)级别的，所以我们使用front来标记队首，使用循环队列设计，同样的在链表中从链表尾部删除或增加元素都是O(n)级别的，为了解决这一个问题，我们决定在链表的尾部增加一个tail变量来标记，从而使得在尾部增加元素是O(1)级别的
链表 - 图7
另外考虑在尾部删除一个元素是O(1)的吗? 答案是不是。因为我们删除一个节点需要知道该节点的前一个节点，而知道tail节点是无法知道tail的前一个节点的，我们还是要遍历。所以我们在head端删除元素，在tail端添加元素，并且由于只涉及到头部和尾部的操作，所以我们也不需要添加虚拟头结点了
链表 - 图8
下面就是实现的代码

  1. public class LinkedListQueue<E> implements Queue<E> {
  2.     private class Node<E> {
  3.         public E e;
  4.         public Node next;
  6.         public Node(E e, Node next) {
  7.             this.e = e;
  8.             this.next = next;
  9.         }
  11.         public Node(E e) {
  12.             this(e, null);
  13.         }
  15.         public Node() {
  16.             this(null, null);
  17.         }
  19.         @Override
  20.         public String toString() {
  21.             return e.toString();
  22.         }
  23.     }
  25.     private Node head;
  26.     private Node tail;
  27.     private int size;
  29.     public LinkedListQueue() {
  30.         head = null;
  31.         tail = null;
  32.         size = 0;
  33.     }
  35.     @Override
  36.     public void enqueue(E e) {
  37.         //队列为空时，tail和head都为null 添加元素后二者都指向第一个元素
  38.         if (size == 0) {
  39.             tail = new Node(e);
  40.             head = tail;
  41.         } else {
  42.             tail.next = new Node(e);
  43.             tail = tail.next;
  44.         }
  45.         size++;
  46.     }
  48.     @Override
  49.     public E dequeue() {
  50.         if (size == 0) {
  51.             throw new IllegalArgumentException("队列为空");
  52.         }
  54.         Node delNode = head;
  55.         head = head.next;
  56.         delNode.next = null;
  58.         size--;
  59.         //如果队列为空了，此时tail指向的是delNode，此时应该让tail为null
  60.         if (size == 0) {
  61.             tail = null;
  62.         }
  63.         return (E) delNode.e;
  64.     }
  66.     @Override
  67.     public E getFront() {
  68.         if (head == null) {
  69.             throw new IllegalArgumentException("队列为空");
  70.         }
  72.         return (E) head.e;
  73.     }
  75.     @Override
  76.     public int getSize() {
  77.         return size;
  78.     }
  80.     @Override
  81.     public boolean isEmpty() {
  82.         return size == 0;
  83.     }
  85.     @Override
  86.     public String toString() {
  87.         StringBuilder res = new StringBuilder();
  89.         res.append("Queue: front ");
  91.         Node cur = head;
  92.         while (cur != null) {
  93.             res.append(cur + "->");
  94.             cur = cur.next;
  95.         }
  96.         res.append("NULL tail");
  98.         return res.toString();
  99.     }
  100. }