继承关系
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
//类内代码
}
继承AbstractSequentialList抽象类（获取对象，迭代器迭代对象等）
实现List接口
实现Cloneable（支持克隆）
实现Deque(双向队列)
实现Serializable（支持序列化 readObject（ObjectInputStream o）、writeObject（ObjectOutputStream o））
组成
主要属性
//长度
transient int size = 0;
//第一个结点
transient Node<E> first;
//最后一个结点
transient Node<E> last;
构造方法
//无参构造器
public LinkedList() {}
//默认初始化数据构造器
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
主要内部类
//链表整体是以Node为基础构建的，一个Node相当于一个结点，一个结点相当于一个LinkedList的一个元素
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;
}
}
主要方法
/**
*增加一个集合到指定位置
*/
public boolean addAll(int index, Collection<? extends E> c) {
//下标位置检查 return index >= 0 && index <= size;
checkPositionIndex(index);
//将集合转化为数组
Object[] a = c.toArray();
//新添加集合的长度
int numNew = a.length;
if (numNew == 0)
//为空的话直接返回
return false;
//定义待添加结点的位置succ
//定义待添加结点位置的前一个结点位置pred
Node<E> pred, succ;
if (index == size) {//如果从集合最后位置开始添加
//待添加结点位置为空
succ = null;
//待添加结点前一个结点为原始集合最后一个结点
pred = last;
} else {//添加位置非原始集合的最后一个位置
//寻找待添加结点位置（后面解析这个方法）
succ = node(index);
//待添加结点位置的前一个结点
pred = succ.prev;
}
//循环待添加数组
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//创建一个结点
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)//如果原始集合为空
first = newNode;//第一个结点为新添加的第一个结点
else //原始集合不为空
pred.next = newNode; //待添加结点的下一个结点为待添加结点
pred = newNode;//将待添加结点指向新的结点，以便于后面继续添加
}
if (succ == null) {//在集合尾部进行添加
last = pred;//集合最后一个结点为上面循环完最后pred的位置
} else {//在原始集合非尾部添加
pred.next = succ;//将最后一个数组元素的下一个结点指向添加第一个待添加位置
succ.prev = pred;//将第一个待添加位置的结点的前一个结点指向循环完数组的最后一个结点
}
size += numNew;//将集合长度累计
modCount++;//累计修改次数
return true;
}
/**
*根据下标查找一个node
*/
Node<E> node(int 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;
}
}
/**
*在最后面添加添加
*/
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)//原始链表为空，第一个结点指向新结点
first = newNode;
else
l.next = newNode;//原始链表不为空，最后一个结点指向新结点
size++;//链表长度累计
modCount++;//修改次数累计
}
/**
*在指定位置添加
*/
public void add(int index, E element) {
checkPositionIndex(index);//检查下标越界问题
if (index == size)//在尾部添加，参考上面方法
linkLast(element);
else
linkBefore(element, node(index));//非尾部添加参考下面方法
}
/**
*在指定位置添加
*e：添加值
*succ：待添加位置结点
*/
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;//待添加位置的上一个结点pred
final Node<E> newNode = new Node<>(pred, e, succ);//创建结点
succ.prev = newNode;//待添加位置当前结点的前驱指针指向新结点
if (pred == null)//初始链表为空，第一个结点为新结点
first = newNode;
else
pred.next = newNode;//初始链表不为空
size++;
modCount++;
}
/**
*获取
*/
public E get(int index) {
checkElementIndex(index);//检查下表越界问题
return node(index).item;//获取值（看前面node方法）
}
/**
*remove的几个方法，思路都一样就不一一注释了（都是修改指针关系）
*unlink:删除指定结点
*unlinkLast:删除最后一个结点
*/
E unlink(Node<E> x) {//删除指定结点
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
private E unlinkLast(Node<E> l) {//删除最后一个结点(直接清空结点信息，然后将上一个结点的后继指针指向空)
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
private E unlinkFirst(Node<E> f) {//删除第一个结点
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
总结
LinkedList里面所有的操作都是依赖指针的修改，需要格外注意越界和判空问题，它本身提供的几个方法都是依赖linkFirst，linkLast，linkBefore，unlinkFirst，unlinkLast，unlink几个核心方法展开的，只需要掌握这几个方法其他的方法就一通百通了。
网友评论