写在前面
本文是针对JDK版本1.8的，可能与其他版本有出入。
全局变量
transient int size = 0; //结点个数
transient Node<E> first; //头结点
transient Node<E> last; //尾结点
元素的存储结构
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;
}
}
构造方法
1.无参构造
public LinkedList() {
}
2.有参构造
public LinkedList(Collection<? extends E> c) {
this(); //调用无参构造
addAll(c); //将c中的元素都添加到链表中
}
//此时size==0，size就是链表的结点个数
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
//构造方法调用此方法理解：从下标为0处开始，将c集合中的元素全添加到链表中
//方法理解：将c集合插入到指定下标index之前
public boolean addAll(int index, Collection<? extends E> c) {
//检查位置是否合法，合法位置区间[0，size]
checkPositionIndex(index);
//将c转换成数组
Object[] a = c.toArray();
int numNew = a.length; //c中的元素个数
if (numNew == 0) //c中无元素
return false;
//通过if-else确定前驱、后继结点
Node<E> pred, succ; //前驱(precursor)、后继(successor)结点
if (index == size) { //从尾结点开始添加元素
succ = null; //此情况无后继结点
pred = last; //有前驱结点为尾结点last
} else { //否则就从中间或者从头结点开始添加元素
succ = node(index); //后继为第index结点元素
pred = succ.prev; //前驱为后继的前驱
}
//循环a数组元素
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//新建一个前驱为pred，值为e，后继为null的结点
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null) //前驱为空，说明index是第一个结点的下标，此链表为空链表
first = newNode; //新建的结点就为头结点
else
pred.next = newNode; //赋值给前驱的后继
pred = newNode; //刷新前驱，以便继续插入结点
}
if (succ == null) { //此情况说明index的值不在(0,size-1)之间
last = pred; //集合c的最后一个元素为链表的尾结点
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew; //更新结点个数
modCount++; //修改次数+1
return true;
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
//判断位置是否在[0,size]之间
return index >= 0 && index <= size;
}
//获取指定index的结点
//思想和折半查询差不多
//判断下标和总长度的一半比较，小就从左边扫描，大就从右边扫描
Node<E> node(int index) {
// assert isElementIndex(index);
//size>>1 位操作，相当于size/2
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;
}
}
其他方法
1.linkFirst(E e)
说明： 添加的e元素作为链表的第一个结点
private void linkFirst(E e) {
final Node<E> f = first; //头结点
//新建一个前驱为null，值为e，后继为原头结点的结点
final Node<E> newNode = new Node<>(null, e, f);
first = newNode; //更新头结点为新建结点
if (f == null) //如果原头结点为null，说明链表为空链表
last = newNode;
else
f.prev = newNode; //原头结点的前驱为新建结点
size++; //结点个数+1
modCount++; //修改次数+1
}
2.linkLast(E e)
说明： 添加的e元素作为链表的最后一个结点
//此方法和linkFirst方法类似
void linkLast(E e) {
final Node<E> l = last; //尾结点
//新建一个前驱为原尾结点，值为e，后继为null的结点
final Node<E> newNode = new Node<>(l, e, null);
last = newNode; //更新尾结点为新建结点
if (l == null) //尾结点为null和头结点为null一样，都是说明链表为空链表
first = newNode;
else
l.next = newNode; //原尾结点的后继为新建结点
size++; //结点个数+1
modCount++; //修改次数+1
}
3.linkBefore(E e, Node succ)
说明： 将添加的e元素插入到结点succ前
//此方法和addAll(int index, Collection<? extends E> c)有相似之处
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev; //得到succ的前驱
//创建一个前驱为pred，值为e，后继为succ的结点
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode; //更新succ的前驱为新建结点
if (pred == null) //前驱若为null，说明succ为头结点
first = newNode;
else
pred.next = newNode; //更新succ前驱的后继为新建结点
size++; //结点个数+1
modCount++; //修改次数+1
}
4.add方法
说明： 添加一个元素e，基本上是调用写好的方法
public boolean add(E e) {
linkLast(e); //将元素e添加到链表的最后
return true;
}
//添加元素到指定位置
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size) //添加到最后一个结点
linkLast(element);
else //添加到index位置
linkBefore(element, node(index));
}
5.unlinkFirst(Node f)
说明： 删除首结点
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//传入的结点必须是首结点而且不能为空
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--; //元素个数-1
modCount++;
return element;
}
6.unlinkLast(Node l)
说明： 删除尾结点
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
//传入的结点必须是尾结点而且不能为空
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;
}
7. unlink(Node x)
说明： 删除某个非空结点
//这个方法有一点需要注意
//在判断x的前驱是否为空的时候，做的操作也只有更新前驱的值或者前驱的后继而已，此时不能更新后继的前驱，因为后继不能确定是否为空
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item; //保存删除结点的元素值
final Node<E> next = x.next; //x的后继
final Node<E> prev = x.prev; //x的前驱
if (prev == null) { //前驱为空，说明x是头结点
first = next;
} else {
prev.next = next; //更新x的前驱的后继
x.prev = null; //x为被删除结点，已无前驱，所以置空
}
if (next == null) { //后继为空，说明x是尾结点
last = prev;
} else {
next.prev = prev; //更新x的后继的前驱
x.next = null; //同理，将x后继置空
}
x.item = null; //值置空
size--;
modCount++;
return element; //返回被删除的结点的值
}
8.remove方法
说明： 根据不同条件删除一个结点
//删除第一个结点
public E removeFirst() {
final Node<E> f = first;
if (f == null) //说明为链表为空
throw new NoSuchElementException();
return unlinkFirst(f); //调用写好的方法
}
//删除最后一个结点
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
//遍历链表，找到相同的元素值并且删除该结点
public boolean remove(Object o) {
if (o == null) { //值为null
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) { //找到元素值为null的结点
unlink(x); //注意：unlink方法是不能删除结点为空的，而不是不能删除结点中元素值为空的结点
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//删除指定index的结点
public E remove(int index) {
//判断index是否合法，合法区间在[0,size)
checkElementIndex(index);
return unlink(node(index));
}
9.set(int index, E element)
说明： 修改指定index的结点的元素值
public E set(int index, E element) {
//判断index是否合法
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item; //得到旧的元素值
x.item = element; //更新元素值
return oldVal; //返回旧的元素值
}
10.get(int index)
说明： 得到指定index的结点
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
11.indexOf(Object o)
说明： 获取元素的下标
//和remove方法相似
//成功放回下标，失败返回-1
//还有一个方法是lastIndexOf(Object o)，两方法只是遍历方向不同，就不赘述了
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
12.contains(Object o)
说明： 判断链表中是否包含元素o
//调用indexOf方法
public boolean contains(Object o) {
return indexOf(o) != -1;
}
13.clear()
说明： 清除该链表
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
//遍历链表，将每个节点的前驱、值、后继都置空
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
14.其他
/**
* Tells if the argument is the index of an existing element.
*/
//告知参数是否为现有元素的索引
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
/**
* Tells if the argument is the index of a valid position for an
* iterator or an add operation.
*/
//告知参数是否是迭代器或添加操作的有效位置的索引
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
总结
LinkedList底层为双向链表，不必保证内存上的连续，所以增删快，而查询时必须要经历从头到尾的遍历，所以查询慢。
最后
感谢你看到这里，文章有什么不足还请指正，觉得文章对你有帮助的话记得给我点个赞，每天都会分享java相关技术文章或行业资讯，欢迎大家关注和转发文章！
网友评论