List系列->02LinkedList

List层级关系:

List层级关系

List系列:

1. ArrayList;
2. LinkedList;
3. Vector;
4. Stack;

一、LinkedList.add:

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    /**
     * 仅仅是进行了将元素追加到最后LastNode的操作, 时间复杂度为O(1)
     */
    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++;
}

二、LinkedList.remove:

public E remove() {
    return removeFirst();
}

public E removeFirst() {
    final Node<E> f = first;
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    /**
     * 删除第一个元素, 结合时间复杂度的定义, 此时时间复杂度为O(1), 仅仅进行了删除, 
     * 链表中元素位置交换操作;
     */
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

三、LinkedList.get:

public E get(int index) {
    return node(index).item;
}

Node<E> node(int index) {
     /**
      * size >> 1为了减少查找的次数, 不过仅仅折半了一次, 所以对时间复杂度并没有影响, 
      * 如果index < (size >> 1), 从前部分开始进行遍历, 反之总后半部分进行遍历查找; 
      */
     if (index < (size >> 1)) {
        Node<E> x = first;
        /**
         * 如果有N个元素, 则需要遍历index次, 考虑最坏的情况for内部需要执行index次, 
         * 如果index = 1, 则for内部只需要执行1次, 综合起来就是需要执行O(index)即O(n)次; 
         */
        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;
    }
}

• LinkedList内部还有其他几个增删改的方法, 如果内部需要用到node(int index), 则时间复杂度为O(n)

四、总结(针对时间复杂度):

操作	时间复杂度	对时间复杂度有影响的操作
add(E)	O(1)	new Node(E)
remove	O(1)	Node(first) = null
get	O(n)	for()

结合List系列->01ArrayList可知, 如果增删操作比较频繁, 而get操作比较少的情况下, 优先采用LinkedList, 反之采用ArrayList;