LinkedList中的变量以及Node类,size代表当前双向链表的长度(Node数量),first代表在当前双向链表中头部的Node,last代表在当前双向链表中尾部的Node,Node代表在双向链表中存储元素的对象,Node中的next和prev代表下一个和上一个Node所在的位置。
//双向链表长度
transient int size = 0;
?
//双向链表头节点
transient Node<E> first;
?
//双向链表尾节点
transient Node<E> last;
?
private static class Node<E> {
//节点元素
E item;
//下一个节点
Node<E> next;
//上一个节点
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
1.将指定元素添加到双向链表末尾
public boolean add(E e) {
//添加元素
linkLast(e);
return true;
}
//将指定元素添加到双向链表末尾
void linkLast(E e) {
//原尾节点
final Node<E> l = last;
//创建新的节点将指定元素放置节点中并将节点中的上一个节点指针指向原尾节点
final Node<E> newNode = new Node<>(l, e, null);
//将当前指定元素所在的节点设置为新的尾节点
last = newNode;
if (l == null)
//原尾节点为null则说明双向链表中没有节点元素
//将当前指定元素所在的节点设置为新的头节点
first = newNode;
else
//将原尾节点中的下一个节点指针指向新的尾节点
l.next = newNode;
//更新双向链表长度
size++;
//更新双向链表修改次数
modCount++;
}
2.将元素添加到指定的索引位置
public void add(int index, E element) {
//校验索引是否在有效的索引位置
checkPositionIndex(index);
if (index == size)
//添加元素的索引位置等于双向链表的长度则往双向链表尾节点插入
linkLast(element);
else
//node(index) 获取当前指定的索引的节点
//在指定的索引的节点前添加元素并修改双向链表中原先的一些节点中的next和prev指针引用
linkBefore(element, node(index));
}
?
//遍历获取到指定索引位置的节点
Node<E> node(int index) {
//assert isElementIndex(index);
//对双向链表的长度右移一位并判断指定的索引位置是在双向链表的前半部分还是后半部分
if (index < (size >> 1)) {
//双向链表的前半部分
//双向链表头节点,当前遍历到的节点
Node<E> x = first;
//从双向链表的头节点开始遍历直到找到指定的索引所在的节点
for (int i = 0; i < index; i++)
//从双向链表的头节点开始获取当前遍历到的节点的下一个节点
//并将下一个节点赋予为当前遍历到的节点,以此类推直到获取到指定索引所在的节点并返回
x = x.next;
return x;
} else {
//双向链表的后半部分
//双向链表尾节点,当前遍历到的节点
Node<E> x = last;
//从双向链表的尾节点开始遍历直到找到指定的索引所在的节点
for (int i = size - 1; i > index; i--)
//从双向链表的尾节点开始获取当前遍历到的节点的上一个节点
//并将上一个节点赋予为当前遍历到的节点,以此类推直到获取到指定索引所在的节点并返回
x = x.prev;
return x;
}
}
?
//将元素e添加到succ节点的前面并修改一些指针引用
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//获取succ节点的上一个节点
final Node<E> pred = succ.prev;
//创建节点将添加的元素放置节点中
//将该节点中的next指针指向succ
//将该节点中的prev指针指向pred
//该节点插入到succ节点和pred节点的中间
final Node<E> newNode = new Node<>(pred, e, succ);
//将succ的prev指针指向新添加的节点
succ.prev = newNode;
if (pred == null)
//如果succ的上一个节点为空则说明succ原先是头节点
//将新添加的节点设置为头节点
first = newNode;
else
//将原succ的下一个节点的指针指向新添加的节点
pred.next = newNode;
//更新双向链表的长度和修改次数
size++;
modCount++;
}
示例：在索引为2的位置上插入元素18
3.将指定元素添加到双向链表的头部节点(元素添加到尾部节点的代码则是序号1中的linkLast)
public void addFirst(E e) {
linkFirst(e);
}
?
private void linkFirst(E e) {
//原头节点
final Node<E> f = first;
//创建新的节点将指定元素放置节点中并将节点中的下一个节点指针指向原头节点
final Node<E> newNode = new Node<>(null, e, f);
//将当前指定元素所在的节点设置为新的头节点
first = newNode;
if (f == null)
//原头节点为null则说明双向链表中没有节点元素
//将当前指定元素所在的节点设置为新的尾节点
last = newNode;
else
//将原头节点中的上一个节点指针指向新的头节点
f.prev = newNode;
//双向链表长度加1
size++;
//双向链表修改次数加1
modCount++;
}
4.将指定的集合元素添加到双向链表的尾部和将指定的集合元素从指定的索引位置开始添加
public boolean addAll(Collection<? extends E> c) {
//将集合元素从双向链表的尾部开始添加
return addAll(size, c);
}
//从指定的索引位置开始添加集合中的元素
public boolean addAll(int index, Collection<? extends E> c) {
//检查指定的索引是否在有效的索引位置
checkPositionIndex(index);
//获取集合中的数组对象
Object[] a = c.toArray();
//待添加的元素数量
int numNew = a.length;
if (numNew == 0)
//元素数量等于0直接返回
return false;
//定义上一个节点和当前指定的索引在双向链表中存在的节点
Node<E> pred, succ;
if (index == size) {
//index等于size则说明
//当前指定的索引在双向链表中不存在节点
succ = null;
//当前指定的索引不存在则从双向链表中的尾节点开始添加元素
pred = last;
} else {
//index不等于size
//当前指定的索引在双向链表中存在,根据指定的索引在双向链表中获取该节点
succ = node(index);
//获取指定索引的节点的上一个节点
pred = succ.prev;
}
//遍历待添加的元素集合
for (Object o : a) {
//强转成泛型
@SuppressWarnings("unchecked") E e = (E) o;
//创建新的节点并将元素添加到节点中
//并设置该节点的prev指针
//index等于size的时候,如果当前元素是集合中的第一个元素
//prev指针则指向原双向链表中的尾节点
//如果当前元素不是集合中的第一个元素则prev指针指向集合中上一个元素所在的节点
//index不等于size的时候,如果当前元素是集合中的第一个元素
//prev指针则指向双向链表中index索引所在的节点指向的上一个节点
//如果当前元素不是集合中的第一个元素则prev指针指向集合中上一个元素所在的节点
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
//上一个节点为null
//说明双向链表中没有节点则将新创建的节点设置为头节点
first = newNode;
else
//上一个节点不为null
//将上一个节点中的next指针指向新创建的节点
pred.next = newNode;
//将新创建的节点更新为上一个节点
//下一次循环创建的新节点中的prev指针则指向该节点
pred = newNode;
}
?
if (succ == null) {
//指定索引(index)的节点在双向链表中不存在
//则说明指定的元素是从双向链表的尾部开始添加的
//将指定的元素集合中的末尾元素所在的节点设置为尾节点
last = pred;
} else {
//指定索引的节点在双向链表中存在
//将指定的元素集合中的末尾元素所在的节点中的next指针指向指定的索引(index)的原节点
pred.next = succ;
//将指定的索引(index)的原节点中的prev指针指向元素集合中的末尾元素所在的节点
succ.prev = pred;
}
//更新双向链表的长度和修改次数
size += numNew;
modCount++;
return true;
}
5.获取双向链表中的头节点和尾节点元素
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
?
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
6.删除双向链表中的头节点
public E removeFirst() {
//头节点
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
//删除头节点并修改指针并返回被删除的元素
return unlinkFirst(f);
}
//删除头节点并修改指针
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//头节点中的元素
final E element = f.item;
//获取头节点next指针指向的下一个节点
final Node<E> next = f.next;
//将头节点中的元素置为null
f.item = null;
//将头节点next指针置为null
f.next = null;
//将被删除的头节点中next指针指向的下一个节点置为新的头节点
first = next;
if (next == null)
//如果被删除的头节点中next指针指向的下一个节点为null
//则说明该双向链表中将头节点删除之后则没有别的节点
//将尾节点置为null
last = null;
else
//如果被删除的头节点中next指针指向的下一个节点不为null
//则将该节点的prev指针置为null
next.prev = null;
//更新双向链表的长度和修改次数
size--;
modCount++;
//返回被删除的元素
return element;
}
7.删除双向链表中的尾节点,该方法和删除头节点的方法相似
public E removeLast() {
//尾节点
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
//删除尾节点并修改指针并返回被删除的元素
return unlinkLast(l);
}
?
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null;
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
8.删除指定元素在双向链表中第一次匹配到的节点
public boolean remove(Object o) {
if (o == null) {
//元素为null
//从头节点开始遍历
for (Node<E> x = first; x != null; x = x.next) {
//如果被遍历到的节点中的元素与待删除的元素不相同
//则将被遍历到的节点中的next指针指向的节点设置为下次待遍历的节点
if (x.item == null) {
//与指定的元素匹配
//删除该元素匹配的节点并且删除相关联的指针
unlink(x);
return true;
}
}
} else {
//元素不为null
//从头节点开始遍历
for (Node<E> x = first; x != null; x = x.next) {
//如果被遍历到的节点中的元素与待删除的元素不相同
//则将被遍历到的节点中的next指针指向的节点设置为下次待遍历的节点
if (o.equals(x.item)) {
//与指定的元素匹配
//删除该元素匹配的节点并且删除相关联的指针
unlink(x);
return true;
}
}
}
return false;
}
//删除节点并且删除相关联的指针
E unlink(Node<E> x) {
// assert x != null;
//待删除的节点中的元素
final E element = x.item;
//待删除节点的右边节点
//待删除的节点next指针指向的节点
final Node<E> next = x.next;
//待删除节点的左边节点
//待删除的节点prev指针指向的节点
final Node<E> prev = x.prev;
?
if (prev == null) {
//如果待删除节点的左边节点为null则说明待删除节点是头节点
//将待删除的节点next指针指向的节点设置为头节点(将待删除节点右边的节点设置为头节点)
first = next;
} else {
//如果待删除节点的左边节点不为null
//则将待删除节点的上一个节点的next指针指向待删除节点的下一个节点(将待删除节点的左边节点与待删除节点的右边节点关联)
prev.next = next;
//将待删除节点与左边节点取消关联
x.prev = null;
}
?
if (next == null) {
//如果待删除节点的右边节点为null则说明待删除节点是尾节点
//将待删除的节点prev指针指向的节点设置为尾节点(将待删除节点左边的节点设置为尾节点)
last = prev;
} else {
//如果待删除节点的右边节点不为null
//则将待删除节点的下一个节点的prev指针指向待删除节点的上一个节点(将待删除节点的右边节点与待删除节点的左边节点关联)
next.prev = prev;
//将待删除节点与右边节点取消关联
x.next = null;
}
//将待删除节点中的元素置为null
x.item = null;
//更新双向链表长度和修改次数
size--;
modCount++;
return element;
}
9.删除指定索引位置的节点,该方法调用的node和unlink方法可以查看序号2和序号8中的node和unlink方法代码
public E remove(int index) {
//校验索引是否是现有节点的索引
checkElementIndex(index);
//node(index) 获取指定索引位置的节点
//unlink 删除节点并且删除相关联的指针
return unlink(node(index));
}