基于节点的数据结构—链表

数组存储：连续的内存空间，并且预留一部分空间方便扩展。这样会大大降低内存的使用率。
链表 - 图1
如上图降低电影院入座率一样。

链表

功能与数组类似——用于存储一系列相同类型的数组。只是存储方式不同。

节点

链表中每个元素我们称之为节点。
链表 - 图2
节点由两部分组成——节点内容和下一个节点地址
与数组的区别就是多了下一个节点的地址。
为什么需要下一个节点地址？

  • 数组中由于连续内存空间存储，可通过start_adress+item_size*i来获取元素位置。
  • 链表中是分散储存的，所以要保存下一个节点位置。

好处：数据分散存储在内存中，达到内存最大利用率。
节点类

  1. public class Node {
  3.   private int content;
  5.   private Node next;
  7.   public Node() {
  8.   }
  10.   public Node(int content, Node next) {
  11.     this.content = content;
  12.     this.next = next;
  13.   }
  15.   public int getContent() {
  16.     return content;
  17.   }
  19.   public void setContent(int content) {
  20.     this.content = content;
  21.   }
  23.   public Node getNext() {
  24.     return next;
  25.   }
  27.   public void setNext(Node next) {
  28.     this.next = next;
  29.   }
  30. }

代码实现链表：

  1. public class Demo {
  3.   // 创建链表
  4.   public static Node createLinkedList(int[] array) {
  5.    if (array.length==1){
  6.     Node root = null;
  7.      return new Node(array[0],root);
  8.    } 
  9.     int[] newarray = new int[array.length-1];
  10.     for (int i=1;i<array.length ;i++ ){
  11.       newarray[i-1] = array[i] ;
  12.     } 
  15.     return new Node(array[0],createLinkedList(newarray));
  16.   }
  18.   public static void main(String[] args) {
  19.     int[] array = {9, 2, 4};
  20.     Node root = createLinkedList(array);
  21.     System.out.println(root.getContent());
  22.   }
  23. }

答案：

  1. public class Demo {
  3.   // 创建链表
  4.   public static Node createLinkedList(int[] array) {
  5.     // 创建一个根节点
  6.     Node root = null;
  7.     // 从末尾元素开始依次创建Node节点
  8.     for (int i = array.length - 1; i >= 0; i--) {
  9.       Node node = new Node(array[i], null);
  10.       // 创建两个节点的连接关系
  11.       if (root != null) {
  12.         node.setNext(root);
  13.         root = node;
  14.       } else {
  15.         root = node;
  16.       }
  17.     }
  18.     return root;
  19.   }
  21.   public static void main(String[] args) {
  22.     int[] array = {9, 2, 4};
  23.     Node root = createLinkedList(array);
  24.     System.out.println(root.getContent());
  25.   }
  26. }

链表的读取与查找

读取

通过第一个节点的地址，依次遍历找到第三个节点地址。
链表 - 图3

时间复杂度

读取第一个O（1），最坏读取最后一个需要N步，所以为O（N）。

查找

链表 - 图4
时间复杂度：O（N）

模拟实现JAVA中的LinkedList（底层是用链表实现的）

  1. public class YKDLinkedList {
  3.   private Node root = null;
  4.   int size = 0;
  6.   public YKDLinkedList() {
  7.   }
  9.   // 数组创建一个链表
  10.   public static Node createLinkedLNode(int[] array) {
  11.     // 创建一个根节点
  12.     Node root = null;
  13.     // 从末尾元素开始依次创建Node节点
  14.     for (int i = array.length - 1; i >= 0; i--) {
  15.       Node node = new Node(array[i], null);
  16.       // 创建两个节点的连接关系
  17.       if (root != null) {
  18.         node.setNext(root);
  19.         root = node;
  20.       } else {
  21.         root = node;
  22.       }
  23.     }
  24.     return root;
  25.   }
  27.   public YKDLinkedList(int[] array) {
  28.     this.root = YKDLinkedList.createLinkedLNode(array);
  29.     this.size = array.length;
  30.   }
  32.   // 获取长度
  33.   public int size() {
  34.     return this.size;
  35.   }
  37.   // 获取某个索引节点内容
  38.   public int get(int index) {
  39.     int i = 0;
  40.     Node node = this.root;
  41.     // 依次往前推进
  42.     while (i < index) {
  43.       node = node.getNext();
  44.       i++;
  45.     }
  46.     return node.getContent();
  47.   }
  49.   // 查找某个值的索引值，默认不存在为-1
  50.   public int find(int value) {
  51.     Node node = this.root;
  52.     // index 保存当前的索引
  53.     int index = 0;
  54.     // 依次遍历链表，找到内容等于value的node，返回index
  55.     while (node != null && node.getNext() != null) {
  56.       if (node.getContent() == value) {
  57.         return index;
  58.       }
  59.       node = node.getNext();
  60.       index++;
  61.     }
  62.     return -1;
  63.   }
  65.   public static void main(String[] args) {
  66.     int[] array = {9, 2, 4};
  67.     YKDLinkedList linkedList = new YKDLinkedList(array);
  68.     System.out.println(linkedList.find(2));
  69.     System.out.println(linkedList.find(5));
  70.     System.out.println(linkedList.get(2));
  71.   }
  72. }

链表的插入

头部插入

链表 - 图5

中间插入

链表 - 图6

尾部插入

链表 - 图7

代码实现

  1. public class YKDLinkedList {
  3.   private Node root = null;
  4.   int size = 0;
  6.   public YKDLinkedList() {
  7.   }
  9.   // 数组创建一个链表
  10.   public static Node createLinkedLNode(int[] array) {
  11.     // 创建一个根节点
  12.     Node root = null;
  13.     // 从末尾元素开始依次创建Node节点
  14.     for (int i = array.length - 1; i >= 0; i--) {
  15.       Node node = new Node(array[i], null);
  16.       // 创建两个节点的连接关系
  17.       if (root != null) {
  18.         node.setNext(root);
  19.         root = node;
  20.       } else {
  21.         root = node;
  22.       }
  23.     }
  24.     return root;
  25.   }
  27.   public YKDLinkedList(int[] array) {
  28.     this.root = YKDLinkedList.createLinkedLNode(array);
  29.     this.size = array.length;
  30.   }
  32.   // 获取长度
  33.   public int size() {
  34.     return this.size;
  35.   }
  37.   // 获取某个索引节点内容
  38.   public int get(int index) {
  39.     int i = 0;
  40.     Node node = this.root;
  41.     // 依次往前推进
  42.     while (i < index) {
  43.       node = node.getNext();
  44.       i++;
  45.     }
  46.     return node.getContent();
  47.   }
  49.   // 查找某个值的索引值，默认不存在为-1
  50.   public int find(int value) {
  51.     Node node = this.root;
  52.     // index 保存当前的索引
  53.     int index = 0;
  54.     // 依次遍历链表，找到内容等于value的node，返回index
  55.     while (node != null && node.getNext() != null) {
  56.       if (node.getContent() == value) {
  57.         return index;
  58.       }
  59.       node = node.getNext();
  60.       index++;
  61.     }
  62.     return -1;
  63.   }
  65.   // 末尾添加元素
  66.   public boolean add(int value) {
  67.     return this.add(this.size - 1, value);
  68.   }
  70.   // 头部插入元素
  71.   public boolean addFirst(int value) {
  72.     return this.add(-1, value);
  73.   }
  75.   // 插入元素
  76.   public boolean add(int index, int value) {
  77.     if (index < -1 || index > this.size - 1){
  78.       return false;
  79.     }
  80.     if (index == -1) {
  81.       if (this.root != null) {
  82.         this.root = new Node(value, this.root);
  83.       } else {
  84.         this.root = new Node(value, null);
  85.       }
  86.     } else {
  87.       Node pre = this.root;
  88.       while (index > 0) {
  89.         if (pre.getNext() == null) {
  90.           return false;
  91.         }
  92.         pre = this.root.getNext();
  93.         index--;
  94.       }
  96.       if (pre == null) {
  97.         return false;
  98.       }
  100.       Node newNode = new Node(value, pre.getNext());
  101.       pre.setNext(newNode);
  102.     }
  103.     this.size++;
  104.     return true;
  105.   }
  107.   // 链表中的元素字符串形式
  108.   public String toString() {
  109.     if (this.root == null) {
  110.       return "";
  111.     }
  113.     StringBuilder str = new StringBuilder();
  114.     Node node = this.root;
  115.     while (node != null) {
  116.       str.append(node.getContent()).append(" ");
  117.       node = node.getNext();
  118.     }
  119.     return str.toString();
  120.   }
  122.   public static void main(String[] args) {
  123.     YKDLinkedList linkedList = new YKDLinkedList();
  124.     boolean result = linkedList.add(9);
  125.     if (!result) {
  126.       System.out.println("9插入失败");
  127.       return;
  128.     }
  129.     result = linkedList.add(4);
  130.     if (!result) {
  131.       System.out.println("4插入失败");
  132.       return;
  133.     }
  134.     result = linkedList.add(0, 2);
  135.     if (!result) {
  136.       System.out.println("2插入失败");
  137.       return;
  138.     }
  139.     result = linkedList.addFirst(10);
  140.     if (!result) {
  141.       System.out.println("10插入失败");
  142.       return;
  143.     }
  144.     System.out.println(linkedList.toString());
  145.   }
  146. }

链表删除

头部删除

链表 - 图8

中间删除

链表 - 图9

尾部删除

链表 - 图10

代码实现

  1. public class YKDLinkedList {
  3.   private Node root = null;
  4.   int size = 0;
  6.   public YKDLinkedList() {
  7.   }
  9.   // 数组创建一个链表
  10.   public static Node createLinkedLNode(int[] array) {
  11.     // 创建一个根节点
  12.     Node root = null;
  13.     // 从末尾元素开始依次创建Node节点
  14.     for (int i = array.length - 1; i >= 0; i--) {
  15.       Node node = new Node(array[i], null);
  16.       // 创建两个节点的连接关系
  17.       if (root != null) {
  18.         node.setNext(root);
  19.         root = node;
  20.       } else {
  21.         root = node;
  22.       }
  23.     }
  24.     return root;
  25.   }
  27.   public YKDLinkedList(int[] array) {
  28.     this.root = YKDLinkedList.createLinkedLNode(array);
  29.     this.size = array.length;
  30.   }
  32.   // 获取长度
  33.   public int size() {
  34.     return this.size;
  35.   }
  37.   // 获取某个索引节点内容
  38.   public int get(int index) {
  39.     int i = 0;
  40.     Node node = this.root;
  41.     // 依次往前推进
  42.     while (i < index) {
  43.       node = node.getNext();
  44.       i++;
  45.     }
  46.     return node.getContent();
  47.   }
  49.   // 查找某个值的索引值，默认不存在为-1
  50.   public int find(int value) {
  51.     Node node = this.root;
  52.     // index 保存当前的索引
  53.     int index = 0;
  54.     // 依次遍历链表，找到内容等于value的node，返回index
  55.     while (node != null && node.getNext() != null) {
  56.       if (node.getContent() == value) {
  57.         return index;
  58.       }
  59.       node = node.getNext();
  60.       index++;
  61.     }
  62.     return -1;
  63.   }
  65.   // 末尾添加元素
  66.   public boolean add(int value) {
  67.     return this.add(this.size - 1, value);
  68.   }
  70.   // 头部插入元素
  71.   public boolean addFirst(int value) {
  72.     return this.add(-1, value);
  73.   }
  75.   // 插入元素
  76.   public boolean add(int index, int value) {
  77.     if (index < -1 || index > this.size - 1){
  78.       return false;
  79.     }
  80.     if (index == -1) {
  81.       if (this.root != null) {
  82.         this.root = new Node(value, this.root);
  83.       } else {
  84.         this.root = new Node(value, null);
  85.       }
  86.     } else {
  87.       Node pre = this.root;
  88.       while (index > 0) {
  89.         if (pre.getNext() == null) {
  90.           return false;
  91.         }
  92.         pre = this.root.getNext();
  93.         index--;
  94.       }
  96.       if (pre == null) {
  97.         return false;
  98.       }
  100.       Node newNode = new Node(value, pre.getNext());
  101.       pre.setNext(newNode);
  102.     }
  103.     this.size++;
  104.     return true;
  105.   }
  107.   // 删除最后一个元素
  108.   public boolean removeLast() {
  109.     return this.remove(this.size - 1);
  110.   }
  112.   // 删除第一个元素
  113.   public boolean removeFirst() {
  114.     return this.remove(0);
  115.   }
  117.   // 插入元素
  118.   // index = 0, 表示删除第 1 个元素
  119.   // index = n，表示删除第 n+1 个元素
  120.   public boolean remove(int index) {
  121.     if (index < 0 || index > this.size - 1){
  122.       return false;
  123.     }
  124.     // 判断整个列表为空情况，删除失败
  125.     if (this.root == null) {
  126.       return false;
  127.     }
  128.     if (index == 0) {
  129.       // 删除第一个元素，情况比较简单，注意必须先保留 this.root，因为紧接着 this.root 会被修改
  130.       Node node = this.root;
  131.       this.root = node.getNext();
  132.       node.setNext(null);
  133.     } else {
  134.       // 判断越界问题
  135.       if(this.size < index + 1){
  136.         return false;
  137.       }
  138.       // 遍历获取index的前置节点
  139.       Node pre = this.root;
  140.       while (index > 1) {
  141.         pre = pre.getNext();
  142.         index--;
  143.       }
  144.       // 修改next指针，同样大家需要先保存 pre.next，因为紧接着下一步会修改 pre.next 指针
  145.       Node next = pre.getNext();
  146.       pre.setNext(next.getNext());
  147.       next.setNext(null);
  148.     }
  149.     this.size--;
  150.     return true;
  151.   }
  153.   // 链表中的元素字符串形式
  154.   public String toString() {
  155.     if (this.root == null) {
  156.       return "";
  157.     }
  159.     StringBuilder str = new StringBuilder();
  160.     Node node = this.root;
  161.     while (node != null) {
  162.       str.append(node.getContent()).append(" ");
  163.       node = node.getNext();
  164.     }
  165.     return str.toString();
  166.   }
  168.   public static void main(String[] args) {
  169.     int[] array = {10, 9, 2, 4};
  170.     YKDLinkedList linkedList = new YKDLinkedList(array);
  171.     boolean result = linkedList.removeFirst();
  172.     if (!result) {
  173.       System.out.println("removeFirst失败");
  174.       return;
  175.     }
  176.     result = linkedList.removeLast();
  177.     if (!result) {
  178.       System.out.println("removeLast失败");
  179.       return;
  180.     }
  181.     result = linkedList.remove(1);
  182.     if (!result) {
  183.       System.out.println("remove(1)失败");
  184.       return;
  185.     }
  187.     System.out.println(linkedList.toString());
  188.   }
  189. }

链表VS数组

链表 - 图11

image.png

复杂场景

我们手里有一堆手机号码，我们希望写一个算法删除无效的手机号码。
具体逻辑：我们每次读取一个手机号码，判断这个手机号码是否是11位，并且满足正则表达式的要求。
遍历
无论是数组还是链表都要进行N次遍历

删除
数组：每次删除都需要移动后面的元素，所以每次删除的时间复杂度为O（N）。
链表：则是O(1)。

总结

在频繁插入和删除的情况下，链表有绝对的优势。

链表经典算法题—多指针使用

如何查找单向链表中倒数第K个节点。

假设链表中：9，2，4，5，6，8，0，3，10
当k为3和6时，结果为0和5。
单向链表——导致节点只知道自己后面的节点，那该如何获取倒数第K个节点呢。

暴力法

  1. 第一次循环，获取链表所有节点个数，设为N
  2. 第二次循环，只需要推进N-k次即可。

代码如下：

  1. // 找寻倒数第 k 个节点内容
  2. public static int findK(Node node, int k) {
  3.     // 第一步，计算链表的长度
  4.     int size = 0;
  5.     Node p = node;
  6.     while (p != null) {
  7.         p = p.getNext();
  8.         size++;
  9.     }
  11.     // 第二步，推进 size - k 步
  12.     Node c = node;
  13.     int index = size - k;
  14.     while (index > 0) {
  15.         c = c.getNext();
  16.         index--;
  17.     }
  18.     return c.getContent();
  19. }

双指针法

  1. 先申明一个先驱指针。为了探索链表的边界。我们将先驱指针移动k-1位。移动后我们开始申明一个新的指针实际指针，用来寻找倒数第k个节点。
  2. 同时移动两个指针
  3. 结束条件：先驱指针执行到链表结尾位置，这是，实际指针刚好指向倒数第K个位置。
    代码实现
    ```java

public class Demo {

// 找寻倒数第 k 个节点内容 public static int findK(Node node, int k) { Node preNode = node; for (int i=0;i<k-1 ;i++ ){ preNode = preNode.getNext(); } Node nowNode = node; while(preNode.getNext()!=null){ preNode = preNode.getNext(); nowNode = nowNode.getNext(); } return nowNode.getContent(); }

// 数组创建一个链表 public static Node createLinkedLNode(int[] array) { // 创建一个根节点 Node root = null; // 从末尾元素开始依次创建Node节点 for (int i = array.length - 1; i >= 0; i—) { Node node = new Node(array[i], null); // 创建两个节点的连接关系 if (root != null) { node.setNext(root); root = node; } else { root = node; } } return root; }

public static void main(String[] args) { int[] array = {9, 2, 4, 5, 6, 8, 0, 3, 10}; Node root = createLinkedLNode(array); int result = findK(root, 3); System.out.println(“k = 3 result: “ + result); result = findK(root, 6); System.out.println(“k = 6 result: “ + result); } }

  1. <a name="UMq6V"></a>
  2. #### 双指针变形——获取中心节点
  3. ```java
  4. public class Demo {
  6.   // 找寻倒数第 k 个节点内容
  7.   public static int findCenter(Node node) {
  8.     // 创建先驱指针
  9.     Node pioneer = node;
  10.     // 创建实际指针
  11.     Node current = node;
  13.     // 每次遍历需要实际指针移动一步，先驱指针移动二步
  14.     while(pioneer.getNext() != null){
  15.       current = current.getNext();
  16.       pioneer = pioneer.getNext();
  17.       if(pioneer.getNext() != null){
  18.         pioneer = pioneer.getNext();
  19.       }
  20.     }
  22.     return current.getContent();
  23.   }
  25.   // 数组创建一个链表
  26.   public static Node createLinkedLNode(int[] array) {
  27.     // 创建一个根节点
  28.     Node root = null;
  29.     // 从末尾元素开始依次创建Node节点
  30.     for (int i = array.length - 1; i >= 0; i--) {
  31.       Node node = new Node(array[i], null);
  32.       // 创建两个节点的连接关系
  33.       if (root != null) {
  34.         node.setNext(root);
  35.         root = node;
  36.       } else {
  37.         root = node;
  38.       }
  39.     }
  40.     return root;
  41.   }
  44.   public static void main(String[] args) {
  45.     int[] array1 = {9, 2, 4, 5, 6, 8, 0, 3, 10};
  46.     Node root1 = createLinkedLNode(array1);
  47.     int result = findCenter(root1);
  48.     System.out.println("array1 result: " + result);
  50.     int[] array2 = {9, 2, 4, 5, 6, 7, 8, 0, 3, 10};
  51.     Node root2 = createLinkedLNode(array2);
  52.     result = findCenter(root2);
  53.     System.out.println("array2 result: " + result);
  54.   }
  55. }

有环链表

链表 - 图13
检查链表是否有环

  1. public class Demo {
  3.   // 查询链表是否有环，true是有环，false是无环
  4.   public static boolean hasCircle(Node node) {
  5.     // 移动先驱指针
  6.     if (node == null || node.getNext() == null) {
  7.       return false;
  8.     }
  10.     // first 每次前进一步
  11.     Node first = node;
  12.     // second 每次前进两步
  13.     Node second = node.getNext();
  15.     // 核心逻辑：如果链表中有环，两个指针用不同速度运行，最终second会追上first，也就是 first == second。
  16.     while (first != null && second != null && first != second) {
  17.       first = first.getNext();
  18.       second = second.getNext();
  19.       if (second != null) {
  20.         second = second.getNext();
  21.       }
  22.     }
  24.     // 如果相等，并且不为空，则表示有环
  25.     if (first != null && first == second) {
  26.       return true;
  27.     }
  28.     return false;
  29.   }
  31.   // 数组创建一个链表
  32.   public static Node createLinkedLNode(int[] array) {
  33.     // 创建一个根节点
  34.     Node root = null;
  35.     // 从末尾元素开始依次创建Node节点
  36.     for (int i = array.length - 1; i >= 0; i--) {
  37.       Node node = new Node(array[i], null);
  38.       // 创建两个节点的连接关系
  39.       if (root != null) {
  40.         node.setNext(root);
  41.         root = node;
  42.       } else {
  43.         root = node;
  44.       }
  45.     }
  46.     return root;
  47.   }
  50.   public static void main(String[] args) {
  51.     testCaseA();
  52.     testCaseB();
  53.     testCaseC();
  54.   }
  56.   // 无环
  57.   public static void testCaseA() {
  58.     int[] array1 = {9, 2, 4, 5, 6, 8, 0, 3, 10};
  59.     Node root1 = createLinkedLNode(array1);
  60.     boolean result = hasCircle(root1);
  61.     System.out.println("caseA has circle: " + result);
  62.   }
  64.   // 有环： 案例1
  65.   public static void testCaseB() {
  66.     Node node0 = new Node();
  67.     node0.setContent(10);
  69.     Node node1 = new Node(3, node0);
  70.     Node node2 = new Node(0, node1);
  71.     Node node3 = new Node(8, node2);
  72.     Node node4 = new Node(6, node3);
  73.     Node node5 = new Node(5, node4);
  74.     Node node6 = new Node(4, node5);
  75.     Node node7 = new Node(2, node6);
  76.     Node node8 = new Node(9, node7);
  78.     node0.setNext(node8);
  80.     boolean result = hasCircle(node8);
  81.     System.out.println("caseB has circle: " + result);
  82.   }
  84.   // 有环： 案例2
  85.   public static void testCaseC() {
  86.     Node node0 = new Node();
  87.     node0.setContent(4);
  88.     Node node1 = new Node(10, node0);
  89.     Node node2 = new Node(3, node1);
  90.     Node node3 = new Node(0, node2);
  91.     Node node4 = new Node(8, node3);
  92.     Node node5 = new Node(6, node4);
  93.     Node node6 = new Node(5, node5);
  94.     node0.setNext(node6);
  96.     Node node7 = new Node(2, node0);
  97.     Node node8 = new Node(9, node7);
  99.     node0.setNext(node8);
  101.     boolean result = hasCircle(node8);
  102.     System.out.println("caseC has circle: " + result);
  103.   }
  104. }

双向链表

链表 - 图14

特点

  1. 对于每个节点，有三部分组成，prev（指向前一个节点），next（指向下一个节点），content（节点内容）

  2. 对于双向链表，为了方便遍历，我们需要同时保留第一个和最后一个节点。

    LinkedList

    阅读LinkedList.java的源码，发现实际上就是利用双向链表实现的。

    1. public class LinkedList<E>
    2.  extends AbstractSequentialList<E>
    3.  implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    4. {
    5.  transient int size = 0;
    7.  /**
    8.   * Pointer to first node.
    9.   * Invariant: (first == null && last == null) ||
    10.   *            (first.prev == null && first.item != null)
    11.   */
    12.  transient Node<E> first;
    14.  /**
    15.   * Pointer to last node.
    16.   * Invariant: (first == null && last == null) ||
    17.   *            (last.next == null && last.item != null)
    18.   */
    19.  transient Node<E> last;
    21.  /**
    22.   * Constructs an empty list.
    23.   */
    24.  public LinkedList() {
    25.  }
    27.  ......
    28. }