下文带/**/为源码注释//为个人注释。源代码使用这个颜色
Node对象存储元素和元素左右数据的指针
add(e)，我将我自己添加到上一个元素的Next
addFirst(e)替换链表头
addLast(e)替换链表尾
addadd(index,ele)---linkLast or linkBefore
getFirst();getLast();效率最高的两个获取
为什么说链表获取元素慢！
set(index,ele)更新元素同样需要遍历集合！
removeFirst删除并重新赋值first
removeLast删除并重新赋值Last
remove(index)四种删除情况！
remove(obj)删除指定元素的两种情况
Node对象存储元素和元素左右数据的指针
/*构建一个空列表*/
//无参构造器
public LinkedList() {}
//将要添加的元素放到Node对象中的item属性中。
//多个Node对象构成一个链表，对象中持有下一个
//和上一个Node对象
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
//当前Node对象
this.item = element;
//下一个
this.next = next;
//上一个
this.prev = prev;
}
}
/**指向最后一个节点的指针**/
transient Node<E> last;//LinkedList的成员变量
/*指向第一个节点的指针*/
transient Node<E> first;//LinkedList的成员变量
/*该列表被修改的次数*/
protected transient int modCount = 0;//LinkedList的成员变量
//当前集合的元素总个数
transient int size = 0;//LinkedList的成员变量
add(e)，我将我自己添加到上一个元素的Next
/*将指定的元素追加到列表的末尾。*/
//添加元素
public boolean add(E e) {
linkLast(e);
return true;
}
/*e作为最后一个元素。*/
void linkLast(E e) {
//先拿到列表中最后一个元素，列表是第一次添加元素是没有的
final Node<E> l = last;
//创建Node对象，将最后一个元素当成Node的prev
//传入的元素是当前Node元素，下一个不传
final Node<E> newNode = new Node<>(l, e, null);
//当前创建的Node成为最后一个元素，也就是下一个Node的prev
last = newNode;
//如果上一个为null，当链表是第一次添加元素这个是null
if (l == null)
//将新增的Node赋值到第一个节点的指向，现在来看这个值只会被赋值一次？
first = newNode;
else
//如果last不是null则表示列表内已经有元素
//一个新增加的元素其实是一个Node但是这个Node是没有next的
//这个赋值代表着，如果链表内有元素，将这个新创建的Node赋值
//给上一个Node的next
l.next = newNode;
size++;
modCount++;
}
addFirst(e)替换链表头
/*在列表的开头插入指定的元素。*/
public void addFirst(E e) {
linkFirst(e);
}
/*e作为第一个元素。*/
private void linkFirst(E e) {
//拿到first元素
final Node<E> f = first;
//创建新Node它的first是null,next是原来的first
final Node<E> newNode = new Node<>(null, e, f);
//将first指针指向新Node
first = newNode;
//如果f是null表示之前没有元素
if (f == null)
//则新添加的node同时也是last
last = newNode;
else//如果f不是null
//将新添加的Node指针赋值给原有first的prev
f.prev = newNode;
//计数器
size++;
modCount++;
}
addLast(e)替换链表尾
/*将指定的元素追加到列表的末尾。*/
public void addLast(E e) {
linkLast(e);
}
/*e作为最后一个元素。*/
void linkLast(E e) {
//拿到原来的last
final Node<E> l = last;
//创建新的Node它的prev是原来的last阿德next是null
final Node<E> newNode = new Node<>(l, e, null);
//将新创建的Node赋值给last
last = newNode;
//如果l==null表示原来没有元素
if (l == null)
//此时只有新增加的元素，所以它也是first
first = newNode;
else
//如果原来有元素，则原来的last的next为新创建的Node
l.next = newNode;
//计数器
size++;
modCount++;
}
addadd(index,ele)---linkLast or linkBefore
/*
在列表的指定位置插入指定的元素。将元素当前的位置
(如果有的话)和后续的元素向右移动(在它们的索引中添加一个)。
*/
public void add(int index, E element) {
//index只能大于=0或者小于=size,否则异常
checkPositionIndex(index);
if (index == size)
//如果index等于size表示当前做的是追加操作
linkLast(element);
else
//那这里应该是包含0的情况其实就是linkFirst()
//不清楚为啥不判断下。
//首先获取下标Node
linkBefore(element, node(index));
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/*告知参数是否是迭代器或添加操作的有效位置的索引。*/
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
/*将元素e插入到非空节点succ之前。*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//拿到下标Node的prev
final Node<E> pred = succ.prev;
//创建新的Node它的prev是succ Node的prev,它的next是succ
//简单描述新创建的元素在index的前边
final Node<E> newNode = new Node<>(pred, e, succ);
//index Node的prev指针变成了新创建的Node
succ.prev = newNode;
//原来的Node的prev如果是null表示它原来是第一个元素
//那就把新创建的Node赋值到first
if (pred == null)
first = newNode;
//原来的Node不是first则将原有Node的prev的next赋值成newNode
else
pred.next = newNode;
//计数器
size++;
modCount++;
}
getFirst();getLast();效率最高的两个获取
//第一个Node创建后，last和first都是Node1。第二个Node创建后last是Node2，还是firstNode1。
//拿到Node后获取成员item。
/*返回列表中的第一个元素。*/
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;
}
为什么说链表获取元素慢！
/*返回列表中指定位置的元素。*/
public E get(int index) {
//判断index是否合法
checkElementIndex(index);
//这是个重点方法。
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**告知参数是否为现有元素的索引。**/
private boolean isElementIndex(int index) {
//要查询的index在0和size-1之间则返回true
return index >= 0 && index < size;
}
/*返回指定元素索引处的(非空)节点。*/
Node<E> node(int index) {
//如果要查询的index小于当前size/2
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {//如果要查询的index大于当前size/2
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//这里假设LinkedList元素总个数为100，当前查询的index为49则100/2=50
//49<50，先获取集合内第一个Node,然后从0开始，每次都取Node的Next
//也就是Next代表的Node。需要循环49次才能拿到index为49的元素。
//如果当前元素为100，当前查询的index为50，则从99开始，往后循环查询
//需要循环48次。最快的两种情况是要查询第0号下标则第一个循环不满足直接
//返回first或者要查询99号下标不满足第二个循环直接返回last。但是这两
//中情况使用getFirst()或者getLast()是最快的。
set(index,ele)更新元素同样需要遍历集合！
/*将列表中指定位置的元素替换为指定元素。*/
public E set(int index, E element) {
//检验下标是否合格，上边说过这个方法。
checkElementIndex(index);
//同样需要找到对应的Node，上边说过这个方法。
Node<E> x = node(index);
//获取老的元素
E oldVal = x.item;
//新的元素替换老的元素
x.item = element;
//返回被替换的元素
return oldVal;
}
removeFirst删除并重新赋值first
/*删除并返回列表中的第一个元素。*/
public E removeFirst() {
//获取first元素
final Node<E> f = first;
if (f == null)
//如果是null表示当前集合没有元素，抛出异常
throw new NoSuchElementException();
return unlinkFirst(f);
}
/*断开第一个非空节点的链接*/
private E unlinkFirst(Node<E> f) {
//获取第一个Node的item
final E element = f.item;
//获取第一个Node的Next
final Node<E> next = f.next;
//将item置为null
f.item = null;
//将next置为null,因为first是没有prev的，所以将
//Node的ele元素和next全部置为null则代表可以
//进行垃圾回收
f.next = null; // help GC
//第一个Node被移除后它next的理应的是first
first = next;
//如果被移除的Node的next现在是first是null则表示
//当前集合没有元素则last也应当是null
if (next == null)
last = null;
//如果first被移除后集合内还有元素，则新的first的prev是null
else
next.prev = null;
//计数器操作
size--;
modCount++;
//返回被移除的元素
return element;
}
removeLast删除并重新赋值Last
/*删除并返回列表中的最后一个元素。*/
public E removeLast() {
//获取最后一个Node
final Node<E> l = last;
//如果是null抛异常
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/*解除最后一个非空节点l的链接。*/
private E unlinkLast(Node<E> l) {
//拿到last的元素
final E element = l.item;
//拿到last的上一个
final Node<E> prev = l.prev;
//断掉指针
l.item = null;
//断掉指针，等待被回收
l.prev = null; // help GC
//last被删除后它的prev理应的是新的last
last = prev;
//如果新的last是null，则表示集合内没有元素
//first置为null
if (prev == null)
first = null;
else
//顺利成为last后它失去next的指针，也就是oldNext的指针
prev.next = null;
//计数器
size--;
modCount++;
//返回被删除的元素
return element;
}
remove(index)四种删除情况！
/*
移除此列表中指定位置的元素。将后面的元素向左移动
(从它们的索引中减去1)。返回从列表中删除的元素。
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/*Unlinks non-null node x.*/
E unlink(Node<E> x) {
// assert x != null;
//需要被删除Node的元素内容
final E element = x.item;
//需要被删除Node的下一个
final Node<E> next = x.next;
//需要被删除Node的上一个
final Node<E> prev = x.prev;
//如果上一个等于null表示被删除的元素是第一个
if (prev == null) {
//则需要将被删除的Node的next赋值到first
first = next;
} else {
//如果被删除的Node不是第一个，需要将它的next
prev.next = next;
//赋值给它的prev的next。并且将它的上一个指针断掉。
x.prev = null;
}
//如果被删除的Node的next是null表示它是最后一个
if (next == null) {
//则需要将它的prev赋值到last
last = prev;
} else {
//否则表示它不是最后一个，需要将被删除的Node的prev
//转移到下一个Node的prev
next.prev = prev;
//将next指针断掉
x.next = null;
}
//将元素内容指针断掉
x.item = null;
//计数器操作
size--;
modCount++;
return element;
}
remove(obj)删除指定元素的两种情况
/*如果指定元素出现，则从列表中删除第一个出现的元素。如果此列表不包含该元素，则将对其进行更改。*/
//其实这个注释是非常不令人理解的。。。我的理解是不包含该元素则不对其进行更改
public boolean remove(Object o) {
//如果被删除的是null
if (o == null) {
//从头遍历集合，根据每一个Node的item判断是不是null
//循环结束条件是next==null
for (Node<E> x = first; x != null; x = x.next) {
//如果找到了就删除还是执行的unlink()最后返回true
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
//如果不是null照样也是从头遍历集合调用被删除元素的equals
//这意味着如果你被删除的元素和集合内其他元素的类型不同则
//可能会报错
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
//如果相同则删除并且返回true
unlink(x);
return true;
}
}
}
//最后没有满足条件的返回false删除失败
return false;
}
