add

    public boolean add(E e) {
        // 采用尾插
        linkLast(e); // 见目录的Link部分
        return true;
    }

   public void add(int index, E element) { // 在中间添加元素
        checkPositionIndex(index);

        if (index == size) // 这里设计也很巧妙 ,如果是last的后一个,直接调用尾插
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

remove

    public boolean remove(Object o) {       // 这里就不讲了,太简单了
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

set

    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index); // 获取指定位置的元素
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

node()会找一个离索引最近的位置开始遍历,决定从前往后还是从后往前

    Node<E> node(int index) {  // 获取指定索引位置的节点
        // assert isElementIndex(index);

        if (index < (size >> 1)) { // index< size÷2    根据index判断它在前一半还是后一半
            Node<E> x = first; // 暂时保存头结点
            for (int i = 0; i < index; i++)  // 还有一个要注意的是 i<index 而不是 小于等于
                x = x.next; // 因为是链表,不断根据i获取下一个节点, 没有对原来的节点造成更改, 只是保存到这个位置时候下一个元素
            return x;
        } else {
            Node<E> x = last; // 从后往前遍历, 暂时保存尾部节点
            for (int i = size - 1; i > index; i--) // 在后半段,往前遍历
                x = x.prev; // 不断获取前一个节点,一点一点往前爬
            return x;
        }
    }

addAll

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }


    public boolean addAll(int index, Collection<? extends E> c) { // 在指定位置插入
        checkPositionIndex(index); // 索引越界检查

        Object[] a = c.toArray();
        int numNew = a.length; // 获取长度
        if (numNew == 0)  // 如果要添加的c集合的长度为0. , 直接返回false
            return false;

        Node<E> pred, succ; /*下面这段代码意思呢,就是判断插入的第一个位置的元素是什么和最后一个元素是什么,这里很巧!*/ // 这里是创建了两个节点, pred指向其前一个节点, succ指向当前要插入节点的位置,;  这里的写法类似于Integer a, b;
        if (index == size) { // 这里的size是指链表的长度, 当插入位置为链表尾部
            succ = null; // 要插入位置为null,就像链表 1->2->3  要在3后面插入, 3的后面就是succ 等于null
            pred = last; // 前一个节点等于last
        } else { // 若不是尾部插入,
            succ = node(index); // node():查询指定索引未知的元素,这个方法写的很巧妙,里面根据索引位置决定从头查询还是从尾部查询
            pred = succ.prev; // 获取之前土著元素的前一个节点
        }

        for (Object o : a) { // 遍历要添加进来的集合a
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null); // ??, 新建next为null, pre为土著元素前一个节点的节点,这里么有吧next链接起来,为了简单,这里把pred <=> e双向链接起来
            if (pred == null) // 如果是头结点
                first = newNode; // first赋值为新的头结点
            else // 如果不是头结点
                pred.next = newNode; //    前一个节点的下一个指向新的node
            pred = newNode;     // 一直往下遍历,保证了 pred始终是前一个,newNode是新欢
        }                       /* 情况一:上面的代码执行完之后,画图可以发现之前的元素都连接起来了,尾结点为null的情况也连接起来了,但是还差了一种情况,就是普通的时候,最后插入的元素的next没有指向下一个*/

        if (succ == null) {
            last = pred;           // 如果之前是在结尾插入,那尾结点就是插入的最后的元素
        } else {
            pred.next = succ;       // 这里就是来补足情况一的,将最后一公里问题解决,把双向链表链接完整
            succ.prev = pred;
        }

        size += numNew;             // 这代码虽然变量命名很蛋疼,但是。woc写的真好!
        modCount++;
        return true;
    }

peek pool

peek和poll区别: peek只获取不删除,poll获取后删除,peek获取没有返回null
poll获取没有,报错NoSuchElementException

    /**
     * Retrieves, but does not remove, the first element of this list, // peek和poll区别: peek只获取不删除,poll获取后删除,peek获取没有返回null
     * or returns {@code null} if this list is empty.                  // poll获取没有,报错NoSuchElementException
     *
     * @return the first element of this list, or {@code null}
     *         if this list is empty
     * @since 1.6
     */
    public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

push & pop

    public void push(E e) { // 在这个列表头部插入元素
        addFirst(e);
    }

    public E pop() {  // 弹出列表中的第一个元素
        return removeFirst();
    }
    public void addFirst(E e) {
        linkFirst(e);
    }
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

Link

  /**
     * Links e as first element.  头部添加元素
     */
    private void linkFirst(E e) {
        final Node<E> f = first; // 暂时保存头节点, 因为后期首节点就不是原来的那个了, 只是美其名曰f是首节点备份,其实他只代表了原来的头结点的位置
        final Node<E> newNode = new Node<>(null, e, f); // 创建新节点,新节点的next是首节点
        first = newNode; // 新创建的节点当成首节点
        if (f == null)
            last = newNode; // last = firset= newNode,
        else
            f.prev = newNode;  // 原来有元素的情况下f的pre要记得链接起来
        size++; // 元素个数加一
        modCount++; // 修改次数加一
    }

    /**
     * Links e as last element.
     */
    void linkLast(E e) { // 尾部添加元素
        final Node<E> l = last; // 暂时保存尾部节点
        final Node<E> newNode = new Node<>(l, e, null); // 新建node节点,让它的next=null, 他的pre=之前的尾部节点
        last = newNode; // 新的节点当选尾部节点
        if (l == null) // 如果原来没有元素
            first = newNode; // last = firset= newNode
        else
            l.next = newNode; // 原来尾部的next由null指向新建立的节点newNode
        size++;
        modCount++;
    }

    /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) { // 在尾部之外位置插入 注意这里的succ是待添加位置的土著元素, 是在succ位置之前添加元素
        // assert succ != null;          //                                     1->2->3 succ:2
        final Node<E> pred = succ.prev; // 暂时保存原有土著居民元素的上一个节点  下一行:1->2->3         :1<-new->2(succ)
        final Node<E> newNode = new Node<>(pred, e, succ); // 新建一个节点,他的上一个节点等于原来土著节点的上一个节点,
        succ.prev = newNode; // 将原有土著元素的pre指向当前新建节点
        if (pred == null) // 如果原有元素是头节点
            first = newNode; // 把 first指向新的newNode
        else // 如果不是头结点, 就可以浪了
            pred.next = newNode; // 将pred的next指向newNode
        size++;
        modCount++;
    }

unlink

unlinklast和unlinkfirst太像了,不赘述了哈

    /**
     * Unlinks non-null first node f.
     */
    private E unlinkFirst(Node<E> f) { // 去掉第一个非空的元素
        // assert f == first && f != null;
        final E element = f.item;   // 获取到那个元素
        final Node<E> next = f.next;    // 获取他的下一个元素,并保存
        f.item = null;                  // 本身置空
        f.next = null; // help GC       // 把要拿走的这个元素的下一个节点置空,(帮助gc,其实不是很必要,但jdk将性能优化到极致,来减少一条没用的引用)
        first = next;                   // 将首节点  =  next
        if (next == null)               // next为空说明原来位移除时候只有一个元素
            last = null;
        else
            next.prev = null;           // 移除了首节点,后来的首节点就是next, 他的前一个就是null
        size--;
        modCount++;
        return element;
    }
   /**
     * Unlinks non-null node x.
     */
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;       // 获取要移除的元素, 并保存他的前一个节点a,后一个节点b
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {             // 如果前一个为空,说明是首节点,那么新的头结点就是b
            first = next;
        } else {
            prev.next = next;
            x.prev = null;              // 帮助gc鸭,小笨蛋
        }

        if (next == null) {             // 这里避免了空指针,和if (prev == null) { 一样,先判断,再改指向
            last = prev;                // 如果下一个为空,说明你这小子把尾结点干掉了啊,辣么,尾结点就变成了a了
        } else {
            next.prev = prev;           // 这一步是关键的,将双向链表前后连接起来
            x.next = null;              // 要不怎么说jdk源码写的好,gc都帮你处理了
        }

        x.item = null;                  // 真的 好,我之前自己手撕双向链表就没有考虑到这
        size--;
        modCount++;
        return element;
    }


1 条评论

dentist liverpool · 2024-01-22 05:45

Hey! Someone in my Fɑcebook group shared this webssite with
us so I camee to give it a look. I’m ԁefinitely enjoying tһe information. I’m boоkmarking and
wiⅼl be tweeting this to my followers! Fantɑstіc blog and brilⅼiant design аnd style.

评论已关闭。

站点统计

  • 文章总数:314 篇
  • 分类总数:19 个
  • 标签总数:193 个
  • 运行天数:1111 天
  • 访问总数:287110 人次

浙公网安备33011302000604

辽ICP备20003309号