LinkedList手撕源码

简介

LinkedList实现了List接口和Deque接口，所以LinkedList既可以作为链表也可以作为双端队列。

另外LinkedList是线程不安全的，如果想要使LinkedList变为线程安全，可调用工具类Collections类中的synchronizedList方法

List LinkedList = Collections.synchronizedList(new LinkedList())

基本的结构与构造方法

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 LinkedList(){
}
//通过已有集合创建链表的构造方法
public LinkedList(Collection<? extends E> c){
    this();
    addAll(c);
}

add方法

add(E e)将元素添加到链表尾部

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;
    //当链表不存在node的情况
    if(l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

add(int index , E e)将元素添加到指定的位置

public void add(int index, E element) {
        checkPositionIndex(index); //检查索引是否处于[0-size]之间
        if (index == size)//添加在链表尾部
            linkLast(element);
        else//添加在链表中间
            linkBefore(element, node(index));
    }

addAll方法

addAll(Collection c)：将集合插入到链表尾部

public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

addAll(int index,Collection c)：将集合从指定位置开始插入

public boolean addAll(int index, Collection<? extends E> c) {
        //1:检查index范围是否在size之内
        checkPositionIndex(index);
        //2:toArray()方法把集合的数据存到对象数组中
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
        //3：得到插入位置的前驱节点和后继节点
        Node<E> pred, succ;
        //如果插入位置为尾部，前驱节点为last，后继节点为null
        if (index == size) {
            succ = null;
            pred = last;
        }
        //否则，调用node()方法得到后继节点，再得到前驱节点
        else {
            succ = node(index);
            pred = succ.prev;
        }
        // 4：遍历数据将数据插入
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //创建新节点
            Node<E> newNode = new Node<>(pred, e, null);
            //如果插入位置在链表头部
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        //如果插入位置在尾部，重置last节点
        if (succ == null) {
            last = pred;
        }
        //否则，将插入的链表与先前链表连接起来
        else {
            pred.next = succ;
            succ.prev = pred;
        }
        size += numNew;
        modCount++;
        return true;
    }

总结起来共分为几步：

1. 检查index范围是否超过size
2. 将待加入的集合转为array
3. 获得index插入位置的前驱节点prev和后继节点succ
4. 遍历待加入的array并通过prev节点插入至链表
5. 连接插入后的prev和succ

获取头结点的方法

public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
public E element() {
        return getFirst();
    }
public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }
public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

getFirst()、element()和peek()、peekFirst()的区别在于对链表为空的处理，是抛出异常还是返回null。

根据对象获得索引

有可能是因为==运算符的速度较o.equals快，所以要分为对象是否为null的两种情况

public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            //从头遍历
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            //从头遍历
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }
public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            //从尾遍历
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            //从尾遍历
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }