1、什么是链表？(摘自LeetCode-小灰的算法之旅)

image.png

地下党都是一些什么样的人物呢? 在影视作品中，我们可能都见到过地下工作者的经典话语： “上级的姓名、住址，我知道，下级的姓名、住址，我也知道，但是这些都是我们党的秘密，不能告诉你们！” 地下党借助这种单线联络的方式，灵活隐秘地传递着各种重要信息。 在计算机科学领域里，有一种数据结构也恰恰具备这样的特征，这种数据结构就是链表。 链表是什么样子的？为什么说它像地下党呢？ 让我们来看一看单向链表的结构。

image.png

链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。 单向链表的每一个节点又包含两部分，一部分是存放数据的变量 data，另一部分是指向下一个节点的指针 next。

  1. private static class Node {
  2.     int data;
  3.     Node next;
  4. }

链表的第 1 个节点被称为头节点，最后 1 个节点被称为尾节点，尾节点的 next 指针指向空。 与数组按照下标来随机寻找元素不同，对于链表的其中一个节点 A，我们只能根据节点 A 的 next 指针来找到该节点的下一个节点 B，再根据节点 B 的 next 指针找到下一个节点 C…… 这正如地下党的联络方式，一级一级，单线传递。

image.png

什么是双向链表？ 双向链表比单向链表稍微复杂一些，它的每一个节点除了拥有 data 和 next 指针，还拥有指向前置节点的 prev 指针。

image.png

接下来我们看一看链表的存储方式。 如果说数组在内存中的存储方式是顺序存储，那么链表在内存中的存储方式则是 随机存储。 什么叫随机存储呢？ 上一节我们讲解了数组的内存分配方式，数组在内存中占用了连续完整的存储空间。而链表则采用了见缝插针的方式，链表的每一个节点分布在内存的不同位置，依靠 next 指针关联起来。这样可以灵活有效地利用零散的碎片空间。 让我们看一看下面两张图，对比一下数组和链表在内存中分配方式的不同。

image.png

图中的箭头代表链表节点的 next 指针。

image.png

2、链表的基本操作(摘自LeetCode-小灰的算法之旅)

2.1、查找节点

在查找元素时，链表不像数组那样可以通过下标快速进行定位，只能从头节点开始向后一个一个节点逐一查找。 例如给出一个链表，需要查找从头节点开始的第 3 个节点。

image.png
第 1 步，将查找的指针定位到头节点。
image.png
第 2 步，根据头节点的 next 指针，定位到第 2 个节点。
image.png
第 3 步，根据第 2 个节点的 next 指针，定位到第 3 个节点，查找完毕。
image.png
image.png

2.2、更新节点

如果不考虑查找节点的过程，链表的更新过程会像数组那样简单，直接把旧数据替换成新数据即可。
image.png

2.3、插入节点

与数组类似，链表插入节点时，同样分为 3 种情况。

  • 尾部插入
  • 中间插入
  • 头部插入

尾部插入，是最简单的情况，把最后一个节点的 next 指针指向新插入的节点即可。
image.png
头部插入，可以分成两个步骤。
第 1 步，把新节点的 next 指针指向原先的头节点。
第 2 步，把新节点变为链表的头节点。
image.png
中间插入，同样分为两个步骤。
第 1 步，新节点的 next 指针，指向插入位置的节点。
第 2 步，插入位置前置节点的 next 指针，指向新节点。
image.png
只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要像数组那样考虑扩容的问题。

2.4、删除元素

链表的删除操作同样分为 3 种情况。

  • 尾部删除
  • 头部删除
  • 中间删除

尾部删除，是最简单的情况，把倒数第 2 个节点的 next 指针指向空即可。
image.png
头部删除，也很简单，把链表的头节点设为原先头节点的 next 指针即可。
image.png
中间删除，同样很简单，把要删除节点的前置节点的 next 指针，指向要删除元素的下一个节点即可。
image.png
这里需要注意的是，许多高级语言，如 Java，拥有自动化的垃圾回收机制，所以我们不用刻意去释放被删除的节点，只要没有外部引用指向它们，被删除的节点会被自动回收。

image.png

  1. //头节点指针
  2. private Node head;
  3. //尾节点指针
  4. private Node last;
  5. //链表实际长度
  6. private int size;
  7. /**
  8. * 链表插入元素
  9.  * @param data 插入元素
  10.  * @param index 插入位置
  11.  */
  12. public void insert(int data, int index) throws Exception {
  13.     if (index<0 || index>size) {
  14.         throw new IndexOutOfBoundsException("超出链表节点范围！");
  15.     }
  16.     Node insertedNode = new Node(data);
  17.     if(size == 0){
  18.         //空链表
  19.         head = insertedNode;
  20.         last = insertedNode;
  21.     } else if(index == 0){
  22.         //插入头部
  23.         insertedNode.next = head;
  24.         head = insertedNode;
  25.     }else if(size == index){
  26.         //插入尾部
  27.         last.next = insertedNode;
  28.         last = insertedNode;
  29.     }else {
  30.         //插入中间
  31.         Node prevNode = get(index-1);
  32.         insertedNode.next = prevNode.next;
  33.         prevNode.next = insertedNode;
  34.     }
  35.     size++;
  36. }
  38. /**
  39.  * 链表删除元素
  40.  * @param index 删除的位置
  41.  */
  42. public Node remove(int index) throws Exception {
  43.     if (index<0 || index>=size) {
  44.         throw new IndexOutOfBoundsException("超出链表节点范围！");
  45.     }
  46.     Node removedNode = null;
  47.     if(index == 0){
  48.         //删除头节点
  49.         removedNode = head;
  50.         head = head.next;
  51.     }else if(index == size-1){
  52.         //删除尾节点
  53.         Node prevNode = get(index-1);
  54.         removedNode = prevNode.next;
  55.         prevNode.next = null;
  56.         last = prevNode;
  57.     }else {
  58.         //删除中间节点
  59.         Node prevNode = get(index-1);
  60.         Node nextNode = prevNode.next.next;
  61.         removedNode = prevNode.next;
  62.         prevNode.next = nextNode;
  63.     }
  64.     size--;
  65.     return removedNode;
  66. }
  67. /**
  68. * 链表查找元素
  69. * @param index 查找的位置
  70. */
  71. public Node get(int index) throws Exception {
  72.     if (index<0 || index>=size) {
  73.         throw new IndexOutOfBoundsException("超出链表节点范围！");
  74.     }
  75.     Node temp = head;
  76.     for(int i=0; i<index; i++){
  77.         temp = temp.next;
  78.     }
  79.     return temp;
  80. }
  82. /**
  83.  * 输出链表
  84.  */
  85. public void output(){
  86.     Node temp = head;
  87.     while (temp!=null) {
  88.         System.out.println(temp.data);
  89.         temp = temp.next;
  90.     }
  91. }
  93. /**
  94.  * 链表节点
  95.  */
  96. private static class Node {
  97.     int data;
  98.     Node next;
  99.     Node(int data) {
  100.         this.data = data;
  101.     }
  102. }
  104. public static void main(String[] args) throws Exception {
  105.     MyLinkedList myLinkedList = new MyLinkedList();
  106.     myLinkedList.insert(3,0);
  107.     myLinkedList.insert(7,1);
  108.     myLinkedList.insert(9,2);
  109.     myLinkedList.insert(5,3);
  110.     myLinkedList.insert(6,1);
  111.     myLinkedList.remove(0);
  112.     myLinkedList.output();
  113. }

以上是对单链表相关操作的代码实现。为了尾部插入的方便，代码中额外增加了指向链表尾节点的指针 last。

3、数组vs链表

image.png