LinkedList源码学习
LinkedList 继承 抽象SequentialList、实现list接口，双端队列Deque以及克隆，因此具备列表、队列、双端队列的特性，可克隆。
1.相关变量信息
//长度为0
transient int size = 0;
//首节点
transient Node<E> first;
//尾节点
transient Node<E> last;
//节点信息包含当前节点元素，下一个元素节点、//前一个元素节点,也就是前驱和后继，//类似于c语言链表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;
}
}2.构造函数
//空参构造方法
public LinkedList() {
}
//构造一个包含指定集合元素的列表，//其顺序由集合的迭代器返回public LinkedList(Collection<? extends E> c) {
//指向空参构造
this();
//添加集合c
addAll(c);
}
其中addAll方法：
//将集合c的元素加入到列表中
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
//插入带有指定元素的集合c到list列表中public boolean addAll(int index, Collection<? extends E> c) {//检查当前位子的索引是否越界
checkPositionIndex(index);
//将带有特定元素的集合c转成数组
Object[] a = c.toArray();
//拿到数组的长度
int numNew = a.length;
//如果长度为0,返回false，不进行添加
if (numNew == 0)
return false;
//定义节点pred 前节点、succ后节点
Node<E> pred, succ;
//如果索引等于列表长度，此时说明//最后一个元素，直接添加即可， if (index == size) {
succ = null;
pred = last;
//否者，进行前驱和后继操作
} else {
//找到当前下标指向的节点，要在该节点 //前插入数据，因此令succ等于该节点。 succ = node(index);
//前节点等于succ的前驱节点
pred = succ.prev;
}
//对c.array中的元素进行遍历，并将//其元素都强转成E类型 for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;//创建一个新的节点对象，节点元素为e，//前节点为pred，后节点为null Node<E> newNode = new Node<>(pred, e, null);
//如果前节点为null,则将当前节点的//信息变为头结点信息 if (pred == null)
first = newNode;
//否者，将当前节点变成前节点的后一个节点
else
pred.next = newNode;//令当前节点作为前节点，获取下一个元素，循环 pred = newNode; }
//说明是从当前集合的末尾开始插入数据，//因此数据的最后一个元素，作为当前集合的last if (succ == null) {
last = pred;
//后节点不为null,pred为新插入的//最后一个数据，令其的后节点等于之前拆开//位置的后节点，succ为之前拆开位置//的前节点，令其前节点prev等于新插入//的元素的最后一个数据 } else {
pred.next = succ;
succ.prev = pred;
}
//由于增加了元素，因此需要增加元素的长度
size += numNew;
modCount++;
return true;}3.相关操作
(1)添加元素
头插：
//添加头结点
public void addFirst(E e) {
linkFirst(e);
}
//增加元素e为头节点元素，头插
private void linkFirst(E e) {
//f为首节点final Node<E> f = first;//创建新节点，前驱节点为null，后继节点为first节点
final Node<E> newNode = new Node<>(null, e, f);
//更新first节点
first = newNode;
//如果f节点为空，则两个节点首节点等于尾节点
// 则表示newNode = new Node<>(null, e, null);
//说明此节点是last节点
if (f == null)
last = newNode;
else
//f不为空时，则newNode = new Node<>(null, e, f); //表示头节点不为空 //而当前节点在头节点前面，因此此时e变成f的前驱节点
f.prev = newNode;
//长度自增
size++;
//修改次数自增
modCount++;
}尾插：
//添加尾元素
public void addLast(E e) {
linkLast(e);
}
//增加e作为链表的尾节点元素，尾插
void linkLast(E e) {
//将l设置为尾节点
final Node<E> l = last;
//创建新节点
final Node<E> newNode = new Node<>(l, e, null);
//将当前节点变成尾节点
last = newNode;
//如果l==null => //newNode = new Node<>(null, e, null) //因此说明此元素是头结点
if (l == null)
first = newNode;
//l不为空，在l的后面，则增加元素往l的后面插
else
l.next = newNode;
size++;
modCount++;
}尾插：
//添加元素，尾插
public boolean add(E e) {
linkLast(e);
return true;
}
//插入带有指定元素的集合c到list列表中
public boolean addAll(int index, Collection<? extends E> c) {//检查当前位子的索引是否越界
checkPositionIndex(index);
//将带有特定元素的集合c转成数组
Object[] a = c.toArray();
//拿到数组的长度
int numNew = a.length;
//如果长度为0,返回false，不进行添加
if (numNew == 0)
return false;
//定义节点pred 前节点、succ后节点
Node<E> pred, succ;
//如果索引等于列表长度，//此时说明最后一个元素，直接添加即可， if (index == size) {
succ = null;
pred = last;
//否者，进行前驱和后继操作
} else {
//找到当前下标指向的节点，要在该节点 //前插入数据，因此令succ等于该节点。 succ = node(index);
//前节点等于succ的前驱节点
pred = succ.prev;
}
//对c.array中的元素进行遍历， //并将其元素都强转成E类型 for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o; //创建一个新的节点对象，节点元素为e， //前节点为pred，后节点为null Node<E> newNode = new Node<>(pred, e, null);
//如果前节点为null,则将当前节点的信息 //变为头结点信息 if (pred == null)
first = newNode;
//否者，将当前节点变成前节点的后一个节点,//将当前节点作为前节点，获取下一个节点，循环else
pred.next = newNode; pred = newNode;
}
//说明是从当前集合的末尾开始插入数据， //因此数据的最后一个元素，作为当前集合的last if (succ == null) {
last = pred;
//后节点不为null,pred为新插入的最后一个数据， //令其的后节点等于之前拆开 // 位置的后节点，succ为之前拆开位置的前节点， //令其前节点prev等于新插入的元素的最后一个数据 } else {
pred.next = succ;
succ.prev = pred;
}
//由于增加了元素，因此需要增加元素的长度
size += numNew;
modCount++;
return true;
}中间插：
//添加指定元素
public void add(int index, E element) {
checkPositionIndex(index);
//所要添加元素等于长度，则尾插
if (index == size)
linkLast(element);
//否者之间插
else
linkBefore(element, node(index));
}
//传入元素和后节点，中间插
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//前节点是后节点的前驱节点
final Node<E> pred = succ.prev;
//创建一个新节点
final Node<E> newNode = new Node<>(pred,e,succ);
//当前节点等于后节点的前驱节点
succ.prev = newNode;
//如果前节点为null，则将新节点变成首节点即可
if (pred == null)
first = newNode;
//如果前节点不为空，则为前节点的后一个元素
else
pred.next = newNode;
size++;
modCount++;
}添加指定元素：
//将集合c的元素加入到列表中
public boolean addAll(Collection<? extends E> c){
return addAll(size, c);
}(2)删除操作，释放节点
删除头结点：
//删除头结点
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
//删除头结点信息
return unlinkFirst(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;
//长度-1
size--;
//修改次数+1
modCount++;
//返回释放的元素
return element;
}删除尾节点：
//删除尾节点
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
//删除尾节点
return unlinkLast(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;
}删除中间节点：
//删除元素
public boolean remove(Object o) {
//删除的对象不为null
if (o == null) {
//进行遍历
for(Node<E> x = first; x != null; x=x.next){
//不为null,进行移除
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for(Node<E> x = first; x != null; x=x.next){
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//释放节点
E unlink(Node<E> x) {
// assert x != null;
//获取要释放的元素
final E element = x.item;
//获取前驱节点和后继节点
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//如果前驱是空的，则说明释放元素就是 //头结点，将后面元素变成头节点 if (prev == null) {
first = next; //一个元素的情况
//如果前驱不为null,则说明当前节点有前驱节点，
// 则只需将前驱节点的next=当前节点的next，
// 同时还需要删除节点的引用，因为此时不可用
} else {
prev.next = next;
x.prev = null;
}
//如果后继为空，则前置节点成为最后一个节点
if (next == null) {
last = prev;
//后继节点不为空，则后继点击前移
//将要删除的节点的后继引用删除
} else {
next.prev = prev;
x.next = null;
}
//将要删除的元素置空，长度减1， //修改次数+1，返回要删除的节点元素 x.item = null;
size--;
modCount++;
return element;
}(3)获取get操作
获取头结点元素：
//获取头结点
public E getFirst() {
final Node<E> f = first;
//进行判空
if (f == null)
throw new NoSuchElementException();
//返回元素信息
return f.item;
}获取尾节点元素：
//获取尾节点
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}获取指定节点元素：
//获取元素
public E get(int index) {
//先检查是否越界
checkElementIndex(index);
//返回元素信息
return node(index).item;
}(4)替换操作：
//替换指定元素
public E set(int index, E element) {
//检查越界情况
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element; //替换节点元素既可
return oldVal;
}(5)返回元素的索引信息：
//返回第一次出现的索引信息
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;
}
//返回最后出现的索引信息
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for(Node<E> x = last; x != null; x=x.prev){
index--;
if (x.item == null)
return index;
}
} else {
for(Node<E> x = last; x != null; x=x.prev){
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}4.队列操作
//返回首节点元素信息
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//获取头结点元素
public E element() {
return getFirst();
}
//移除头结点
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//删除头结点
public E remove() {
return removeFirst();
}
//添加元素到队尾
public boolean offer(E e) {
return add(e);
}5.双端队列操作
//头插，添加元素
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//尾插，添加元素
public boolean offerLast(E e) {
addLast(e);
return true;
}
//返回头节点的元素
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//返回尾节点的元素
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
//删除头结点信息
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//删除尾节点信息
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}6.栈操作
//由于支持栈操作，所以支持push头部添加元素，进栈
public void push(E e) {
addFirst(e);
}
//支持栈操作，pop移除，也就是消费，出栈
public E pop() {
return removeFirst();
}7.迭代操作
//进行元素迭代
private class ListItr implements ListIterator<E>{
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index){
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
//是否进行下一次迭代
public boolean hasNext() {
return nextIndex < size;
}
//返回下一个元素
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
//下一个元素
lastReturned = next;
//下一个元素作为参考，当前元素，next元素 //的节点就是next.next next = next.next;
//nextIndex自增
nextIndex++;
return lastReturned.item;
}
//是否存在前驱元素
public boolean hasPrevious() {
return nextIndex > 0;
}
//存在前驱元素，则进行获取
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev; nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
//进行remove操作
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
//元素替换
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
//添加元素
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
//进行迭代
public void forEachRemaining(Consumer<? super E> action){ Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) { action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
//检查修改次数与期望修改此时是否相同
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}8.克隆操作
public Object clone() {
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}9.序列化操作
//将LinkedList写入流中，也就是将LinkedList保存到流中，//进行自己的个性化序列化//包括序列化数字、size、元素、节点信息
private void writeObject(java.io. ObjectOutputStream s) throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
//反序列化，从流中将LinkedList读取出来
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in size
int size = s.readInt();
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}当然JDK1.8时出现了迭代 public Spliterator<E> spliterator()，功能与迭代器类似。由于其具有队列和链表的特性，同时还可以像栈一样操作，因此我们可以知道其顺序访问的速度较快，随机访问的速度较慢，插入、删除速度快。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-02-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录