前言
LinkedList使用频率相较ArrayList
不高,但也值得探讨一下。适合集合高频次修改时采用。
介绍
与ArrayList
不同,LinkedList是对List和Deque接口的双向链表实现。实现所有可选的列表操作,并允许所有元素(包括null)。 所有操作的执行都与双链接列表的预期一样。索引到列表中的操作将从开始或结束遍历列表,以更接近指定索引的为准。
请注意,此实现是不同步的。如果多个线程同时访问一个链表,并且至少有一个线程在结构上修改链表,则必须在外部对其进行同步。(结构修改是添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。)这通常通过在自然封装列表的某个对象上进行同步来实现。如果不存在此类对象,则应使用Collections.synchronizedList
方法“包装”列表。最好在创建时执行此操作,以防止意外不同步地访问列表:
List list = Collections.synchronizedList(new LinkedList(...));
成员变量
1 | transient int size = 0; |
节点
1 | private static class Node<E> { |
数据结构
双向链表,可以从任一节点向前或者向后遍历。不支持随机访问。
push(E e)
1 | /** |
1 | /** |
1 | /** |
这里其实就是链表的头插法,新建一个节点指向之前的头节点,之前的头节点向前指向新节点。头指针指向新的节点。
pop()
1 |
|
1 | /** |
1 | /** |
和push
相反,pop
弹出头节点,头指针指向头节点的下一个节点,下一个节点向前指向null
结尾
这里只是把LinkedList
的核心数据结构指出,其他方法也都是对于双向链表的常规操作,读者可自行了解。
关于作者
我叫无涯,一位热爱coding的coder。更多文章在我的个人博客:oneyoung.top 。让我们一起进步。