深入解析数据结构：链表的设计与Java手动实现LinkedList详细教程

链表设计与实现

在谈链表之前，咱们先谈谈咱们平时编程会遇到的很常见的一个问题。如果在编程的时候，某个变量在后续编程中仍需应用，咱们能够用一个局部变量来保留该值，除此之外一个更加罕用的办法就是应用容器了。

那什么是容器呢？从字面上来说就是用来装某个货色的，比方咱们的杯子，就是容器。在程序设计当中咱们最常见的容器就是数组了，他能够存咱们想保留的货色。在编程当中咱们最常见的容器如下：

• 在Python当中有列表、字典、元组、汇合等等。
• 在Java当中常见的容器有 ArrayList、LinkedList、HashMap、HashSet等等。
• 在C++当中有vector、list、unordered_map、unordered_set等等。

明天要谈到的链表在Java的LinkedList和C++的list当中就有应用到。

那什么是链表呢？链表是由一个一个的节点组成的，每个节点蕴含两个字段，其中一个字段data示意实在须要示意的数据，另外一个字段next示意指向下一个节点的指针（如果不理解指针也没有关系，就将其当做一个一般的变量既可，不影响咱们的了解），data和next两者一起组成链表当中的节点(Node)。

其中data示意链表当中存储的实在的数据，而next示意指向下一个节点的指针（如果不理解指针也没有关系，就将其当做一个一般的变量既可，不影响咱们的了解），data和next两者一起组成链表当中的节点(Node)。

Java代码：

class Node {
    E item;
    Node next;
    public Node(E item, Node next) {
      this.item = item;
      this.next = next;
    }
  }

单链表

所谓单链表就是只有一个指向其余节点的变量，比方下图当中只有一个next变量指向其余同样的节点。

双向链表

双向链表和单链表的区别就是他的指向有两个方向，而单链表只有一个方向，在双向链表的节点当中会有两个指向其余同样节点的变量，一个指向前一个节点，一个指向后一个节点，对应下图prev指向前一个节点，next指向后一个节点。

循环链表

这个概念也比较简单，就是链表首尾相连，造成一个环，比方单循环链表：

双向循环链表，第一个节点（头结点）的prev指向最初一个节点（尾节点），尾节点的next指向头结点：

动态链表

咱们后面所提到的链表中的节点除了数据域（data）还有一个变量指向其余的节点，节点与节点之间的内存地址是不间断的，而动态链表和后面提到的链表不一样，它是应用数组来实现链表，只是将next变成一个int类型的数据，示意下一跳数据的下标，比方下图当中所示意的那样（其中-1示意链表的结尾，因为next域存储的是下一个节点的下标，下标必定大于等于0，因而能够应用-1示意链表的结尾）：

在上图当中对应的链表如下（通过剖析上图当中next域的指向剖析失去下图）：

像这种应用数组实现的链表叫做动态链表，下面谈到的就是动态单链表，它对应的数据结构也很分明：

private static class StaticNode {
    // 指向节点的实在存储的数据
    E item;
    // 指向下一个节点的下标
    int next;

    public StaticNode(E item, int next) {
      this.item = item;
      this.next = next;
    }
  }

为什么须要链表？

答复这个问题之前，首先须要搞清楚咱们面临什么样的需要：

• 咱们须要有一个容器能够保留咱们的数据
• 咱们的数据有肯定的程序性，比方咱们当初容器当中的数据个数是10个，咱们想在下标为3的中央插入一个数据

​ 在数组长度够的状况下，咱们须要将下标2之后的数据往后搬一个地位而后将新的数据放到下标为3的地位，这种插入的工夫复杂度为 O(n)，至于为什么是O(n)咱们在谈ArrayList时咱们再进行证实。

• 然而如果咱们采纳的是链表的办法的话，咱们的工夫复杂度能够做到O(1)。

​ 对于下面这种插入状况，咱们只须要略微扭转一下next的指向就能够了：

• 如果咱们须要在数组当中删除一个元素，同样的原理，因为某个数据被删除之后它所在的那个地位就空了，因而须要将后续的数据往前搬一个地位：

  比方咱们须要删除下标为三的数据：

然而如果咱们应用的是链表的话咱们也只须要简略挪动链表即可，比方要删除节点N，只须要将节点N的上一个节点的next指向节点N的下一个节点即可，同时将节点N的next设置为空。

​ 因为咱们在操作的时候只须要调整一下next指针的指向即可，这个操作的工夫复杂度是常数级别的，因而工夫复杂度为O(1)。

​ 依据下面所谈到的内容，能够发现链表在这种须要频繁插入和删除的场景很适宜。

Java代码实现双向链表

需要剖析

在正式实现双向链表之前咱们首先剖析一下咱们的需要：

• 须要有一个办法判断链表外面是否有数据，也就是链表是否为空。
• 须要有一个办法判断链表外面是否蕴含某个数据，这个蕴含的意思示意是否存在一个数据和以后的数据一样，并不是内存地址统一，相当于Java当中的equals办法。
• 须要有一个办法往链表当中增加数据
• 须要有一个办法往链表当中删除数据

咱们的需要次要就是下面这些了，当然也能够减少一些其余的办法，比如说减少将链表变成数组的办法等等，为了简略咱们只实现上述性能。

具体实现

• 定义节点的数据结构

  依据后面的剖析咱们很容易能够设计出链表当中节点的构造，其代码如下所示：

  /**
   * 本人实现链表
   * @param  泛型，示意容器当中存储数据的数据类型
   */
  public class MyLinkedList {
  
    private static class Node {
      // 指向节点的实在存储的数据
      E item;
      // 前向指针：指向前一个数据
      Node prev;
      // 后向指针：指向后一个数据
      Node next;
      public Node(E item, Node prev, Node next) {
        this.item = item;
        this.prev = prev;
        this.next = next;
      }
    }
  }

• 为了合乎设计模式，让咱们的代码更加清晰和容易保护，咱们能够设计一个接口（为了防止简单的接口信息咱们就用一个对立的接口示意）示意咱们要实现的性能，其代码如下：

  public interface MyCollection {
  
    /**
     * 往链表尾部退出一个数据
     * @param o 退出到链表当中的数据
     * @return
     */
    boolean add(E o);
  
    /**
     * 示意在第 index 地位插入数据 o
     * @param index
     * @param o
     * @return
     */
    boolean add(int index, E o);
  
    /**
     * 从链表当中删除数据 o
     * @param o
     * @return
     */
    boolean remove(E o);
  
    /**
     * 从链表当中删除第 index 个数据
     * @param index
     * @return
     */
    boolean remove(int index);
    
    /**
     * 往链表尾部退出一个数据，性能和 add 一样
     * @param o
     * @return
     */
    boolean append(E o);
  
    /**
     * 返回链表当中数据的个数
     * @return
     */
    int size();
  
    /**
     * 示意链表是否为空
     * @return
     */
    boolean isEmpty();
  
    /**
     * 示意链表当中是否蕴含数据 o
     * @param o
     * @return
     */
    boolean contain(E o);
  }

• 链表当中应该有哪些变量?首先咱们必定须要晓得链表当中有多少数据，其次因为咱们是双向链表，须要可能从头或者从尾部进行链表的遍历，因而很天然咱们须要变量指向链表当中的第一个节点和最初一个节点。

  // 示意链表当中数据的个数
  private int size;

  // 链表当中第一个节点
  private Node first;

  // 示意链表当中最初一个节点
  private Node last;

• 往链表尾部退出一个节点

  @Override
  public boolean append(E o) {
    final Node l = last;
    // 新增的节点须要将 prev 指向上一个节点，上一个节点就是链表的 last 节点
    // 新增节点的下一个节点就 null
    final Node newNode = new Node<>(o, last, null);
    last = newNode;
    if (first == null) {
      // 如果链表当中还没有节点，就将其作为第一个节点
      first = newNode;
    }else {
      // 如果链表当中曾经有节点，须要将新增的节点连贯到链表的尾部
      l.next = newNode;
    }
    size++;
    return true;
  }

• 依据下标找到链表当中对应下标的节点

  /**
   * 依据下标找节点
   * @param index
   * @return
   */
   Node findNodeByIndex(int index) {
     if (index >= size)
       throw new RuntimeException("输出 index 不非法链表中的数据个数为 " + size);
    Node x;
    // 首先看看 index 和 size / 2 的关系
    // 这里次要是看链表的首和尾部谁间隔 index 地位近，那头近就从哪头遍历
    // size >> 1 == size / 2
    if (index <(size >> 1)) {
      x = first;
      for (int i = 0; i  index; i--)
        x = x.prev;
    }
    return x;
  }

• 在链表当中删除某个节点

  void removeNode(Node node) {
     if (node == null)
       throw new NullPointerException();
     if (node.prev != null)
       node.prev.next = node.next;
     if (node.next != null)
       node.next.prev = node.prev;
  }

  /**
   * 依据下标删除某个节点
   * @param index
   * @return
   */
  @Override
  public boolean remove(int index) {
    // 首先找到第 index 个数据对应的节点
    Node node = findNodeByIndex(index);
    // 删除节点
    removeNode(node);
    size--;
    return true;
  }

• toString办法重写

  @Override
  public String toString() {

     if (first == null)
       return "[]";

    StringBuilder builder = new StringBuilder();
    builder.append("[");
    Node start = first;
    builder.append(start.item.toString());
    start = start.next;
    while (start != null) {
      builder.append(", ").append(start.item.toString());
      start = start.next;
    }
    builder.append("]");
    return builder.toString();
  }

• 测试代码

  public static void main(String[] args) {
    MyLinkedList list = new MyLinkedList<>();
    System.out.println(list.contain(100));
    for (int i = 0; i <10; i++) {
      list.add(i);
    }
    list.add(0, -9999);
    System.out.println(list.size() / 2);
    list.add(5, 9999);
    list.append(Integer.MAX_VALUE);
    System.out.println(list);

    list.remove(5);
    list.add(6, 6666);
    System.out.println(list);
    System.out.println(list.contain(6666));
  }

输入

false
5
[-9999, 0, 1, 2, 3, 9999, 4, 5, 6, 7, 8, 9, 2147483647]
[-9999, 0, 1, 2, 3, 4, 6666, 5, 6, 7, 8, 9, 2147483647]
true

双向链表实现残缺代码：

/**
 * 本人实现链表
 * @param  泛型，示意容器当中存储数据的数据类型
 */
public class MyLinkedList implements MyCollection {

  // 示意链表当中数据的个数
  private int size = 0;

  // 链表当中第一个节点
  private Node first;

  // 示意链表当中最初一个节点
  private Node last;

  @Override
  public boolean add(E o) {
    return append(o);
  }

  @Override
  public boolean add(int index, E o) {
    Node node = findNodeByIndex(index);
    insertBeforeNode(node, o);
    size++;
    return true;
  }

  /**
   * 在节点数据 node 之后插入数据 o
   * @param node
   * @param o
   */
  void insertAfterNode(Node node, E o) {
    if (node == null)
      throw new NullPointerException();
    // newNode 后面的节点为 node 前面的节点是 node.next
    Node newNode = new Node<>(o, node, node.next);
    if (node.next != null)
      node.next.prev = newNode;
    if (node == last)
      last = newNode;
    node.next = newNode;
  }


  /**
   * 在节点 node 之前插入数据 o
   * @param node
   * @param o
   */
  void insertBeforeNode(Node node, E o) {
    if (node == null)
      throw new NullPointerException();
    // newNode 后面你的节点为 node.prev 前面的节点为 node
    Node newNode = new Node<>(o, node.prev, node);
    if (node.prev != null)
      node.prev.next = newNode;
    else
      first = newNode;
    node.prev = newNode;
  }

  /**
   * 依据下标找节点
   * @param index
   * @return
   */
   Node findNodeByIndex(int index) {
     if (index >= size)
       throw new RuntimeException("输出 index 不非法链表中的数据个数为 " + size);
    Node x;
    // 首先看看 index 和 size / 2 的关系
    // 这里次要是看链表的首和尾部谁间隔 index 地位近，那头近就从哪头遍历
    // size >> 1 == size / 2
    if (index <(size >> 1)) {
      x = first;
      for (int i = 0; i  index; i--)
        x = x.prev;
    }
    return x;
  }

  void removeNode(Node node) {
     if (node == null)
       throw new NullPointerException();
     if (node.prev != null)
       node.prev.next = node.next;
     if (node.next != null)
       node.next.prev = node.prev;
  }

  @Override
  public boolean remove(E o) {
     Node start = first;
     while (start != null) {
       if (start.item.equals(o))
         removeNode(start);
       start = start.next;
     }
     size--;
    return true;
  }

  /**
   * 依据下标删除某个节点
   * @param index
   * @return
   */
  @Override
  public boolean remove(int index) {
    // 首先找到第 index 个数据对应的节点
    Node node = findNodeByIndex(index);
    // 删除节点
    removeNode(node);
    size--;
    return true;
  }

  @Override
  public boolean append(E o) {
    final Node l = last;
    // 新增的节点须要将 prev 指向上一个节点，上一个节点就是链表的 last 节点
    // 新增节点的下一个节点就 null
    final Node newNode = new Node<>(o, last, null);
    last = newNode;
    if (first == null) {
      // 如果链表当中还没有节点，就将其作为第一个节点
      first = newNode;
    }else {
      // 如果链表当中曾经有节点，须要将新增的节点连贯到链表的尾部
      l.next = newNode;
    }
    size++;
    return true;
  }

  @Override
  public int size() {
    return size;
  }

  @Override
  public boolean isEmpty() {
    return size == 0;
  }

  @Override
  public boolean contain(E o) {
     Node start = first;
     while (start != null) {
       if (start.item.equals(o))
         return true;
       start = start.next;
     }
    return false;
  }

  private static class Node {
    // 指向节点的实在存储的数据
    E item;
    // 前向指针：指向前一个数据
    Node prev;
    // 后向指针：指向后一个数据
    Node next;
    public Node(E item, Node prev, Node next) {
      this.item = item;
      this.prev = prev;
      this.next = next;
    }
  }

  @Override
  public String toString() {

     if (first == null)
       return "[]";

    StringBuilder builder = new StringBuilder();
    builder.append("[");
    Node start = first;
    builder.append(start.item.toString());
    start = start.next;
    while (start != null) {
      builder.append(", ").append(start.item.toString());
      start = start.next;
    }
    builder.append("]");
    return builder.toString();
  }

  public static void main(String[] args) {
    MyLinkedList list = new MyLinkedList<>();
    System.out.println(list.contain(100));
    for (int i = 0; i <10; i++) {
      list.add(i);
    }
    list.add(0, -9999);
    System.out.println(list.size() / 2);
    list.add(5, 9999);
    list.append(Integer.MAX_VALUE);
    System.out.println(list);

    list.remove(5);
    list.add(6, 6666);
    System.out.println(list);
    System.out.println(list.contain(6666));
  }
}

关注公众号：一无是处的钻研僧，理解更多计算机常识

下期咱们仔细分析JDK外部LinkedList具体实现，我是LeHung，咱们下期再见！！！