JDK源码阅读--LinkedList
2024-09-30 23:46:50
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable 继承了bstractSequentialList类，实现了List、Deque、Cloneable、Serializable接口。
底层数据结构是链表，增删快，查询慢。先进后出，双向链表。重写了clone方法(只是浅拷贝，不会克隆链表中的元素)。添加的元素是可以重复的。 字段和构造方法：
//被transient修饰的字段，不会被加入序列化
transient int size = 0; /**
* Pointer to first node.第一个节点的指针
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first; /**
* Pointer to last node. 指向最后一个节点的指针
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last; /**
* 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<? extends E> c) {
this();
addAll(c);
}
LinkedList数据结构中链表的本质操作：
/**
* Links e as first element.
* 链接e作为第一个元素
*/
private void linkFirst(E e) {
//first原先是一个空的节点
final Node<E> f = first;//first:第一个节点的指针
/**
* Node(Node<E> prev, E element, Node<E> next)
* @param prev 前一个节点 也叫前置节点
* @param element 当前节点上的元素
* @param next 下一个节点 也叫后置节点
*/
//创建一个没有前置节点，并且当前节点的值为e，并且后置节点为f的节点Node
final Node<E> newNode = new Node<>(null, e, f);
//将创建的newNode节点赋给第一个节点的指针first
first = newNode;
//如果后置节点为空，则也将newNode赋给最后一个节点的指针last;如果后置节点不为空，则将newNode作为 后置节点的前置节点，从而让链表连接起来
if (f == null) {
last = newNode;
}
else {
f.prev = newNode;
}
size++;//链表的长度+1
modCount++;//链表被修改的次数+1
} /**
* Links e as last element.
* 链接e作为最后一个元素
*/
void linkLast(E e) {
final Node<E> l = last;//last:最后一个节点的指针
/**
* Node(Node<E> prev, E element, Node<E> next)
* @param prev 前一个节点
* @param element 当前节点上的元素
* @param next 下一个节点
*/
//创建一个没有后置节点，前置节点为l，当前节点指针指向的值为e的节点newNode
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) {
//如果前置节点为空，则将该节点作为第一个节点的指针
first = newNode;
}
else {
//如果前置节点不为空，则将newNode作为 前置节点的的后置节点
l.next = newNode;
}
size++;//链表的长度+1
modCount++;//链表被修改的次数+1
} /**
* 在非空节点succ之前插入节点e
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//获取节点succ原先的前置节点
final Node<E> pred = succ.prev;
//创建一个节点newNode，该节点的前置节点为 节点succ的前置节点，该节点的后置节点为succ
final Node<E> newNode = new Node<>(pred, e, succ);
//将succ节点的前置节点指向newNode节点
succ.prev = newNode;
if (pred == null) {
//如果succ节点原先的前置节点为空，则说明succ节点是第一个节点，则将newNode节点设置为第一个节点
first = newNode;
} else {
//如果succ节点原先的前置节点不为空，则将newNode节点作为succ节点的 原先的节点 的后置节点。
pred.next = newNode;
}
size++;//链表的长度+1
modCount++;//链表被修改的次数+1
} /**
* Unlinks non-null first node f.
* 断开非空第一个节点f的链接。断开之后变成两个链表了。
* 从节点f的右侧断开。
* 从节点f的位置开始断开，并将节点f指针指向的值设置为空，并且将节点f的后置节点设置为空。
* 返回节点f指针指向的值。
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
//获取节点f原先的后置节点
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
//将节点f原先的后置节点作为第一个节点(的指针)
first = next;
if (next == null) {
//如果节点f原先的后置节点为null，说明节点f原先就是最后一个节点，将最后一个节点置为null。
last = null;
}else {
//如果节点f原先的后置节点不为null，则将节点f原先的后置节点的 前置节点置为null,从而让链表断开。
next.prev = null;
}
size--;//链表的长度+1
modCount++;//链表被修改的次数+1
return element;
} /**
* Unlinks non-null last node l.
* 断开非空的最后一个节点l。
* 从节点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;
} /**
* Unlinks non-null node x.
* 断开非空节点x的链接。相当于去掉节点x
*/
E unlink(Node<E> x) {
// assert x != null;
//节点x的指针所指向的值
final E element = x.item;
//节点x的后置节点
final Node<E> next = x.next;
//节点x的后置节点
final Node<E> prev = x.prev; if (prev == null) {
//如果节点x原先的前置节点为空，则说明节点x就是第一个节点，则将节点x原先的后置节点作为第一个节点
first = next;
} else {
//如果节点x原先的前置节点不为空，则将节点x的后置节点 作为 节点x原先的前置节点的 后置节点，并将节点x的前置节点置为null
prev.next = next;
x.prev = null;
} if (next == null) {
//如果节点x原先的后置节点为空，说明节点x就是最后一个元素，则将节点x原先的前置节点作为最后一个节点
last = prev;
} else {
//如果节点x原先的后置节点不为空，则将节点x原先的前置节点作为 节点x原先后置节点的 前置节点，将节点x的后置节点置为null
next.prev = prev;
x.next = null;
} x.item = null;//将节点x指针所指向的值 置为null
size--;//链表长度-1
modCount++;//链表被修改次数+1
return element;//返回节点x原先指针所指向的值
}
/**
* 静态 类 Node<E> 节点 这个类作为节点Node
* @param <E>
*/
private static class Node<E> {
E item;//当前节点的的指针指向的值
Node<E> next;//下一个节点的指针
Node<E> prev;//前一个节点的指针 /**
* 构造方法 Node(Node<E> prev, E element, Node<E> next)
* @param prev 前一个节点
* @param element 当前节点(指针)上的元素
* @param next 下一个节点
*/
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;//将element赋值给当前节点item 将element作为为当前节点的指针指向的值
this.next = next;//将next赋给下一个节点 为后置节点初始化
this.prev = prev;//将prev赋给前一个节点 为前置节点初始化
}
}
添加：
/**
* Inserts the specified element at the beginning of this list.
* 在链表的开始处插入元素e
* @param e 被插入的元素e
*/
public void addFirst(E e) {
linkFirst(e);
} /**
* Appends the specified element to the end of this list.
* 在链表的末尾追加元素e
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
*/
public void addLast(E e) {
linkLast(e);
} /**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the specified
* collection's iterator. The behavior of this operation is undefined if
* the specified collection is modified while the operation is in
* progress. (Note that this will occur if the specified collection is
* this list, and it's nonempty.)
*
* @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 NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> 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<? extends E> c) {
checkPositionIndex(index); Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false; 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;
} else {
pred.next = succ;
succ.prev = pred;
} size += numNew;
modCount++;
return true;
}
删除：
/**
* Removes and returns the first element from this list. 移除第一个元素
*
* @return the first element from this list 返回被移除的第一个元素
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
} /**
* Removes and returns the last element from this list. 移除最后一个元素
*
* @return the last element from this list 返回被移除的第一个元素
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
} /**
* Removes all of the elements from this list.
* 清空链表中的所有元素(也就是清空链表中的所有节点(节点的item、next、prev))
* The list will be empty after this call returns.
*/
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++;
}
/**
* Removes and returns the first element from this list. 移除第一个元素
*
* @return the first element from this list 返回被移除的第一个元素
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
} /**
* Removes and returns the last element from this list. 移除最后一个元素
*
* @return the last element from this list 返回被移除的第一个元素
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
查询：
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return 返回链表中指定索引位置的元素 the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;//返回指定节点指针所指向的值
}
/**
* Returns the (non-null) Node at the specified element index.返回指定元素索引处的(非空)节点。
*/
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
/**
* Returns the first element in this list.
* 返回LinkedList中的第一个节点的指针所指向的值。
*
* @return 返回LinkedList中的第一个元素。
* @throws NoSuchElementException 如果这个链表为空，则抛出这个异常
*/
public E getFirst() {
final Node<E> f = first;
if (f == null) {
throw new NoSuchElementException();
}
return f.item;//返回第一个节点的指针所指向的值
} /**
* Returns the last element in this list.
*
* @return 返回LinkedList中的最后一个节点的指针所指向的值。
* @throws NoSuchElementException if this list is empty
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;//返回最后一个节点的指针所指向的值
}
LinkedList作为堆栈的时候：
/**
* Pushes an element onto the stack represented by this list. In other
* words, inserts the element at the front of this list.
* 将元素推入此列表所表示的堆栈。换句话说，就是在此链表的开头插入元素
* <p>This method is equivalent to {@link #addFirst}.
*
* @param e the element to push
* @since 1.6
*/
public void push(E e) {
addFirst(e);
} /**
* Pops an element from the stack represented by this list. In other
* words, removes and returns the first element of this list.
* 从这个列表表示的堆栈中弹出一个元素，换句话说，就是移除并返回此列表的第一个元素。
* <p>This method is equivalent to {@link #removeFirst()}.
*
* @return the element at the front of this list (which is the top
* of the stack represented by this list)
* @throws NoSuchElementException if this list is empty
* @since 1.6
*/
public E pop() {
return removeFirst();
}
set方法：替换元素
/**
* Replaces the element at the specified position in this list with the
* specified element.
* 将列表中指定位置的元素替换为指定元素。
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
将LinkedList转为数组：
/**
*
* @return 返回链表中按照顺序排列的一个数组
*/
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
//遍历链表中的所有节点，并且将节点所指向的值存放到数组中
for (Node<E> x = first; x != null; x = x.next) {
result[i++] = x.item;
}
return result;
}
序列化和反序列化：
/**
* Saves the state of this {@code LinkedList} instance to a stream (that is, serializes it).
* 将链表的实例状态保存到一个流中。也就是将链表序列化成一个流。
* @serialData The size of the list (the number of elements it
* contains) is emitted (int), followed by all of its
* elements (each an Object) in the proper order.
*/
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);
} /**
* Reconstitutes this {@code LinkedList} instance from a stream (that is, deserializes it).
* 从流中重新构造这个实例。也就是将 流反序列化成链表(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());
}
最新文章
- UML基本介绍
- BZOJ3697: 采药人的路径
- CSS3实现元素旋转
- HTML布局与框架
- NoSQL聚合数据模型
- java 中 java.lang.ArrayIndexOutOfBoundsException: 0 异常
- [shell基础]——join命令
- 理解dojo.require机制
- element的height与width
- .Neter玩转Linux系列之二：Linux下的文件目录及文件目录的权限
- js 可拖动div 调整大小
- JDK安装与配置（Windows 7系统）
- Linux内核分析— —扒开系统调用的三层皮（下）
- Ubuntu软件操作的相关命令
- git查看各个branch之间的关系图
- Codeforces Round #418 (Div. 2)D
- JavaScript数据结构-1.数组
- PAT甲级1018. Public Bike Management
- 笔试面试的路上——努力ing
- ecliplse导入tomcat