LinkedList

LinkedList线程不安全，

image.png

不指定位置add操作

image.png

• 不指定位置的添加操作；

  
  image.png
• 把当前尾节点暂存；
• 对新添加元素创建节点对象，创建对象过程中指定了新添加元素节点的前驱节点为原来的尾节点，后继节点为null;
• 设置最新尾节点为新添加元素节点；
• 如果原来的尾节点为null，设置第一个节点也是新添加元素节点；
• 否则设置原来尾节点的后继节点为新添加元素节点。

指定位置add操作

image.png

• 检查所有位置是否越界
• 判断指定的索引是否为尾节点索引，是执行添加尾节点的逻辑
• 否则，执行添加指定位置的节点逻辑

image.png

• 判断指定索引的值是否是原来的添加元素数量的前半部分；
• 如果是从前往后遍历
• 如果过否从后往前遍历
• 总之为了提高索引效率。

image.png

• 请求参数，新添加的元素，指定索引位置的老元素；
• 获取指定索引位置的老元素的前驱节点；
• 创建新添加元素的节点对象；
• 将指定索引位置的老元素的前驱节点指向新添加元素的节点对象；
• 如果指定索引位置的老元素的前驱节点不存在，即没有前驱节点，老元素是第一个节点，则此时的新元素将占据老元素的位置变为第一个节点，
• 否则指定索引位置的老元素的前驱节点的后继节点指向新添加元素的节点对象。
• 自此完成新节点的插入。