添加元素方法
add方法详解
/*
E:创建LinkedList对象时泛型中设置好的数据类型
e: 传递的参数
boolean： 添加成功即为true，添加失败即为false
*/
public boolean add(E e) {
// 在链表最后一个结点后面插入新结点(根据待插入元素封装的结点)
linkLast(e);
// 返回true，代表添加成功
return true;
}
void linkLast(E e) {
// 声明一个新结点，将尾节点赋给l
final Node<E> l = last;
// 将数据e封装为一个新结点，用于挂载到链表上，三个参数l代表新结点的前一个结点，e新结点的数据域，null即新结点的后继结点
final Node<E> newNode = new Node<>(l, e, null);
// 新插入的结点会变成新的尾结点
last = newNode;
// 如果原来的尾结点为null,代表此前链表中一个结点都没有，此刻心插入结点又是链表的首结点
if (l == null)
first = newNode;
// 原来链表中存在结点时，新插入的结点会是原来尾结点l的后继结点
else
l.next = newNode;
// 插入成功后，链表中结点/元素的数量+1
size++;
modCount++;
}
结论： 通过插入过程，我们发现LinkedList是一个双向链表，因为数据会被封装成结点，进而挂载到双向链表
push方法详解
/**
* 添加元素
* 无返回值，参数为程序员调用push方法传递的值
*/
public void push(E e) {
addFirst(e);
}
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
// 声明一个结点f,将首结点赋给f结点
final Node<E> f = first;
// 将待添加数据封装成一个新结点，此时null为新结点的前驱结点，e为数据域，f为后继结点
final Node<E> newNode = new Node<>(null, e, f);
// 更新首结点
first = newNode;
// 如果f结点为null,代表之前首结点为null，即链表中没有结点，此刻新插入的结点也是尾结点
if (f == null)
last = newNode;
// 否则代表之前链表中有结点，将之前的首结点f的前驱结点指向新结点
else
f.prev = newNode;
// 添加后元素个数+1
size++;
modCount++;
}offer方法详解
// offer方法本质上就是add方法
public boolean offer(E e) {
return add(e);
}addAll方法详解
/**
* index:待添加元素的位置索引
* c：待添加的数据集
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 检测索引的合法性，当不合法时底层代码会抛出异常，此时程序结束
checkPositionIndex(index);
// 将数据集转换为Object类型的数组
Object[] a = c.toArray();
// 获取到数据集的长度
int numNew = a.length;
// 如果长度为0,证明你要添加的数据集是空集合，不需要添加到链表中去，返回false
if (numNew == 0)
return false;
Node<E> pred, succ;
// 如果索引为size，代表将集合c追加到链表中
if (index == size) {
// 后继结点设置为null
succ = null;
// 当前链表的尾节点设置为前驱结点
pred = last;
} else {// 将集合c插入到链表中
// 获取当前链表的index位置对应的结点 赋给succ
succ = node(index);
// 在获取succ的前驱结点赋给pred
pred = succ.prev;
}
// 遍历整个a集合
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
// 将数据o封装为新结点，新结点的前驱结点即为pred，
// e即为数据域，null是当前结点的后继结点
Node<E> newNode = new Node<>(pred, e, null);
// 如果前驱结点为null,证明链表中此时没有结点
if (pred == null)
// 新结点即为我们的首结点
first = newNode;
// 证明链表中此时有结点时
else
// pred的后继结点指向新结点
pred.next = newNode;
// pred更新为newNode
pred = newNode;
}
// 如果succ为null，代表我们是以追加的形式存放集合c中
if (succ == null) {
// 此时pred就是我们新链表的尾结点
last = pred;
} else {
// 代表随机插入的形式存放数据集c到链表，此时原来链表中index对应的结点成了pred的
// 后继结点，prev本身是集合c中的最后一个元素封装成的结点
pred.next = succ;
//原来链表中index对应的结点succ的前驱结点指向了集合c中的最后一个元素封装成的结点
succ.prev = pred;
}
// 元素个数+ 集合c中元素的个数 代表此刻LinkedList中的元素个数
size += numNew;
modCount++;
// 返回true，添加成功
return true;
}
/**
* 检测索引是否合法
*/
private void checkPositionIndex(int index) {
// 如果isPositionIndex方法返回的是false，证明索引不合法，则抛出索引越界异常
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
// 当索引>=0且索引<=size此时 我们是合法的索引 返回true，否则返回false
return index >= 0 && index <= size;
}
/**
* 获取index 位置对应的结点
*/
Node<E> node(int index) {
// 如果位置信息 小于 链表中元素个数的一半，此时从前往后遍历
if (index < (size >> 1)) {
// 获取首结点作为当前结点
Node<E> x = first;
// 从首结点开始向后遍历，index次
for (int i = 0; i < index; i++)
// 当前结点的后继结点赋给当前结点
x = x.next;
// 出来循环后即找到index位置的结点，将其返回即可
return x;
} else {
// 此时代表从后向前遍历
// 将尾节点作为当前结点
Node<E> x = last;
for (int i = size - 1; i > index; i--)
当前结点往前移动一位
x = x.prev;
// 返回index位置所对应的结点
return x;
}
/*
由此可以证明index参数本质不是索引的概念，因为索引不需要一个个的遍历
知识点拓展：索引必须在物理内存上是连续的，而链表物理内存上并不连续，只是逻辑上连续而已
*/
}
set方法详解
/**
* index:我要修改的结点位置（不是索引，链表中本质是没有索引的概念的）
* element:要修改成的新元素
*/
public E set(int index, E element) {
// 检测位置信息是否合法
checkElementIndex(index);
// 获取到index对应的结点
Node<E> x = node(index);
// 获取要被修改结点的数据域
E oldVal = x.item;
// 更新当前结点的数据域
x.item = element;
// 返回旧值
return oldVal;
}get方法详解
/**
* index:我查询的位置信息对应的数据，即链表中第index+1结点对应的数据
*/
public E get(int index) {
// 检测位置信息的合法性
checkElementIndex(index);
// 位置信息合法，获取该位置对应的node的数据域，并返回
return node(index).item;
}contains代码详解：
/**
* 查询集合中是否包含元素o,包含则返回true，不包含则返回false
*/
public boolean contains(Object o) {
// 如果元素o在链表中的位置信息为-1，说明o并不存在，否则o包含在链表之中
return indexOf(o) != -1;
}
/**
* 获取元素o对应的位置信息，o在集合中存在则返回对应的位置信息，不存在返回-1
*/
public int indexOf(Object o) {
// 初始化 位置信息的值为0
int index = 0;
// 当o为null
if (o == null) {
// 从链表的首结点开始遍历，一直到尾节点
for (Node<E> x = first; x != null; x = x.next) {
// 如果当前结点的数据域为null，则说明找到我想要的结点了
if (x.item == null)
// 返回当前结点对应的位置信息
return index;
// 没找到时index+1
index++;
}
} else {
// 从链表的首结点开始遍历，一直到尾节点
for (Node<E> x = first; x != null; x = x.next) {
// 如果当前结点的数据域为null，则说明找到我想要的结点了
if (o.equals(x.item))
return index;
// 没找到时index+1
index++;
}
}
// 整个链表都没找到，那么返回-1
return -1;
}
clear方法详解
/**
* 清理整个链表中的数据
*/
public void clear() {
// 遍历整个链表，x作为当前结点，初始化为首结点
for (Node<E> x = first; x != null; ) {
// 获取到当前结点的下一个结点
Node<E> next = x.next;
// 将当前结点的数据域、后继结点、前驱结点全设置为空，为了方便GC
x.item = null;
x.next = null;
x.prev = null;
// 将next结点设置为当前要处理的结点
x = next;
}
// 将first last结点设置null
first = last = null;
// 链表中元素个数回复为0
size = 0;
modCount++;
}