分类： Java
2021-06-15 17:21:07
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection c) {
//调用无参构造，其实就是个空方法
this();
//添加全部元素至LinkedList
addAll(c);
}
//addAll方法，此时对于新建的LinkedList实例，size=0
public boolean addAll(Collection c) {
return addAll(size, c);
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection c) {
//越界检查
checkPositionIndex(index);
//将Collection入参转换为数组
Object[] a = c.toArray();
//检查入参中是否包含元素，如果返回false，说明有参构造的Collection参数不包含元素
int numNew = a.length;
if (numNew == 0)
return false;
//链表节点Node
Node pred, succ;
//验证index是否==size，如果等于，则在链表last元素后追加新元素
if (index == size) {
succ = null;
pred = last;
} else {
//如不等于，则获取下标为index元素，
succ = node(index);
pred = succ.prev;
}
//循环入参中的元素
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//新建一个节点，不包含next下一节点
Node newNode = new Node<>(pred, e, null);
如果新建节点next==null，说明是头节点
if (pred == null)
first = newNode;
else
//否则，将前节点的next引用指向新建节点
pred.next = newNode;
pred = newNode;
}
//循环结束，如果传入index为链表长度，最后一次循环得到pred就是尾节点
if (succ == null) {
last = pred;
} else {
//如果index不等于size，说明是从中间插入的，最后一个元素也有下一节点
//该下一节点就是之前下标为index的元素
pred.next = succ;
succ.prev = pred;
}
//链表元素数量增加
size += numNew;
//迭代器需要用到的修改次数，若不为0，使用迭代器遍历会报错
modCount++;
return true;
}
//越界检查
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//越界检查
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
//链表中节点，包含自身引用及前后节点引用
//这样，链表中的节点便是包含前一节点和后一节点引用(除去首尾节点)
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
/**
* Returns the (non-null) Node at the specified element index.
* 返回指定位置的非空节点
* 节点如果为空
*/
Node node(int index) {
// assert isElementIndex(index);
//index大于size的一半，则从链表头部开始向下遍历处理
if (index < (size >> 1)) {
Node x = first;
//从头遍历，找到下标为index的元素（同数组的下标）
//也就是说秒如果index=4，得到的，是第五个元素
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//否则，则从链表尾部开始向上遍历处理
Node x = last;
//从尾巴节点的前节点开始找，假如size=8.index = 6.实际得到的，相当于数组中下标为7的元素
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
