Java集合-LinkedList工作原理及实现

概述

1.基于双向链表实现，容量无限制。但双向链表本身使用了更多空间，也需要额外的链表指针操作。

2.按下标访问元素—get(i)/set(i,e) 要悲剧的遍历链表将指针移动到位(如果i>数组大小的一半，会从末尾移起)，时间复杂度O(N/2)

3.插入和删除：只须修改前后节点的指针即可，但还是要遍历部分链表的指针才能移动到下标所指的位置，只有在链表两头的操作—add(), addFirst(),removeLast()或用iterator()上的remove()能省掉指针的移动

链表结构定义

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    transient int size = ;  
    transient Node<E> first;  
    transient Node<E> last;
    // 其余省略
}
           

典型的双向链表实现，看个示例代码：

LinkedList<String> list = new LinkedList<String>();
list.add("语文: 1");  
list.add("数学: 2");  
list.add("英语: 3");
           

结构也相对简单一些，如下图所示：

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和get方法

public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }        public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
           

这两个方法都用node(index)方法找链表节点，查找的方法会比对索引下标，如果小于size的一半就从头部开始查找，如果大于size的一半就从尾部从后向前查找，实现时间复杂度为O(n/2)，提高效率，

Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> )) {
            Node<E> x = first;
            for (int i = ; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - ; i > index; i--)
                x = x.prev;
            return x;
        }
    }
           

白天在加班加点的干活，还要抽出时间成为技术知识的分享者，分享不易，转载请注明出处。