链表设计与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> {
    E item;
    Node<E> next;
    public Node(E item, Node<E> 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> {
    // 指向节点的真实存储的数据
    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 <E> 泛型，表示容器当中存储数据的数据类型
 */
public class MyLinkedList<E> {

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

  • 为了符合设计模式，让我们的代码更加清晰和容易维护，我们可以设计一个接口（为了避免复杂的接口信息我们就用一个统一的接口表示）表示我们要实现的功能，其代码如下：

    public interface MyCollection<E> {

  /**
   * 往链表尾部加入一个数据
   * @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<E> first;

  // 表示链表当中最后一个节点
  private Node<E> last;
  • 往链表尾部加入一个节点 
  @Override
  public boolean append(E o) {
    final Node<E> l = last;
    // 新增的节点需要将 prev 指向上一个节点，上一个节点就是链表的 last 节点
    // 新增节点的下一个节点就 null
    final Node<E> newNode = new Node<>(o, last, null);
    last = newNode;
    if (first == null) {
      // 如果链表当中还没有节点，就将其作为第一个节点
      first = newNode;
    }else {
      // 如果链表当中已经有节点，需要将新增的节点连接到链表的尾部
      l.next = newNode;
    }
    size++;
    return true;
  }
  • 根据下标找到链表当中对应下标的节点 
  /**
   * 根据下标找节点
   * @param index
   * @return
   */
   Node<E> findNodeByIndex(int index) {
     if (index >= size)
       throw new RuntimeException("输入 index 不合法链表中的数据个数为 " + size);
    Node<E> x;
    // 首先看看 index 和 size / 2 的关系
    // 这里主要是看链表的首和尾部谁距离 index 位置近，那头近就从哪头遍历
    // size >> 1 == size / 2
    if (index < (size >> 1)) {
      x = first;
      for (int i = 0; i < index; i++)
        x = x.next;
    } else {
      x = last;
      for (int i = size - 1; i > index; i--)
        x = x.prev;
    }
    return x;
  }
  • 在链表当中删除某个节点 
  void removeNode(Node<E> 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<E> node = findNodeByIndex(index);
    // 删除节点
    removeNode(node);
    size--;
    return true;
  }
  • toString方法重写 
  @Override
  public String toString() {

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

    StringBuilder builder = new StringBuilder();
    builder.append("[");
    Node<E> 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<Integer> 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 <E> 泛型，表示容器当中存储数据的数据类型
 */
public class MyLinkedList<E> implements MyCollection<E> {

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

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

  // 表示链表当中最后一个节点
  private Node<E> last;

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

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

  /**
   * 在节点数据 node 之后插入数据 o
   * @param node
   * @param o
   */
  void insertAfterNode(Node<E> node, E o) {
    if (node == null)
      throw new NullPointerException();
    // newNode 前面的节点为 node 后面的节点是 node.next
    Node<E> 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<E> node, E o) {
    if (node == null)
      throw new NullPointerException();
    // newNode 前面你的节点为 node.prev 后面的节点为 node
    Node<E> 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<E> findNodeByIndex(int index) {
     if (index >= size)
       throw new RuntimeException("输入 index 不合法链表中的数据个数为 " + size);
    Node<E> x;
    // 首先看看 index 和 size / 2 的关系
    // 这里主要是看链表的首和尾部谁距离 index 位置近，那头近就从哪头遍历
    // size >> 1 == size / 2
    if (index < (size >> 1)) {
      x = first;
      for (int i = 0; i < index; i++)
        x = x.next;
    } else {
      x = last;
      for (int i = size - 1; i > index; i--)
        x = x.prev;
    }
    return x;
  }

  void removeNode(Node<E> 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<E> 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<E> node = findNodeByIndex(index);
    // 删除节点
    removeNode(node);
    size--;
    return true;
  }

  @Override
  public boolean append(E o) {
    final Node<E> l = last;
    // 新增的节点需要将 prev 指向上一个节点，上一个节点就是链表的 last 节点
    // 新增节点的下一个节点就 null
    final Node<E> 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<E> start = first;
     while (start != null) {
       if (start.item.equals(o))
         return true;
       start = start.next;
     }
    return false;
  }

  private static class Node<E> {
    // 指向节点的真实存储的数据
    E item;
    // 前向指针：指向前一个数据
    Node<E> prev;
    // 后向指针：指向后一个数据
    Node<E> next;
    public Node(E item, Node<E> prev, Node<E> 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<E> 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<Integer> 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，我们下期再见！！！

#双向链表##Java集合#
全部评论
很有用，学到了
点赞 回复 分享
发布于 2022-08-11 11:31

相关推荐

11-23 23:34
旷视_运营_HR
旷视11月缺人岗位
11月这两个岗位比较缺人，大家还没投的继续试试！大模型产品经理（北京）职位描述：1.负责大模型ToB业务的规划设计，包括ToB产品的设计迭代以及关键项目的落地；2.根据落地场景把控大模型优化方向，设计大模型产品效果评估指标体系，参与产品的评估、验收相关工作；3.与基座模型、研发、设计、销售团队紧密合作，高效协同各方资源，保证项目高质量交付；4.关注行业及竞品最新动态，输出市场调研与分析，为产品优化提供有效建议。职位要求：1.&nbsp;计算机相关专业本科及以上学历；2.有责任心和owner意识，有优秀的沟通和协调能力；3.具备优秀的自学能力和独立思考能力，善于思考和表达自己的想法，具备良好的团队合作精神...
投递旷视等公司10个岗位 >
点赞 评论 收藏
分享
11-22 22:26
门头沟学院 前端工程师
糕手的秋招总结
没人规定0offer就不能写秋招总结吧？😡写出我的经历，让你们看看我至今还是0offer糕手，都做对了些什么🤡🤡🤡糕手思维比较发散，所以写帖子一般废话多了点我尽量来点干货（话说今天恰华莱士给我干窜了。。。）前排提醒，小白向的，您都拿大厂offer或者就是前端大师，糕手可不敢在您面前造次啊🤡🤡🤡1.运气非常重要，如果你做到了这一条，剩下的都是狗屁，没啥要看的了2.简历还是简点好，缩成一页已经是老生常谈了，除非你四五段实习吧。就拿前端举例子，不太建议写TS。刚开始的小白思维都这样，我新学会个技术栈，那一定要写上，证明我的牛x都这么过来的，都懂我从始至终都不太喜欢TS，你可以...
码农烧烤启动：喜欢糕手
点赞 评论 收藏
分享
10-30 23:23
已编辑
中山大学 Web前端
奇怪的字节hr
红温了，啥意思，要挂就给个感谢信吧，不明不白的…
去B座二楼砸水泥地：这无论是个人素质还是专业素质都👇拉满了吧
点赞 评论 收藏
分享
09-26 12:42
重庆理工大学 汽车设计
点赞 评论 收藏
分享
11-19 12:12
北京理工大学 管理培训生
点赞 评论 收藏
分享
4 3 评论
分享

招聘动态

查看更多

字节跳动

2025校园招聘

阿里云管培生

2025届校园招聘

快手Star

2025届招聘

快手

销售类投递专区

全站热榜

正在热议
# 25届秋招总结 #
297587次浏览 2618人参与
# 美团求职进展汇总 #
1326248次浏览 12438人参与
# 北方华创开奖 #
26279次浏览 282人参与
# 地方国企笔面经互助 #
3713次浏览 9人参与
# 如果不工作真的会快乐吗 #
58788次浏览 510人参与
# 选完offer后，你后悔学本专业吗 #
19477次浏览 142人参与
# 阿里云管培生offer #
16401次浏览 292人参与
# 国央企薪资爆料 #
7759次浏览 55人参与
# 如何一边实习一边秋招 #
991456次浏览 12635人参与
# 提前批简历挂麻了怎么办 #
146293次浏览 1944人参与
# 学历or实习经历，哪个更重要 #
50693次浏览 399人参与
# 海康威视求职进展汇总 #
398570次浏览 3405人参与
# 正在实习的你，几点下班 #
51488次浏览 383人参与
# 米哈游求职进展汇总 #
175689次浏览 1458人参与
# 投递实习岗位前的准备 #
1178689次浏览 18389人参与
# 面试体验感最好的是哪家？ #
84981次浏览 845人参与
# 实习生应该准时下班吗 #
167324次浏览 1159人参与
# 得物求职进展汇总 #
66099次浏览 681人参与
# 求职遇到的搞笑事件 #
70565次浏览 575人参与
# 网申一定要掌握的小技巧 #
5300次浏览 53人参与
# 0offer是寒冬太冷还是我太菜 #
897563次浏览 8007人参与
# 腾讯求职进展汇总 #
195607次浏览 1639人参与
牛客网
牛客企业服务