LinkedList源码详解

深藏阁楼爱情的钟 2022-05-18 08:34 187阅读 0赞

##### 成员变量声明 #####

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;
        }
    }
    
    transient int size = 0;
    //头节点
    transient Node<E> first;
    //尾节点
    transient Node<E> last;

##### 构造方法初始化 #####

public LinkedList() {
    }

##### add方法 #####

public boolean add(E e) {
        linkLast(e);
        return true;
    }
    void linkLast(E e) {
        //拿到最后一个节点
        final Node<E> l = last;
        //创建新节点
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            //将新节点插入到尾部
            l.next = newNode;
        size++;
        modCount++;
    }

##### set方法 #####

public E set(int index, E element) {
        checkElementIndex(index);
        //找到第index个节点，返回x
        Node<E> x = node(index);
        //新值替换旧值
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }
    Node<E> node(int index) {
        // assert isElementIndex(index);
        //判断index是在前半区间还是后半区间，如果在前半区间就从first搜索，而在后半区间就从last搜索
        //复杂度为O(n/2)
        if (index < (size >> 1)) {
            //从first开始遍历
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            //从last开始遍历
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

##### get方法 #####

public E get(int index) {
        checkElementIndex(index);
        //也是通过node方法遍历找到元素
        return node(index).item;
    }

##### remove方法 #####

public E remove(int index) {
        checkElementIndex(index);
        //找到index位置的节点，调用unlink方法
        return unlink(node(index));
    }
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;//remove节点的后一个
        final Node<E> prev = x.prev;//remove节点的后一个
    
        if (prev == null) {
            first = next;//要删除的节点为第一个节点
        } else {
            prev.next = next;//前一个和后一个连接
            x.prev = null;
        }
    
        if (next == null) {
            last = prev;//要删除的节点为最后与一个节点
        } else {
            next.prev = prev;
            x.next = null;
        }
    
        x.item = null;//元素置为空
        size--;
        modCount++;
        return element;
    }