LinkedList底层数据结构是一个具有头尾节点的双向链表。双向链表的优点就是通过某个节点访问其前驱和后驱表较方便。缺点是需要额外存储其前驱和后驱的空间。LinkeList链表允许null元素；
问题一：LinkedList如何初始化
LinkedList构造函数有两种，无参构造和带集合的构造函数
1.无参构造，初始化集合大小size=0，初始不用存储任何数据，内存占用低；
public LinkedList() {
this.size = 0;
}
2.带集合的构造函数，创建一个大小和传入集合大小一致的链表，记录头尾节点
public LinkedList(Collection<? extends E> c) {
this();
this.addAll(c);
}
3.接着2我们来看下addAll方法，他的参数有index和传入的集合，猜想index应该是传入集合存储开始的地方。
public boolean addAll(int index, Collection<? extends E> c) {
//判断这个index是否超过链表有效位置的范围，超出的话会报IndexOutOfBoundsException.
this.checkPositionIndex(index);
//返回包含这个集合中所有数据的数组，感觉是个耗时操作
Object[] a = c.toArray();
//获取参数集合的长度，是构造之后链表的长度
int numNew = a.length;
//参数集合长度为0，说明不需要存储任何数据，就不用做任何事了直接返回。
if (numNew == 0) {
return false;
} else {
//辅助构造链表
LinkedList.Node pred;
LinkedList.Node succ;
//index = this.size从链表尾部插入
if (index == this.size) {
succ = null;
pred = this.last;
} else {
//index != this.size从链表中间插入
succ = this.node(index);
pred = succ.prev;
}
Object[] var7 = a;
int var8 = a.length;
//遍历参数集合的数组，从插入的位置index开始插入
for(int var9 = 0; var9 < var8; ++var9) {
Object o = var7[var9];
LinkedList.Node<E> newNode = new LinkedList.Node(pred, o, (LinkedList.Node)null);
//插入集合的第一个节点
if (pred == null) {
this.first = newNode;
} else {
//上一个节点记录一下当前节点，形成链表
pred.next = newNode;
}
//pred记录当前节点，开始下一个节点的插入
pred = newNode;
}
//succ =null说明是从链表尾部开始插入的，所以记录一下链表头部，就行了。
if (succ == null) {
this.last = pred;
} else {
//相反的不是从链表尾部插入，从第index个插入，index元素排在插入的数据后面，形成新链表。
pred.next = succ;
succ.prev = pred;
}
//记录新的链表长度
this.size += numNew;
++this.modCount;
return true;
}
}
问题二：LinkedList怎么插入数据？
LinkedList堆插入操作做了相关优化。由于其基于双端链表实现，所以其在头尾插入速度较快，在链表中部插入相对较慢。
1.头部插入元素，直接通过头节点first插入，头节点变成第二个元素，更新头节点，非常简单。
private void linkFirst(E e) {
LinkedList.Node<E> f = this.first;
LinkedList.Node<E> newNode = new LinkedList.Node((LinkedList.Node)null, e, f);
this.first = newNode;
if (f == null) {
this.last = newNode;
} else {
f.prev = newNode;
}
++this.size;
++this.modCount;
}
2.尾部插入元素，直接通过尾节点插入新元素 ，待插入节点变成新的尾节点。
void linkLast(E e) {
LinkedList.Node<E> l = this.last;
LinkedList.Node<E> newNode = new LinkedList.Node(l, e, (LinkedList.Node)null);
this.last = newNode;
if (l == null) {
this.first = newNode;
} else {
l.next = newNode;
}
++this.size;
++this.modCount;
}
3.中间插入元素，如果index=链表长度则表示在链表尾部插入数据，否则实在指定元素之前插入元素。
public void add(int index, E element) {
this.checkPositionIndex(index);
if (index == this.size) {
this.linkLast(element);
} else {
this.linkBefore(element, this.node(index));
}
}
4.在看linkBefore之前我看下node方法，这个方法是通过index找到链表中的某个数据。通过以下代码我们可以看到它使用了一次二分查找，提高了一次查找效率，但是随着数据增多这个函数的效率会变得越来越低。
LinkedList.Node<E> node(int index) {
LinkedList.Node x;
int i;
if (index < this.size >> 1) {
x = this.first;
for(i = 0; i < index; ++i) {
x = x.next;
}
return x;
} else {
x = this.last;
for(i = this.size - 1; i > index; --i) {
x = x.prev;
}
return x;
}
}
5.接着看下linkBefore方法。找到指定元素就非常好办了，生成新节点，把新节点放在指定元素的前面就可以了。
void linkBefore(E e, LinkedList.Node<E> succ) {
LinkedList.Node<E> pred = succ.prev;
LinkedList.Node<E> newNode = new LinkedList.Node(pred, e, succ);
succ.prev = newNode;
//如果succ是头节点，还需要更新头节点指针。
if (pred == null) {
this.first = newNode;
} else {
pred.next = newNode;
}
++this.size;
++this.modCount;
}
问题三：LinkedList怎么删除元素
删除节点和增加节点都是通过node方法找到指定元素，然后删除指定节点，链表的基本操作，这里不再赘叙。
网友评论