数据结构之LinkedList底层实现和原理详解

2024-12-14 00:38

短信预约 -IT技能 免费直播动态提醒

当然作为高级程序员，我们不仅仅要会用，还要了解其中的原理;

今天我们就来聊聊LinkedList底层实现和原理

一、LinkedList介绍

public class LinkedList 
    extends AbstractSequentialList 
    implements List, Deque, Cloneable, java.io.Serializable 
{ 
    //长度 
    transient int size = 0; 
    //指向头结点 
    transient Node first; 
    //指向尾结点 
    transient Node last; 
}

1、LinkedList概述

LinkedList同时实现了List接口和Deque对口，也就是收它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(stack);

这样看来，linkedList简直就是无敌的，当你需要使用栈或者队列时，可以考虑用LinkedList,一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类(只是一个接口的名字);

关于栈或队列，现在首选是ArrayDeque，它有着比LinkedList(当作栈或队列使用时)更好的性能;

LinkedList的实现方式决定了所有跟下表有关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步(synchronized)，如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装

2、数据结构

继承关系

java.lang.Object  
    java.util.AbstractCollection  
        java.util.AbstractList  
            java.util.AbstractSequentialList  
                java.util.LinkedList

实现接口

Serializable, Cloneable, Iterable, Collection, Deque, List, Queue

基本属性

transient int size = 0; //LinkedList中存放的元素个数
transient Node first; //头节点
transient Node last; //尾节点
Collection 接口：Collection接口是所有集合类的根节点，Collection表示一种规则，所有实现了Collection接口的类遵循这种规则

继承的类与实现的接口

List 接口：List是Collection的子接口，它是一个元素有序(按照插入的顺序维护元素顺序)、可重复、可以为null的集合
AbstractCollection 类：Collection接口的骨架实现类，最小化实现了Collection接口所需要实现的工作量
AbstractList 类：List接口的骨架实现类，最小化实现了List接口所需要实现的工作量
Cloneable 接口：实现了该接口的类可以显示的调用Object.clone()方法，合法的对该类实例进行字段复制，如果没有实现Cloneable接口的实例上调用Obejct.clone()方法，会抛出CloneNotSupportException异常。正常情况下，实现了Cloneable接口的类会以公共方法重写Object.clone()
Serializable 接口：实现了该接口标示了类可以被序列化和反序列化，具体的查询序列化详解
Deque 接口：Deque定义了一个线性Collection，支持在两端插入和删除元素，Deque实际是“double ended queue(双端队列)”的简称，大多数Deque接口的实现都不会限制元素的数量，但是这个队列既支持有容量限制的实现，也支持没有容量限制的实现，比如LinkedList就是有容量限制的实现,其最大的容量为Integer.MAX_VALUE
AbstractSequentialList 类：提供了List接口的骨干实现，最大限度地减少了实现受“连续访问”数据存储(如链表)支持的此接口所需的工作，对于随机访问数据(如数组)，应该优先使用 AbstractList，而不是使用AbstractSequentailList类

二、底层源码分析

LinkedList是通过双向链表去实现的，既然是链表实现那么它的随机访问效率比ArrayList要低，顺序访问的效率要比较的高。每个节点都有一个前驱(之前前面节点的指针)和一个后继(指向后面节点的指针)

效果如下图：

源码标注如下：

public class LinkedListextends AbstractSequentialList 
    implements List, Deque, Cloneable, java.io.Serializable 
{ 
    transient int size = 0;   //LinkedList中存放的元素个数 
    transient Node first;  //头节点 
    transient Node last;   //尾节点 
    //构造方法，创建一个空的列表 
    public LinkedList() { 
    } 
    //将一个指定的集合添加到LinkedList中，先完成初始化，在调用添加操作 
    public LinkedList(Collection c) { 
        this(); 
        addAll(c); 
    } 
    //插入头节点 
    private void linkFirst(E e) { 
        final Node f = first;  //将头节点赋值给f节点 
        //new 一个新的节点，此节点的data = e , pre = null , next - > f  
        final Node newNode = new Node<>(null, e, f); 
        first = newNode; //将新创建的节点地址复制给first 
        if (f == null)  //f == null，表示此时LinkedList为空 
            last = newNode;  //将新创建的节点赋值给last 
        else 
            f.prev = newNode;  //否则f.前驱指向newNode 
        size++; 
        modCount++; 
    } 
    //插入尾节点 
    void linkLast(E e) { 
        final Node l = last;  
        final Node newNode = new Node<>(l, e, null); 
        last = newNode; 
        if (l == null) 
            first = newNode; 
        else 
            l.next = newNode; 
        size++; 
        modCount++; 
    } 
    //在succ节点前插入e节点，并修改各个节点之间的前驱后继 
    void linkBefore(E e, Node succ) { 
        // assert succ != null; 
        final Node pred = succ.prev; 
        final Node newNode = new Node<>(pred, e, succ); 
        succ.prev = newNode; 
        if (pred == null) 
            first = newNode; 
        else 
            pred.next = newNode; 
        size++; 
        modCount++; 
    } 
    //删除头节点 
    private E unlinkFirst(Node f) { 
        // assert f == first && f != null; 
        final E element = f.item; 
        final Node 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; 
    } 
    //删除尾节点 
    private E unlinkLast(Node l) { 
        // assert l == last && l != null; 
        final E element = l.item; 
        final Node prev = l.prev; 
        l.item = null; 
        l.prev = null; // help GC 
        last = prev; 
        if (prev == null) 
            first = null; 
        else 
            prev.next = null; 
        size--; 
        modCount++; 
        return element; 
    } 
    //删除指定节点 
    E unlink(Node x) { 
        // assert x != null; 
        final E element = x.item; 
        final Node next = x.next;  //获取指定节点的前驱 
        final Node prev = x.prev;  //获取指定节点的后继 
        if (prev == null) { 
            first = next;   //如果前驱为null, 说明此节点为头节点 
        } else { 
            prev.next = next;  //前驱结点的后继节点指向当前节点的后继节点 
            x.prev = null;     //当前节点的前驱置空 
        } 
        if (next == null) {    //如果当前节点的后继节点为null ,说明此节点为尾节点 
            last = prev; 
        } else { 
            next.prev = prev;  //当前节点的后继节点的前驱指向当前节点的前驱节点 
            x.next = null;     //当前节点的后继置空 
        } 
        x.item = null;     //当前节点的元素设置为null ,等待垃圾回收 
        size--; 
        modCount++; 
        return element; 
    } 
    //获取LinkedList中的第一个节点信息 
    public E getFirst() { 
        final Node f = first; 
        if (f == null) 
            throw new NoSuchElementException(); 
        return f.item; 
    } 
    //获取LinkedList中的最后一个节点信息 
    public E getLast() { 
        final Node l = last; 
        if (l == null) 
            throw new NoSuchElementException(); 
        return l.item; 
    } 
    //删除头节点 
    public E removeFirst() { 
        final Node f = first; 
        if (f == null) 
            throw new NoSuchElementException(); 
        return unlinkFirst(f); 
    } 
    //删除尾节点 
    public E removeLast() { 
        final Node l = last; 
        if (l == null) 
            throw new NoSuchElementException(); 
        return unlinkLast(l); 
    } 
    //将添加的元素设置为LinkedList的头节点 
    public void addFirst(E e) { 
        linkFirst(e); 
    } 
    //将添加的元素设置为LinkedList的尾节点 
    public void addLast(E e) { 
        linkLast(e); 
    } 
    //判断LinkedList是否包含指定的元素 
    public boolean contains(Object o) { 
        return indexOf(o) != -1; 
    } 
    //返回List中元素的数量 
    public int size() { 
        return size; 
    } 
    //在LinkedList的尾部添加元素 
    public boolean add(E e) { 
        linkLast(e); 
        return true; 
    } 
    //删除指定的元素 
    public boolean remove(Object o) { 
        if (o == null) { 
            for (Node x = first; x != null; x = x.next) { 
                if (x.item == null) { 
                    unlink(x); 
                    return true; 
                } 
            } 
        } else { 
            for (Node x = first; x != null; x = x.next) { 
                if (o.equals(x.item)) { 
                    unlink(x); 
                    return true; 
                } 
            } 
        } 
        return false; 
    } 
    //将集合中的元素添加到List中 
    public boolean addAll(Collection c) { 
        return addAll(size, c); 
    } 
    //将集合中的元素全部插入到List中，并从指定的位置开始 
    public boolean addAll(int index, Collection c) { 
        checkPositionIndex(index); 
        Object[] a = c.toArray();  //将集合转化为数组 
        int numNew = a.length;  //获取集合中元素的数量 
        if (numNew == 0)   //集合中没有元素，返回false 
            return false; 
        Node pred, succ; 
        if (index == size) { 
            succ = null; 
            pred = last; 
        } else { 
            succ = node(index); //获取位置为index的结点元素，并赋值给succ 
            pred = succ.prev; 
        } 
        for (Object o : a) {  //遍历数组进行插入操作。修改节点的前驱后继 
            @SuppressWarnings("unchecked") E e = (E) o; 
            Node newNode = new Node<>(pred, e, null); 
            if (pred == null) 
                first = newNode; 
            else 
                pred.next = newNode; 
            pred = newNode; 
        } 
        if (succ == null) { 
            last = pred; 
        } else { 
            pred.next = succ; 
            succ.prev = pred; 
        } 
        size += numNew; 
        modCount++; 
        return true; 
    } 
    //删除List中所有的元素 
    public void clear() { 
        // Clearing all of the links between nodes is "unnecessary", but: 
        // - helps a generational GC if the discarded nodes inhabit 
        //   more than one generation 
        // - is sure to free memory even if there is a reachable Iterator 
        for (Node x = first; x != null; ) { 
            Node next = x.next; 
            x.item = null; 
            x.next = null; 
            x.prev = null; 
            x = next; 
        } 
        first = last = null; 
        size = 0; 
        modCount++; 
    } 
    //获取指定位置的元素 
    public E get(int index) { 
        checkElementIndex(index); 
        return node(index).item; 
    } 
    //将节点防止在指定的位置 
    public E set(int index, E element) { 
        checkElementIndex(index); 
        Node x = node(index); 
        E oldVal = x.item; 
        x.item = element; 
        return oldVal; 
    } 
    //将节点放置在指定的位置 
    public void add(int index, E element) { 
        checkPositionIndex(index); 
        if (index == size) 
            linkLast(element); 
        else 
            linkBefore(element, node(index)); 
    } 
    //删除指定位置的元素 
    public E remove(int index) { 
        checkElementIndex(index); 
        return unlink(node(index)); 
    } 
    //判断索引是否合法 
    private boolean isElementIndex(int index) { 
        return index >= 0 && index < size; 
    } 
    //判断位置是否合法 
    private boolean isPositionIndex(int index) { 
        return index >= 0 && index <= size; 
    } 
    //索引溢出信息 
    private String outOfBoundsMsg(int index) { 
        return "Index: "+index+", Size: "+size; 
    } 
    //检查节点是否合法 
    private void checkElementIndex(int index) { 
        if (!isElementIndex(index)) 
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 
    } 
    //检查位置是否合法 
    private void checkPositionIndex(int index) { 
        if (!isPositionIndex(index)) 
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 
    } 
    //返回指定位置的节点信息 
    //LinkedList无法随机访问，只能通过遍历的方式找到相应的节点 
    //为了提高效率，当前位置首先和元素数量的中间位置开始判断，小于中间位置， 
    //从头节点开始遍历，大于中间位置从尾节点开始遍历 
    Node node(int index) { 
        // assert isElementIndex(index); 
        if (index < (size >> 1)) { 
            Node x = first; 
            for (int i = 0; i < index; i++) 
                x = x.next; 
            return x; 
        } else { 
            Node x = last; 
            for (int i = size - 1; i > index; i--) 
                x = x.prev; 
            return x; 
        } 
    } 
    //返回第一次出现指定元素的位置 
    public int indexOf(Object o) { 
        int index = 0; 
        if (o == null) { 
            for (Node x = first; x != null; x = x.next) { 
                if (x.item == null) 
                    return index; 
                index++; 
            } 
        } else { 
            for (Node 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 x = last; x != null; x = x.prev) { 
                index--; 
                if (x.item == null) 
                    return index; 
            } 
        } else { 
            for (Node x = last; x != null; x = x.prev) { 
                index--; 
                if (o.equals(x.item)) 
                    return index; 
            } 
        } 
        return -1; 
    } 
    //弹出第一个元素的值 
    public E peek() { 
        final Node f = first; 
        return (f == null) ? null : f.item; 
    } 
    //获取第一个元素 
    public E element() { 
        return getFirst(); 
    } 
    //弹出第一元素，并删除 
    public E poll() { 
        final Node f = first; 
        return (f == null) ? null : unlinkFirst(f); 
    } 
    //删除第一个元素 
    public E remove() { 
        return removeFirst(); 
    } 
    //添加到尾部 
    public boolean offer(E e) { 
        return add(e); 
    } 
    //添加到头部 
    public boolean offerFirst(E e) { 
        addFirst(e); 
        return true; 
    } 
    //插入到最后一个元素 
    public boolean offerLast(E e) { 
        addLast(e); 
        return true; 
    } 
    //队列操作 
    //尝试弹出第一个元素，但是不删除元素 
    public E peekFirst() { 
        final Node f = first; 
        return (f == null) ? null : f.item; 
     } 
    //队列操作 
    //尝试弹出最后一个元素，不删除 
    public E peekLast() { 
        final Node l = last; 
        return (l == null) ? null : l.item; 
    } 
    //弹出第一个元素，并删除 
    public E pollFirst() { 
        final Node f = first; 
        return (f == null) ? null : unlinkFirst(f); 
    } 
    //弹出最后一个元素，并删除 
    public E pollLast() { 
        final Node l = last; 
        return (l == null) ? null : unlinkLast(l); 
    } 
    //如队列，添加到头部 
    public void push(E e) { 
        addFirst(e); 
    } 
    //出队列删除第一个节点 
    public E pop() { 
        return removeFirst(); 
    } 
   //删除指定元素第一次出现的位置 
    public boolean removeFirstOccurrence(Object o) { 
        return remove(o); 
    } 
    //删除指定元素最后一次出现的位置 
    public boolean removeLastOccurrence(Object o) { 
        if (o == null) { 
            for (Node x = last; x != null; x = x.prev) { 
                if (x.item == null) { 
                    unlink(x); 
                    return true; 
                } 
            } 
        } else { 
            for (Node x = last; x != null; x = x.prev) { 
                if (o.equals(x.item)) { 
                    unlink(x); 
                    return true; 
                } 
            } 
        } 
        return false; 
    } 
    //遍历方法 
    public ListIterator listIterator(int index) { 
        checkPositionIndex(index); 
        return new ListItr(index); 
    } 
    //内部类，实现ListIterator接口 
    private class ListItr implements ListIterator { 
        private Node lastReturned = null; 
        private Node next; 
        private int nextIndex; 
        private int expectedModCount = modCount; 
        ListItr(int index) { 
            // assert isPositionIndex(index); 
            next = (index == size) ? null : node(index); 
            nextIndex = index; 
        } 
        public boolean hasNext() { 
            return nextIndex < size; 
        } 
        public E next() { 
            checkForComodification(); 
            if (!hasNext()) 
                throw new NoSuchElementException(); 
            lastReturned = next; 
            next = next.next; 
            nextIndex++; 
            return lastReturned.item; 
        } 
        public boolean hasPrevious() { 
            return nextIndex > 0; 
        } 
        public E previous() { 
            checkForComodification(); 
            if (!hasPrevious()) 
                throw new NoSuchElementException(); 
            lastReturned = next = (next == null) ? last : next.prev; 
            nextIndex--; 
            return lastReturned.item; 
        } 
        public int nextIndex() { 
            return nextIndex; 
        } 
        public int previousIndex() { 
            return nextIndex - 1; 
        } 
        public void remove() { 
            checkForComodification(); 
            if (lastReturned == null) 
                throw new IllegalStateException(); 
            Node lastNext = lastReturned.next; 
            unlink(lastReturned); 
            if (next == lastReturned) 
                next = lastNext; 
            else 
                nextIndex--; 
            lastReturned = null; 
            expectedModCount++; 
        } 
        public void set(E e) { 
            if (lastReturned == null) 
                throw new IllegalStateException(); 
            checkForComodification(); 
            lastReturned.item = e; 
        } 
        public void add(E e) { 
            checkForComodification(); 
            lastReturned = null; 
            if (next == null) 
                linkLast(e); 
            else 
                linkBefore(e, next); 
            nextIndex++; 
            expectedModCount++; 
        } 
        final void checkForComodification() { 
            if (modCount != expectedModCount) 
                throw new ConcurrentModificationException(); 
        } 
    } 
    //静态内部类，创建节点 
    private static class Node { 
        E item; 
        Node next; 
        Node prev; 
        Node(Node prev, E element, Node next) { 
            this.item = element; 
            this.next = next; 
            this.prev = prev; 
        } 
    } 
     
    public Iterator descendingIterator() { 
        return new DescendingIterator(); 
    } 
     
    private class DescendingIterator implements Iterator { 
        private final ListItr itr = new ListItr(size()); 
        public boolean hasNext() { 
            return itr.hasPrevious(); 
        } 
        public E next() { 
            return itr.previous(); 
        } 
        public void remove() { 
            itr.remove(); 
        } 
    } 
    @SuppressWarnings("unchecked") 
    private LinkedList superClone() { 
        try { 
            return (LinkedList) super.clone(); 
        } catch (CloneNotSupportedException e) { 
            throw new InternalError(); 
        } 
    } 
     
    public Object clone() { 
        LinkedList clone = superClone(); 
        // Put clone into "virgin" state 
        clone.first = clone.last = null; 
        clone.size = 0; 
        clone.modCount = 0; 
        // Initialize clone with our elements 
        for (Node x = first; x != null; x = x.next) 
            clone.add(x.item); 
        return clone; 
    } 
    public Object[] toArray() { 
        Object[] result = new Object[size]; 
        int i = 0; 
        for (Node x = first; x != null; x = x.next) 
            result[i++] = x.item; 
        return result; 
    } 
    @SuppressWarnings("unchecked") 
    public  T[] toArray(T[] a) { 
        if (a.length < size) 
            a = (T[])java.lang.reflect.Array.newInstance( 
                                a.getClass().getComponentType(), size); 
        int i = 0; 
        Object[] result = a; 
        for (Node x = first; x != null; x = x.next) 
            result[i++] = x.item; 
        if (a.length > size) 
            a[size] = null; 
        return a; 
    } 
    private static final long serialVersionUID = 876323262645176354L; 
    //将对象写入到输出流中 
    private void writeObject(java.io.ObjectOutputStream s) 
        throws java.io.IOException { 
        // Write out any hidden serialization magic 
        s.defaultWriteObject(); 
        // Write out size 
        s.writeInt(size); 
        // Write out all elements in the proper order. 
        for (Node x = first; x != null; x = x.next) 
            s.writeObject(x.item); 
    } 
    //从输入流中将对象读出 
    @SuppressWarnings("unchecked") 
    private void readObject(java.io.ObjectInputStream s) 
        throws java.io.IOException, ClassNotFoundException { 
        // Read in any hidden serialization magic 
        s.defaultReadObject(); 
        // Read in size 
        int size = s.readInt(); 
        // Read in all elements in the proper order. 
        for (int i = 0; i < size; i++) 
            linkLast((E)s.readObject()); 
    } 
}

1、构造方法

LinkedList()  
LinkedList(Collection c)

LinkedList没有长度的概念，所以不存在容量不足的问题，因此不需要提供初始化大小的构造方法，因此值提供了两个方法，一个是无参构造方法，初始一个LinkedList对象，和将指定的集合元素转化为LinkedList构造方法。

2、添加节点

public boolean add(E e) { 
     linkLast(e); 
     return true; 
} 
void linkLast(E e) { 
     final Node l = last; 
     final Node newNode = new Node<>(l, e, null); 
     last = newNode; 
     if (l == null) 
         first = newNode; 
     else 
          l.next = newNode; 
     size++; 
     modCount++; 
}

通过源码可以看出添加的过程如下：

记录当前末尾节点，通过构造另外一个指向末尾节点的指针l
产生新的节点：注意的是由于是添加在链表的末尾，next是为null的
last指向新的节点
这里有个判断，我的理解是判断是否为第一个元素(当l==null时，表示链表中是没有节点的)，
那么就很好理解这个判断了，如果是第一节点，则使用first指向这个节点，若不是则当前节点的next指向新增的节点
size增加：在上面提到的LinkedList["A","B","C"]中添加元素“D”，过程大致如图：

3、删除节点

LinkedList中提供了两个方法删除节点

//方法1.删除指定索引上的节点 
public E remove(int index) { 
    //检查索引是否正确 
    checkElementIndex(index); 
    //这里分为两步，第一通过索引定位到节点，第二删除节点 
    return unlink(node(index)); 
} 
//方法2.删除指定值的节点 
public boolean remove(Object o) { 
    //判断删除的元素是否为null 
    if (o == null) { 
        //若是null遍历删除 
        for (Node x = first; x != null; x = x.next) { 
            if (x.item == null) { 
                unlink(x); 
                return true; 
            } 
        } 
    } else { 
        //若不是遍历删除  
        for (Node x = first; x != null; x = x.next) { 
            if (o.equals(x.item)) { 
                unlink(x); 
                return true; 
            } 
        } 
    } 
    return false; 
}