1.继承的父类与实现的接口
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
2.类的属性
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
在LinkedList中,定义了如上三个属性。
int size:集合的元素数量
Node<E> first:链表的头元素
Node<E> last:链表的尾元素
3.Node类
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;
}
}
LinkedList的内部类,用以表示一个链表节点。
E item:当前元素
Node<E> next:下一个元素
Node<E> prev:上一个元素
Node(Node<E> prev, E element, Node<E> next):唯一构造函数。每创建一个节点,必须带有前一个节点
4.类的构造函数
public LinkedList() {}
LinkedList():无参构造函数。
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
LinkedList(Collection<? extends E> c):有参构造函数,参数类型为Collection<? extend E>。
由上代码可见,有参构造函数,其实是调用了无参构造函数,以及类中的addAll(Collection)方法,将参数传递进去。
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
而addAll(Collection)方法,内部又是调用了addAll(int,Collection)方法。
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); //校验index是否下标越界。
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0) //没有添加新的元素,返回false
return false;
Node<E> pred, succ; //建立前节点,后节点
if (index == size) { //index==size,说明是在当前集合的末尾插入新数据,因此没有后节点,succ=null,前节点为当前集合的最后一个节点pred=last
succ = null;
pred = last;
} else {
succ = node(index); //找到当前下标指代的节点,要在该节点前插入数据,因此令succ等于该节点。
pred = succ.prev; //pred则等于succ前面一位的节点。需要注意当index=0时,该点可以为null。
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o; //强制类型转换Object转为E
Node<E> newNode = new Node<>(pred, e, null); //创建一个新的节点,节点元素为e,前节点为pred,后节点为null。
if (pred == null) //说明index=0,因此新插入的集合的第一个元素,作为first
first = newNode;
else
pred.next = newNode; //说明index<>0,因此新的节点,作为前节点的后节点(pred.next)
pred = newNode; //令当前节点作为前节点,获取下一个元素,循环。
}
if (succ == null) { //说明是从当前集合的末尾开始插入数据,因此数据的最后一个元素,作为当前集合的last
last = pred;
} else { //pred为新插入的最后一个数据,令其的后节点等于之前拆开位置的后节点,succ为之前拆开位置的前节点,令其前节点prev等于新插入的元素的最后一个数据。
pred.next = succ;
succ.prev = pred;
}
size += numNew; //新插入numNew条数据,size增加相应的大小。
modCount++;
return true;
}
在addAll(int,Collection)方法中,首先执行checkPositionIndex(int)检验index的合法性(是否在当前对象的size范围内)。
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
5.总结
LinkedList重点在于对内部类Node<E>的理解。
每一个元素在LinkedList中都是在Node<E>中存储,每个Node<E>中同时还存储了当前元素的前节点和后节点。
新增元素或集合,只要找到添加的位置,获取该位置的前节点pred,和后节点succ,令pred.next=新插入集合的第一个元素节点,令succ.pred=新插入的集合的最后一个元素节点即可。
删除元素或集合,找到删除的位置,获取该位置的前节点pred,和后节点succ,令pred.next=succ.pred即可。
注意不论是新增还是删除,均要考虑到起始节点没有pred和结束节点没有next的问题。
每一个LinkedList对象中均只存了first和last两个节点,因此当根据索引寻找元素时,代码会判断索引是在前半部分还是后半部分,从而决定从first出发,还是从last出发。
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;
}
}
Comments | NOTHING