Java集合-04LinkedList源码解析

回顾与对比

LinkedList简介

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList构造函数

1. public LinkedList()

2. LinkedList(Collection<? extends E> c)

结构分析

LinkedList源码分析(java version:1.8.0_111)

Node

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;
        }
    }

添加元素

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++;
    }

---

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

Node<E> node(int index) {
        // assert isElementIndex(index);

        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;
        }
    }

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

LinkedList遍历

1.迭代器遍历

Iterator iterator = list.iterator();
while (iterator.hasNext()){
    iterator.next();
}

2.ForEach遍历

for (Object s : list) 

3.随机访问遍历

for (int i =0; i<list.size();i++){
    list.get(i);
}

4.pollFirst()/pollLast()/removeFirst()/removeLast()方法

while (list.pollFirst() != null){

}

总结