java LinkedList源码阅读记录

浅浅的花香味﹌ 2022-06-17 09:42 178阅读 0赞

ps:环境说明，**这是jdk1.8的源码** ，1.8中并没有采用循环双链表的形式了，只是采用了双链表的数据结构

1.  LinkedList  
    1.1 构造方法(不同于1.6的循环链表)以及结点格式  
    无参构造方法并没有采取任何措施和这里

public LinkedList() {
        }
        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }
        public boolean addAll(Collection<? extends E> c) {
            //size表示当前元素的大小
            return addAll(size, c);
        }

private static class Node<E> {
            E item;
            Node<E> next;   //后一节点
            Node<E> prev;   //前一结点
    
            Node(Node<E> prev, E element, Node<E> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

1.2 添加add()

add(E e)此方法默认添加到链表尾部

/** * 添加元素E作为最后一个元素 */
     public boolean add(E e) {
            linkLast(e);
            return true;
        }

void linkLast(E e) {
            //获取最后一个元素
            final Node<E> l = last;
            //新建结点 newNode 将l作为前驱结点
            final Node<E> newNode = new Node<>(l, e, null);
            //更新最后一个结点为last
            last = newNode;
            /** *第一个if(l==null)适用于以下这种情况 *此处由于初次添加的时候first和last都为空，添加第一个结点时： *l为之前保存的last为空 last更新为newnode *而first为空，所以first为新结点， */
            if (l == null)
                first = newNode;  
            else
                l.next = newNode;
            size++;
            modCount++;
        }
        //此处构造方法 LinkedList(Collection<? extends E> c)调用了该方法
        public boolean addAll(int index, Collection<? extends E> c) {
            //检查是否越界
            checkPositionIndex(index);
            //转换为对象
            Object[] a = c.toArray();
            int numNew = a.length;
            //进行长度判断若为零则直接返回false
            if (numNew == 0)
                return false;
    
            Node<E> pred, succ;
            //获得插入处结点和插入处前一结点的信息
            if (index == size) {  //从尾部插入
                succ = null;
                pred = last;
            } else { //从中间插入，并采用折半查找，查找index所在结点，请看1.3查找
                succ = node(index);
                pred = succ.prev;
            }
             //进行插入
            for (Object o : a) {
                @SuppressWarnings("unchecked") E e = (E) o;
                Node<E> newNode = new Node<>(pred, e, null);
                if (pred == null)  //头插入
                    first = newNode;
                else
                    pred.next = newNode;
                pred = newNode;
            }
    
            if (succ == null) {
       //尾部插入时
                last = pred;
            } else {  //中间插入 
                pred.next = succ;  //将pre指向succ 将链表顺向链接起来
                succ.prev = pred;  //同时设置succ的前一节点指向pred 将链表反向链接起来
            }
    
            size += numNew;
            modCount++;
            return true;
        }

其他的add方法都大同小异了

1.3 查找

public E get(int index) {
         checkElementIndex(index);
         return node(index).item;
     }
    //此处采用了折半查找
    Node<E> node(int index) {
          // assert isElementIndex(index);
          //当查找位置小于一半（size>>1等同于size/2）时,从头开始查找，否则从尾部进行查找
          if (index < (size >> 1)) {
              Node<E> x = first;
              for (int i = 0; i < index; i++)
                  x = x.next;
              return x;
          } else {
              Node<E> x = last;
              for (int i = size - 1; i > index; i--)
                  x = x.prev;
              return x;
          }
     }

1.4删除  
remove()此方法默认从头开始删除

public E remove() {
         return removeFirst();
     }
     public E removeFirst() {
         final Node<E> f = first;
         if (f == null)
             throw new NoSuchElementException();
         return unlinkFirst(f);
     }
     private E unlinkFirst(Node<E> f) {
            // 此处 f == first && f != null;
            final E element = f.item;
            final Node<E> next = f.next;
            f.item = null;
            f.next = null; // 有利于gc
            first = next;
            if (next == null)
                last = null;
            else
                next.prev = null;
            size--;
            modCount++;
            return element;
        }

remove(int index) 移除index处的结点

public E remove(int index) {
            checkElementIndex(index);
            //再次折半查找找到index处结点
            return unlink(node(index));
     }

E unlink(Node<E> x) {
            // assert x != null;
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;
            //此处解决删除点x的前结点问题
            if (prev == null) {  //此处说明该结点时头结点
                first = next;  
            } else {
                prev.next = next;  //prev 指向x的下一个,跳过x达到删除目的
                x.prev = null;     //x.prev与prev断开联系
            }
            //此处解决删除点x的后结点问题
            if (next == null) {    //说明该结点时尾节点
                last = prev;       //last向前移
            } else {
                next.prev = prev;  //将x的后一个结点指向x的前一个
                x.next = null;     //x.prev与prev断开联系
            }
    
            x.item = null;
            size--;
            modCount++;
            return element;
        }

2.总结  
发现全是数据结构的知识，还是再去看看数据结构吧，逃！