什么是链表? 之前学习过前两节的数组结构 和 栈和队列结构,我们知道都需要一个固定的大小,当达到这个大小时,我们还要进行动态的扩容,在性能上会有很多的浪费,那么是否有不需要动态扩容的数据结构呢? 当然那就是本章要讲解的链表,链表结构没有固定的大小,通过链式的结构存储数据,但是链表丧失了随机访问的能力.每次访问都要从链表头部遍历.

链表的概念

在之前我们学习过的数组结构以及栈和队列结构,栈和队列其实都是通过数组来实现的,都需要申请一个连续的存储空间,如果申请一个100M空间的数组,当内存的空间没有连续和大小不足时会申请失败.
链表结构,不需要一块连续的存储空间,而是通过 指针 将零散的内存块串联起来.
如下图所示: 数组需要提前申请好空间,很容易造成空间的浪费,而链表不用提前申请好空间,在需要的时候才会申请一块内存空间.

d5d5bee4be28326ba3c28373808a62cd.jpg
(图片来自:极客时间<数据结构与算法之美>)

链表常见的结构:单链表、双链表、循环链表.在上节栈和队列结构 中,我们也可以使用链表来实现栈和队列.来提高栈和队列的性能

单链表

链表是将零散的 内存块 串联在一起, 内存块 成为链表的节点,为了将所有的节点串联起来,每个节点存储着数据和指向下一个节点的内存地址,也可以叫做 后继指针 .如下图所示,有两个节点比较特殊,头部的节点和尾部的节点,头部节点记录链表的基地址,尾部节点的指针指向了一个空地址.这样就可以对链表进行遍历.

b93e7ade9bb927baad1348d9a806ddeb.jpg
(图片来自:极客时间)

来实现链表的添加、修改、删除操作,代码如下:
首先我们需要一个节点类,节点类中存储数据和指向下一个的节点.然后新建一个虚拟头部节点,值和指针都为NULL

  1.  //节点
  2.     private static class Node<E> {
  4.         public E e;
  6.         public Node<E> next;
  8.         public Node(E e, Node<E> next) {
  9.             this.e = e;
  10.             this.next = next;
  11.         }
  13.         public Node(Node<E> next) {
  14.             this(null, next);
  15.         }
  17.         public Node(E e) {
  18.             this(e, null);
  19.         }
  20.     }
  22.     //链表的虚拟头部节点
  23.     private Node<E> head;
  24.     private int size;
  26.     public LinkedList() {
  27.         this.head = new Node<>(null, null);
  28.         size = 0;
  29.     }
  31.     public int size(){
  32.         return size;
  33.     }
  35.     public boolean isEmpty(){
  36.         return size == 0;
  37.     }

添加和删除操作,添加数据的逻辑很简单,我们只需要遍历链表到要添加节点的前一个位置,将指针指向新插入的节点,然后新插入的指针指向后一个节点.而链表的删除操作,需要遍历链表到要删除节点的前一个节点perv,将perv->next 指向要删除节点的下一个节点.然后将要删除节点的下一个节点置为NULL即可.

在上两节讲解的数组操作,在插入和删除,为了保证数据的连续性需要进行大量的搬移操作,所以时间复杂度为O(n),而链表的插入和删除只需要修改相邻节点指针的改变就可以了,时间复杂度为O(1).但是链表的随机性访问就没有那么高效了,需要根据指针一个一个节点的遍历.就好像一个队伍,前面的人都知道自己后面的人是谁,但是要只要第K个人是谁就需要一个一个的往下数了.链表的插入操作每次都需要new Node节点,在性能上也存在一定的损耗.

如下图所示:
452e943788bdeea462d364389bd08a17.jpg
(图片来自:极客时间)

理论讲解完毕,下面我们通过代码来实现链表的插入和删除操作

  1. public void add(E e, int index) {
  2.         if (index < 0 || index > size)
  3.             throw new IllegalArgumentException("index > 0 && index < size");
  4.         Node perv = head;
  5.         for (int i = 0; i < index; i++) {
  6.             perv = perv.next;
  7.         }
  8. //            Node<E> node = new Node<>(e);
  9. //            node.next = perv.next;
  10. //            perv.next = node;
  11.         perv.next = new Node(e, perv.next);
  12.         size++;
  13.     }
  14.    /**
  15.      * 添加尾节点
  16.      * O(n)
  17.      * @param e
  18.      */
  19.     public void addLast(E e) {
  20.         add(e, size);
  21.     }
  23.    /**
  24.      * 添加头节点
  25.      * O(1)
  26.      * @param e
  27.      */
  28.     public void addFirst(E e) {
  29. //        Node<E> node = new Node<>(e);
  30. //        node.next = head;
  31. //        head = node;
  32.         add(e, 0);
  33.     }
  35. public E remove(int index) {
  36.         if (index < 0 && index >= size) {
  37.             throw new IllegalArgumentException("Remove Error,Illegal index");
  38.         }
  39.         Node<E> prev = head;//从0开始查找
  40.         for (int i = 0; i < index; i++) {
  41.             prev = prev.next;
  42.         }
  43.         Node<E> dNode = prev.next;
  44.         prev.next = dNode.next;
  45.         dNode.next = null;
  46.         size--;
  47.         return dNode.e;
  48.     }
  49.  public E removeFirst() {
  50.         return remove(0);
  51.     }
  53.     public E removeLast() {
  54.         return remove(size - 1);
  55.     }
  56.    //修改某个节点的值,我们只需要遍历找到这个节点然后修改它的值即可
  57.     public void set(int index, E e) {
  58.         if (index < 0 && index >= size) {
  59.             throw new IllegalArgumentException("Set Error,Illegal index");
  60.         }
  61.         Node<E> node = head.next;//由于head是虚拟节点 获取下一个节点为头节点
  62.         for (int i = 0; i < index; i++) {
  63.             node = node.next;
  64.         }
  65.         node.e = e;
  66.     }

写完之后,我们写一个测试用例(好习惯)来看看链表是否正确

  1.     public static void main(String[] args) {
  2.         LinkedList<Integer> linkedList = new LinkedList<>();
  3.         for (int i = 0; i < 5; i++) {
  4.             linkedList.addFirst(i);
  5.             System.out.println(linkedList);
  6.         }
  7.         linkedList.add(266, 2);
  8.         System.out.println(linkedList);
  9.         linkedList.set(2,100);
  10.         System.out.println(linkedList);
  11.         linkedList.remove(2);
  12.         System.out.println(linkedList);
  13.         linkedList.removeFirst();
  14.         System.out.println(linkedList);
  15.         linkedList.removeLast();
  16.         System.out.println(linkedList);
  17.     }

输出结果:

  1. //头部插入
  2. 0 -> null
  3. 1 -> 0 -> null
  4. 2 -> 1 -> 0 -> null
  5. 3 -> 2 -> 1 -> 0 -> null
  6. 4 -> 3 -> 2 -> 1 -> 0 -> null
  7. //中间插入    
  8. 4 -> 3 -> 266 -> 2 -> 1 -> 0 -> null
  9. //修改某个节点的值    
  10. 4 -> 3 -> 100 -> 2 -> 1 -> 0 -> null
  11. //删除节点    
  12. 4 -> 3 -> 2 -> 1 -> 0 -> null
  13. 3 -> 2 -> 1 -> 0 -> null
  14. 3 -> 2 -> 1 -> null

链式栈结构

在上述中,讲解了单链表的实现,我们来分析一下单链表的一些操作的时间复杂度.

  • 头部插入和头部删除操作,我们只需要修改头节点便可,时间复杂度为O(1)
  • 中间某个位置插入和删除,都需要对节点进行遍历,时间复杂度为:O(n)
  • 尾部插入和删除,需要对节点遍历到尾部,时间复杂度为O(n)

从上面的结论中,可以看出链表的头部插入和头部删除操作时间复杂度为O(1),速度非常快,那么大家想一想有哪些操作是只对头部进行操作呢?

没错就是栈结构,栈结构是后进先出,在上一节中栈和队列结构 中栈结构应用非常广泛,通过数组来实现的栈结构,对数组的尾部进行插入和删除操作同样时间复杂度为O(1),但是数组是一个固定大小的连续存储空间,当数组大小不够时,需要对数组进行扩容操作,当数组太小时需要对数组进行缩容操作,防止数组占用太多的存储空间,所以用数组实现的栈结构当需要很多数据时,在效率上就不是很高了.

链表来实现栈结构,其实非常简单的,用上面实现的单链表结构,对链表进行头部操作即可.代码如下:

  1. public class LinkedStack<E> implements Stack<E> {
  3.     private LinkedList<E> linkedList;
  5.     public LinkedStack() {
  6.         linkedList = new LinkedList<>();
  7.     }
  9.     @Override
  10.     public void push(E e) {
  11.         linkedList.addFirst(e);
  12.     }
  14.     @Override
  15.     public E pop() {
  16.         return linkedList.removeFirst();
  17.     }
  19.     @Override
  20.     public E peek() {
  21.         return linkedList.getFirst();
  22.     }
  24.     @Override
  25.     public int size() {
  26.         return linkedList.size();
  27.     }
  29.     @Override
  30.     public boolean isEmpty() {
  31.         return linkedList.isEmpty();
  32.     }
  34.     @Override
  35.     public String toString() {
  36.         StringBuilder builder = new StringBuilder();
  37.         builder.append("Stack:top");
  38.         builder.append(linkedList);
  39.         return builder.toString();
  40.     }
  41. }

我们使用上述非常简单的代码,就可以实现非常高性能的栈结构,保持好习惯我们写一个测试用例来测试是否正确.

  1.     public static void main(String[] args) {
  2.         LinkedStack<Integer> linkedStack = new LinkedStack<>();
  3.         for (int i = 0; i < 5; i++) {
  4.             linkedStack.push(i);
  5.             System.out.println(linkedStack);
  6.         }
  7.         linkedStack.pop();
  8.         System.out.println(linkedStack);
  9.     }
  11. 输出:
  13. Stack:top 0 -> null
  14. Stack:top 1 -> 0 -> null
  15. Stack:top 2 -> 1 -> 0 -> null
  16. Stack:top 3 -> 2 -> 1 -> 0 -> null
  17. Stack:top 4 -> 3 -> 2 -> 1 -> 0 -> null
  18. Stack:top 3 -> 2 -> 1 -> 0 -> null

下面我们通过一个例子来测试一下,数组实现的栈结构和链表实现的栈结构,性能对比:

  1.     // 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间，单位：秒
  2.     private static double testQueue(Stack<Integer> q, int opCount) {
  4.         long startTime = System.nanoTime();
  6.         Random random = new Random();
  7.         for (int i = 0; i < opCount; i++)
  8.             q.push(random.nextInt(Integer.MAX_VALUE));
  9.         for (int i = 0; i < opCount; i++)
  10.             q.pop();
  12.         long endTime = System.nanoTime();
  14.         return (endTime - startTime) / 1000000000.0;
  15.     }
  17.     public static void main(String[] args) {
  19.         int opCount = 1000000;
  21.         ArrayStack<Integer> arrayQueue = new ArrayStack<>();//0.020
  22.         double time1 = testQueue(arrayQueue, opCount);
  23.         System.out.println("ArrayQueue, time: " + time1 + " s");
  25.         LinkedStack<Integer> loopQueue = new LinkedStack<>();//0.008 链表栈比数组栈性能要高一些，因为数组栈要就行扩容，而链表要不停的new操作，都
  26.         //存在性能问题 在复杂度上没有巨大的差异
  27.         double time2 = testQueue(loopQueue, opCount);
  28.         System.out.println("LoopQueue, time: " + time2 + " s");
  29.     }
  31. 输出:
  32. ArrayStack, time: 0.020 s
  33. LinkedStack, time: 0.008 s

在上述代码中, ArrayStack 和 LinkedStack 分别进行了10万条数据的插入和删除.链表栈比数组栈性能要高一些，因为数组栈要就行扩容，而链表要不停的new操作，都存在性能问题 在复杂度上没有巨大的差异.

链式队列结构

既然链表可以实现栈结构,同样链表也可以实现队列结构, 队列是先进先出结构,所以我们可以通过一个标记尾部的节点来进行队列的入队操作,这样做我们在入队时就已经知道了尾部节点,而不需要进行遍历操作.一个标记的头节点进行队列的出队操作.这样入队和出队时间复杂度都为O(1)

代码实现如下:

  1. public class LinkedQueue<E> implements Queue<E> {
  3.     //节点
  4.     private static class Node<E> {
  6.         public E e;
  8.         public Node<E> next;
  10.         public Node(E e, Node<E> next) {
  11.             this.e = e;
  12.             this.next = next;
  13.         }
  15.         public Node(Node<E> next) {
  16.             this(null, next);
  17.         }
  19.         public Node(E e) {
  20.             this(e, null);
  21.         }
  22.     }
  24.     private Node<E> head, tail;
  26.     private int size = 0;
  28.     public LinkedQueue() {
  29.         head = null;
  30.         tail = null;
  31.         size = 0;
  32.     }
  34.     @Override
  35.     public void enqueue(E e) {
  36.         if (tail == null) {
  37.             tail = new Node<>(e, null);
  38.             head = tail;
  39.         } else {
  40.             tail.next = new Node<>(e, null);
  41.             tail = tail.next;
  42.         }
  43.         size++;
  44.     }
  46.     @Override
  47.     public E dequeue() {
  48.         if (isEmpty()) {
  49.             throw new IllegalArgumentException("queue is Empty");
  50.         }
  51.         Node<E> eNode = head;
  52.         head = head.next;
  53.         eNode.next = null;
  54.         if (head == null) {
  55.             tail = null;
  56.         }
  57.         size--;
  58.         return eNode.e;
  59.     }
  61.     @Override
  62.     public boolean isEmpty() {
  63.         return size == 0;
  64.     }
  66.     @Override
  67.     public int size() {
  68.         return size;
  69.     }
  71.     @Override
  72.     public E getTopQueue() {
  73.         if (tail != null) {
  74.             return tail.e;
  75.         }
  76.         return null;
  77.     }
  78. }

保持好习惯,我们来用一个测试用例来检测我们的代码是否正确

  1.   public static void main(String[] args) {
  2.         LinkedQueue<Integer> arrayQueue = new LinkedQueue<Integer>();
  3.         for (int i = 0; i < 6; i++) {
  4.             arrayQueue.enqueue(i);
  5.         }
  6.         System.out.println(arrayQueue);
  7.         arrayQueue.dequeue();
  8.         System.out.println(arrayQueue);
  9.         arrayQueue.enqueue(7);
  10.         System.out.println(arrayQueue);
  11.         arrayQueue.dequeue();
  12.         System.out.println(arrayQueue);
  13.     }
  14. 输出:
  15. Queue: 
  16. 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> top
  17. Queue: 
  18. 1 -> 2 -> 3 -> 4 -> 5 -> top
  19. Queue: 
  20. 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> top
  21. Queue: 
  22. 2 -> 3 -> 4 -> 5 -> 7 -> top


链式队列结构实现完成后,我们做一个性能对比,在上一节中我们实现了数组队列和循环队列,用我们实现的链式队列和这两个队列进行打擂台,看看哪个性能更好.

  1. // 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间，单位：秒
  2.     private static double testQueue(Queue<Integer> q, int opCount) {
  4.         long startTime = System.nanoTime();
  6.         Random random = new Random();
  7.         for (int i = 0; i < opCount; i++)
  8.             q.enqueue(random.nextInt(Integer.MAX_VALUE));
  9.         for (int i = 0; i < opCount; i++)
  10.             q.dequeue();
  12.         long endTime = System.nanoTime();
  14.         return (endTime - startTime) / 1000000000.0;
  15.     }
  17.     public static void main(String[] args) {
  19.         int opCount = 100000;
  21.         ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
  22.         double time1 = testQueue(arrayQueue, opCount);
  23.         System.out.println("ArrayQueue, time: " + time1 + " s");
  25.         LoopQueue<Integer> loopQueue = new LoopQueue<>();
  26.         double time2 = testQueue(loopQueue, opCount);
  27.         System.out.println("LoopQueue, time: " + time2 + " s");
  29.         LinkedQueue<Integer> linkedQueue = new LinkedQueue<>();
  30.         double time3 = testQueue(linkedQueue, opCount);
  31.         System.out.println("linkedQueue, time: " + time3 + " s");
  32.     }
  34. 输出:
  35. ArrayQueue, time: 3.371875371 s
  36. LoopQueue, time: 0.015056431 s
  37. linkedQueue, time: 0.009146646 s

在上述代码中,我们用一万条数据进行了插入和删除操作,很明显 linkedQueue 的性能要高出 ArrayQueue 和 LoopQueue 很多. 这也充分证明了在编程使用正确的数据结构,有助于我们系统性能的提高.