java -- LinkedList

java -- LinkedList

 

 

LinkedList是一个简单的数据结构，与ArrayList不同的是，他是基于链表实现的。

 

 

 

优点

 

• 插入和删除操作比 ArrayList 更加高效
• LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
• 不需要连续的存储空间，只需要有指向上一个节点和下一个节点的标记就好
• 可以接受各种数据类型
• LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。

 

 

缺点

 

• 随机访问的效率比ArrayList差，但是顺序访问还是可以的
• 非线程安全

 

 

工作原理

 

    LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：

 

    既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息，如下图所示： 

 

 

 

构造方法

 

LinkedList有两种构造方法：

 

• 第一个构造方法不接受参数，将header实例的previous和next全部指向header实例（注意，这个是一个双向循环链表，如果不是循环链表，空链表的情况应该是header节点的前一节点和后一节点均为null），这样整个链表其实就只有header一个节点，用于表示一个空的链表。 
• 第二个构造方法接收一个Collection参数c，调用第一个构造方法构造一个空的链表，之后通过addAll将c中的元素全部添加到链表中。

第一种情况如下图：

 

 

// 第一种构造函数
public LinkedList() {    
 header.next = header.previous = header;
 }

// 第二种构造函数
public LinkedList(Collection<? extends E> c) {
     this();
   addAll(c);

 

 

 

 

 

插入、修改、数据存储

 

• 插入数据add(e)，会插入到最尾，修改指针指向的节点就好，如果add(index, e)也是同样的道理，所以也是非常快
• 修改、查找数据set(index, e), get(index)，复杂度是O(n/2)，虽然不是O(n)，但怎么都比数组要慢。同时，查到某个节点后，可以查前一个和后一个节点。
• 删除remove(index)，与ArrayList比较而言，LinkedList的删除动作不需要“移动”很多数据，从而效率更高。

 

容量调整

      不同于ArrayList，LinkedList不可以在初始化时候指定大小。同样ArrayList有加载因子，在容量不够的时候可以扩容，然而LinkedList容量的说法，每次向其中加入元素时候，容量自动加1。

 

 

并发处理

      与ArrayList类似，面对并发的修改，迭代器很快就会完全失败，而不冒将来不确定的时间任意发生不确定行为的风险。