【数据结构与算法】4、双向链表（学习 jdk 的 LinkedList 部分源码）

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】4、双向链表（学习 jdk 的 LinkedList 部分源码）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、双向链表

【数据结构与算法】4、双向链表（学习 jdk 的 LinkedList 部分源码）,数据结构与算法,java,链表,学习

🎁 单链表的节点中只有一个 next 指针引用着下一个节点的地址
🎁 当要获取单链表中的最后一个元素的时候，需要从头节点开始遍历到最后
🎁 单链表一开始的时候有 first 头指针引用着头节点的地址

💰 双向链表可以提升链表的综合性能
💰 双向链表的节点中有 prev 指针引用着上一个节点的地址，有 next 指针引用着下一个节点的地址
💰 双向链表中一开始的时候有 first 头指针引用着头节点的地址，有 last 尾指针引用着尾节点的地址
💰 ① 当需要获取双向链表靠后的节点【index >= (size / 2)】的时候从尾节点开始遍历；② 当需要获取双向链表靠前的节点【index < (size / 2)】的时候从头节点开始遍历

🎄 头节点的 prev 为 null
🎄 尾节点的 next 为 null

二、node(int index) 根据索引找节点

  /**
   * 根据索引找节点
   */
  private Node<E> node(int index) {
      rangeCheck(index);

      if (index < (index >> 1)) { // 找左边的节点
          Node<E> node = first;
          for (int i = 0; i < index; i++) {
              node = node.next;
          }
          return node;
      } else {
          Node<E> node = last;
          for (int i = size - 1; i > index; i--) {
              node = node.prev;
          }
          return node;
      }
  }

三、clear()

  @Override
  public void clear() {
      size = 0;
      first = null;
      last = null;
  }

只有被【gc root 对象】引用的对象才不会被垃圾回收器回收：

🍃 被栈指针（局部变量）引用的对象是 gc root 对象

【数据结构与算法】4、双向链表（学习 jdk 的 LinkedList 部分源码）,数据结构与算法,java,链表,学习

四、add(int, E）

【数据结构与算法】4、双向链表（学习 jdk 的 LinkedList 部分源码）,数据结构与算法,java,链表,学习

🎄 ① 当往索引 0 处插入节点的时候
🎄 ② 当往最后插入节点的时候
🎄 ③ 当一个节点都没有（插入第一个节点）的时候

【数据结构与算法】4、双向链表（学习 jdk 的 LinkedList 部分源码）,数据结构与算法,java,链表,学习

    @Override
    public void add(int index, E element) {
        rangeCheck4Add(index);

        if (size == 0 || (first == null && last == null)) { // 添加第一个节点
            // 新节点的 prev 和 next 都指向 null
            first = new Node<>(element, null, null);
            // 头指针和尾指针都指向新节点
            last = first;
        } else {
            if (index == size) { // 往最后插入新节点
                Node<E> oldLast = last;
                last = new Node<>(element, oldLast, null);
                oldLast.next = last;
            } else {
                // 找到 index 索引处的节点（该节点是新节点的下一个节点）
                Node<E> next = node(index);
                // 前一个节点（假如是往索引为 0 的位置插入节点的话, prev 是 null）
                Node<E> prev = next.prev;

                // 新节点的 prev 指向【前一个节点】
                // 新节点的 next 指向【后一个节点】
                Node<E> newNode = new Node<>(element, prev, next);

                // 后一个节点的 prev 指向新节点
                next.prev = newNode;

                /* 往索引为 0 处插入新节点 */
                if (prev == null) { // 往索引为 0 的位置插入新节点（插入新节点到头节点的位置）
                    first = newNode; // 头指针指向新节点
                } else {
                    // 前一个节点的 next 指向新节点
                    prev.next = newNode;
                }
            }
        }

        size++;
    }

【数据结构与算法】4、双向链表（学习 jdk 的 LinkedList 部分源码）,数据结构与算法,java,链表,学习

五、remove(int index)

【数据结构与算法】4、双向链表（学习 jdk 的 LinkedList 部分源码）,数据结构与算法,java,链表,学习

自己写的代码（测试成功的）：

    @Override
    public E remove(int index) {
        rangeCheck(index);

        // 拿到 index 位置的节点
        Node<E> oldNode = node(index);

        if (index == 0) { // 删除头节点
            // 拿到头节点
            first = oldNode.next;
            first.prev = null;
        } else {
            oldNode.prev.next = oldNode.next;

            if (oldNode.next == null) { // 删除尾节点
                last = oldNode.prev;
            } else {
                oldNode.next.prev = oldNode.prev;
            }
        }

        size--;

        return oldNode.element;
    }

老师的代码：

    @Override
    public E remove(int index) {
        rangeCheck(index);

        Node<E> node = node(index);
        Node<E> prev = node.prev;
        Node<E> next = node.next;

        if (prev == null) { // 删除头节点
            first = next;
        } else {
            prev.next = next;
        }


        if (next == null) { // 删除尾节点
            last = prev;
        } else {
            next.prev = prev;
        }

        size--;

        return node.element;
    }