LinkedList内部实现原理

java

list

同ArrayList内部原理一样

我们先创建一个LinkedList对象LinkedList<String> li = new LinkedList<>();，然后查看其构造方法

	transient Node<E> first;

	transient Node<E> last;

	public LinkedList() {

    }

比较尴尬的是在它的构造方法中什么也没有写。LinkedList的结构是**双向链表结构**，链表结构数据是存储在节点中的，我们正好看到两个Node节点属性，一个叫first代表链表中第一个节点，另一个叫last代表链表中最后一个节点。

查看一下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;

        }

这是一个内部类，标准的双向链表的数据结构Node<E> prev前驱指向该节点的前一个节点，Node<E> next;后继指向该节点的后一个节点，E item;元素用于存放数据。

当我们执行add()方法向LinkedList中添加数据的时候，调用以下方法

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

    }

我们发现它将last（最后一个节点）给了l节点，然后new了一个新的节点初始化新节点的前驱为l节点，后继为null,元素为我们要存放的对象。然后设置newNode为last节点，如果节点l为null则设置newNode为first节点，否则使l的next指向新的节点 l.next = newNode。

FirstLastNode

内部原理

巴特西

LinkedList内部实现原理

LinkedList内部实现原理

最新文章

热门文章