LinkedList源码解析学习（jdk8）

「爱情、让人受尽委屈。」 2024-03-22 11:02 128阅读 0赞

> 今天学习了LinkedList的源码，在这里终结一下自己的学习成果。

#### LinkedList中的一些属性 ####

// transient关键字,会使属性不能序列化
    	transient int size = 0; // 链表当前长度
        /**
         * Pointer to first node.
         * Invariant: (first == null && last == null) ||
         * (first.prev == null && first.item != null)
         */
        transient Node<E> first; // 头结点,初始为null
        /**
         * Pointer to last node.
         * Invariant: (first == null && last == null) ||
         * (last.next == null && last.item != null)
         */
        // 指向最后一个结点
        transient Node<E> last; // 尾节点,初始为null

#### Node内部类 ####

private static class Node<E> {
        
            E item; // 结点元素
            Node<E> next; // 后置结点指针
            Node<E> prev; // 前置结点指针
    		// 有参构造方法,用于Node的属性的初始化
            Node(Node<E> prev, E element, Node<E> next) {
        
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

#### add方法 ####

public boolean add(E e) {
        
            linkLast(e); // 将e元素加在链表的后面
            return true; // 成功返回true
        }

##### linkLast(e)添加元素到链表后面 #####

void linkLast(E e) {
        
            final Node<E> l = last; // 尾节点赋值给l
    
            /** 创建一个e的Node节点，前置指向原last节点，后置指向null */
            final Node<E> newNode = new Node<>(l, e, null);
    
            /** 将newNode节点赋值为last节点 */
            last = newNode;
    
            // 链表刚开始的时候,first=null,last=null,如果这是加入的第一元素,那么这个元素就是头结点
            if (l == null) {
        
                /** 如果是第一个添加的元素，则first指针指向该结点*/
                first = newNode; // eg1: first指向newNode
            } else {
        
                /** 如果不是第一个添加进来的元素，则更新l的后置结点指向新添加的元素结点newNode*/
                l.next = newNode; 
            }
            size++; // 元素个数加一
            modCount++;
        }

> 这个add方法还是挺简单的

#### get方法解析 ####

// index需要查询的下标
    	public E get(int index) {
        
    		// 判断下标是否越界
            checkElementIndex(index);
            // 查询操作
            return node(index).item;
        }

##### checkElementIndex(index); #####

private void checkElementIndex(int index) {
        
            /** index >= 0 && index < size */
            if (!isElementIndex(index)) {
         // 越界则抛出异常
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
            }
        }
    	// 判断是否越界
    	private boolean isElementIndex(int index) {
        
    		// 查询的下标要大于等于0,并且小于元素个数
            return index >= 0 && index < size;
        }

##### node(index); 查询出对应的下标的元素,因为这是链表,所以只能遍历查找，这个查找的思想还是挺巧妙的，先把链表分为两半，判断你这个下标在哪一部分，前半部分便从头结点遍历，后半部分便从尾节点开始遍历，这样可以很好的提高效率。 #####

Node<E> node(int index) {
        
            // assert isElementIndex(index);
    
            /** 如果需要获取的index小于总长度size的一半，则从头部开始向后遍历查找 */
            // size >> 1 表示又移一位,相当于除以2,判断这个元素在前半端还是后半段
            if (index < (size >> 1)) {
        
                Node<E> x = first; // 头结点
                for (int i = 0; i < index; i++) {
         
                    x = x.next; // 从first结点向后next查找，直到index下标node，返回node
                }
                return x;
            } else {
         /** 从尾部开始向前遍历查找 */
                Node<E> x = last;
                for (int i = size - 1; i > index; i--) {
        
                    x = x.prev; // 从last结点向前prev查找，直到index下标node，返回node
                }
                return x;
            }
        }

##### toArray()这个方法也是挺常用的，也看了一下，其实就是构造一个数组，然后遍历链表赋值给数组。 #####

public Object[] toArray() {
        
            Object[] result = new Object[size]; // 构造一个size大小的数组,刚好装下链表中的元素
            int i = 0;
            // 从头结点开始遍历,赋值给数组
            for (Node<E> x = first; x != null; x = x.next) {
        
                result[i++] = x.item;
            }
            return result;
        }

> 若有不足之处，还望大佬们不吝赐教。