概述

     LinkedList采用底层采用双向链表结构，与ArrayList的数组结构不一样。LinkedList因数据结构不一样，不需要申请连续内存，可以利用碎片内存。元素保存数据内容外还需要存储上下游的引用，形成数据链。LinkedList是非线程安全的。   类图  

 

 

size变量     与ArrayList的size变量一样，size在此意思元素数量。   first变量      存储第一个元素引用   last变量      存储最后一个元素引用   Node节点类      LinkedList中实现一个内部类Node，实例对象存储在item中并且保存上下游引用。item变量引用被存储元素实例，next变量引用下一个节点，prev引用上一个节点。见下源码：  

 

 

private修饰说明Node只在LinkedList内部使用 static修饰，因为要static关键字不知道有什么用。   添加元素 add函数其实很简单，调用linkLast函数,未异常返回boolean类型true.   

 

 

linkLast函数实现新增元素追加到元素链最后，并且建立链路关系。size变量累加。 第一种场景：e是第一个元素，last变量为null, newNode变量引用赋给first，last变量引用newNode。 第二种场景：LinkedList的first已存储引用，即e元素非第一个元素。l实例的next变量引用newNode,newNode赋值给last成为最后一个元素。newNode的next变量为null.  

 

 

  批量添加元素 1）checkPositionIndex检查index不能大于size-1   2)传递index变量给node函数获取相应位置的Node实例。见下面源码： index<(size>>1)当成if条件，这里使用一次二分查找方式来快速查找Node实现，LinkedList元素链长的时间特别有用。接下来是一个从头开始查找，另一个从尾开始查找。  

 

 

3）逐个追加元素   4）addAll函数源码  

 

 

  指定索引位置代替元素 使用set函数实现插入元素。使用checkElementIndex检查index,然后使用node函数获取对应index位置Node实例，最后element赋值给item变量。  

 

 

删除指定索引元素的remove函数 1）使用checkElementIndex检查index,node函数获取index对应位置的Node实例， 2）unlink函数删除链路关系。   指定index索引获取元素 1）checkElementIndex检查索引 2）node函数通过index获取Node实例，返回node.item元素。  

 

 

  总结：      1）插入，代替，删除操作耗时少      2）查找操作耗时比较多