LinkedList源码分析

文章目录

集合继承结构总揽

构造方法

`linkedList(Collection<? extends E> c)` 批量添加集合内容到linkedList的构造方法`linkedList()`无参构造方法 ](https://www.yuque.com/docs/share/86676521-3769-466c-8871-d38fc35f23f0?#%20%E3%80%8AlinkedList%E3%80%8B)继承自Iterable的方法

Iterator iterator() 获取迭代器 继承自Collection的方法

`add(E element)` 在集合尾部插入元素,几乎等价于linkLast(E element)`addAll(Collection<? extends E> c)` 批量添加集合元素到当前集合中`contains(Object o)` 判断集合是否包含某个元素 继承自List的方法

`set(int index, E element)` 修改元素值,同时返回原先存储的Node节点元素值`add(int index, E element)` 查找并且插入相应的元素值`addAll(int index, Collection<? extends E> c)` 批量添加集合元素到制定下标之后当前集合中(重载)`indexOf(Object o)` 获取某个元素在集合结构中的下标`listIterator()` 获取List类型的可迭代对象`listIterator(final int index)` 获取集合中某个下标值之后的List类型的可迭代对象`get(int index)` 获取当前集合中某个下标节点存储的值`remove(int index)` 删除当前集合中某个下标节点存储的值 继承自Queque的方法

`poll()` 获取并且删除集合的第一个元素`offer(E e)` 在集合尾部插入元素 继承自Deque的方法

`descendingIterator()` 获取一个可以逆序迭代的迭代器`addFirst(E element)` 在集合头部插入元素`addLast(E element)` 在集合尾部插入元素`pollFirst()` 获取并且删除集合的第一个元素`pollLast()` 获取并且删除集合的最后一个元素`peekFirst()` 获取集合的第一个元素`peekLast()` 获取集合的最后一个元素`offerFirst(E e)` 在集合头部插入元素`offerLast(E e)` 在集合尾部插入元素 其他私有方法(下标范围判断)

`checkPositionIndex(int index)` 确认当前传入的下标是否为可迭代的，否则抛出异常`isPositionIndex(int index)` 判断当前传入的下标是否为可迭代的`checkElementIndex(int index)` 确认当前传入的下标是否为越界，否则抛出异常`isElementIndex(int index)` 判断当前传入的下标是否为越界 其他私有方法(元素遍历)

`node(int index)` 根据下标来迭代获取响应的元素 其他私有方法(元素增删)

`linkFirst(E element)` 在集合头部插入元素`linkLast(E element)` 在集合尾部插入元素`linkBefore(E e, Node succ)` 在集合某个Node节点之前插入元素`unlinkFirst(E element)` 删除集合头结点`unlinkLast(Node l)` 删除集合尾节点`unlink(Node x)` 在集合中某个Node节点的值
集合继承结构总揽

兼具List的有序性和Deque的队列的特性,这个集合平常项目中使用的比较少,接着刷题的机会了解到这个数据集合,趁机来深度学习下源码知识，希望对大家可以有所帮助

public class linkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable{ //集合size属性 transient int size = 0; transient Node first; transient Node last; protected transient int modCount = 0; private static class Node { //Node节点中存储的元素值 E item; //下一个Node节点 Node next; //上一个Node节点 Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }}

构造方法 linkedList(Collection<? extends E> c) 批量添加集合内容到linkedList的构造方法

public linkedList(Collection<? extends E> c) { this(); addAll(c);}

linkedList()无参构造方法

//无参构造方法,初始化集合对象,此时初始化以后的是一个空的集合size=0public linkedList() {}

 继承自Iterable的方法 Iterator iterator() 获取迭代器

public Iterator iterator() { //调用List子集实现的方法 return listIterator();}

继承自Collection的方法 add(E element) 在集合尾部插入元素,几乎等价于linkLast(E element)

//默认在链表尾部插入数据public boolean add(E element) { linkLast(e); return true;}

addAll(Collection<? extends E> c) 批量添加集合元素到当前集合中

public boolean addAll(Collection<? extends E> c) { //默认将元素添加到当前集合的末尾,调用addALL方法时index参数设置为当前集合的size属性 //调用List子集实现的方法 return addAll(size, c);}

contains(Object o) 判断集合是否包含某个元素

public boolean contains(Object o) { //调用List子集实现的方法 return indexOf(o) != -1;}

---

继承自List的方法 set(int index, E element) 修改元素值,同时返回原先存储的Node节点元素值

//使用无参构造方法实例化linkedList后立即调用set(int index, E element)或者操作会抛出下标越界的异常IndexOutOfBoundsException,这时通不过checkPositionIndex方法的校验,因为Node节点first和last都还未实例化//该方法不改变集合结构,不对修改集合长度。设置前提是当前Node节点已经存在,public E set(int index, E element) { //判断下标是否越界 checkElementIndex(index); //循环遍历获取到响应的Node节点 Node x = node(index); E oldVal = x.item; x.item = element; return oldVal;}

add(int index, E element) 查找并且插入相应的元素值

//使用无参构造方法实例化linkedList后立即调用add(int index, E element)操作会抛出下标越界的异常IndexOutOfBoundsException,这时通不过checkPositionIndex方法的校验,因为Node节点first和last都还未实例化public E add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index));}

addAll(int index, Collection<? extends E> c) 批量添加集合元素到制定下标之后当前集合中(重载)

public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); //Collection的子集都必须实现的方法toArray() Object[] a = c.toArray(); //待添加集合的长度 int numNew = a.length; //待添加集合为空,方法终止 if (numNew == 0) return false; //定义当前待插入数据的最前置Node节点pred //和 Node pred, succ; //将目标集合的元素插入到当前集合尾部 if (index == size) { succ = null; //最前置节点Node当于当前集合的last,完成两个集合的头尾衔接 pred = last; } else { //将目标集合的元素插入到本集合中间的某个特定下标的位置 //获取当前index的Node节点,并将其赋值给succ succ = node(index); //替换当前下标值对应节点以及其之后的位置(连它一起往后,再此之前开始插入值),将当前Node.prev设置为待添加集合的pred节点 pred = succ.prev; } //循环赋值 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node newNode = new Node<>(pred, e, null); if (pred == null) //pred为空则表示原先的集合为空,直接将新建的Node设置为头节点 first = newNode; else //再pred的尾部插入新建的节点 pred.next = newNode; //把新加入的节点赋值给pred,后续的新增节点可以继续通过循环往后追加值 pred = newNode; } if (succ == null) { //根据传入index找不到数据,直接将循环以后最后一个待插入元素赋值给当前集合的last last = pred; } else { //把待插入集合最后一个元素的next和原始集合下标为index的节点串起来,双向链表接通 pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true;}

indexOf(Object o) 获取某个元素在集合结构中的下标

public int indexOf(Object o) { int index = 0; if (o == null) { //待判断元素为null,从first开始通过链表往后顺序到第一个空元素并且返回下标 for (Node x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { //如果待判断元素非空,从first开始通过链表往后顺序查找,挨个判断是否与其相等 for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1;}

listIterator() 获取List类型的可迭代对象

public ListIterator listIterator() { return listIterator(0);}

listIterator(final int index) 获取集合中某个下标值之后的List类型的可迭代对象

public ListIterator listIterator(final int index) { //这部分代码实现在其父类AbstractSequentialList的父类AbstractList中有做相关的实现 rangeCheckForAdd(index); return new ListItr(index); }

get(int index) 获取当前集合中某个下标节点存储的值

public E get(int index) { //判断下标是否越界 checkElementIndex(index); //通过node方法遍历找到传入index对应的Node,并且获取其item值 return node(index).item;}

remove(int index) 删除当前集合中某个下标节点存储的值

public E remove(int index) { //判断下标是否越界 checkElementIndex(index); //通过node方法遍历找到传入index对应的Node,然后通过unlink方法删除元素值 return unlink(node(index));}

---

继承自Queque的方法 poll() 获取并且删除集合的第一个元素

//实现上和pollFirst()一模一样public E poll() { final Node f = first; return (f == null) ? null : unlinkFirst(f);}

offer(E e) 在集合尾部插入元素

public boolean offer(E e) { return add(e);}

​

_

---

继承自Deque的方法 descendingIterator() 获取一个可以逆序迭代的迭代器

public Iterator descendingIterator() { return new DescendingIterator();}private class DescendingIterator implements Iterator { private final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); }}

addFirst(E element) 在集合头部插入元素

public void addFirst(E e) { linkFirst(e);}

addLast(E element) 在集合尾部插入元素

public void addLast(E e) { linkLast(e);}

pollFirst() 获取并且删除集合的第一个元素

public E pollFirst() { final Node f = first; return (f == null) ? null : unlinkFirst(f);}

pollLast() 获取并且删除集合的最后一个元素

public E pollLast() { final Node l = last; return (l == null) ? null : unlinkLast(l);}

peekFirst() 获取集合的第一个元素

public E peekFirst() { final Node f = first; return (f == null) ? null : f.item;}

peekLast() 获取集合的最后一个元素

public E peekLast() { final Node l = last; return (l == null) ? null : l.item;}

offerFirst(E e) 在集合头部插入元素

public boolean offerFirst(E e) { addFirst(e); return true;}

offerLast(E e) 在集合尾部插入元素

public boolean offerLast(E e) { addLast(e); return true;}

---

其他私有方法(下标范围判断) checkPositionIndex(int index) 确认当前传入的下标是否为可迭代的，否则抛出异常

private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

isPositionIndex(int index) 判断当前传入的下标是否为可迭代的

判断当前传入的下表是否为可迭代的, 可选范围是0<= index <= size 在链表的迭代器(Iterator)里,双向Queue(Deque)中可以正向、反向的迭代,所以index的可选范围对比数组是要大一点

private boolean isPositionIndex(int index) { return index >= 0 && index <= size;}

checkElementIndex(int index) 确认当前传入的下标是否为越界，否则抛出异常

private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

isElementIndex(int index) 判断当前传入的下标是否为越界

private boolean isElementIndex(int index) { return index >= 0 && index < size;}

其他私有方法(元素遍历) node(int index) 根据下标来迭代获取响应的元素

Node node(int index) { //这一步判断目前都 // assert isElementIndex(index); //size >> 1 在未超出数据类型限制的情况下,右移1尾效果等价于/2 //因为linkedList实现的是Deque(双向队列) // 因此如果 index < size/2 时考虑从头fisrt开始正序遍历 // 因此如果 index >= size/2 时考虑从头last开始反序遍历 if (index < (size >> 1)) { Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; }}

其他私有方法(元素增删) linkFirst(E element) 在集合头部插入元素

private void linkFirst(E e) { final Node f = first; final Node newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++;}

linkLast(E element) 在集合尾部插入元素

void linkLast(E e) { final Node l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++;}

linkBefore(E e, Node succ) 在集合某个Node节点之前插入元素

void linkBefore(E e, Node succ) { // assert succ != null; //待插入集合的头指向相应Node节点 final Node pred = succ.prev; //创建待插入节点 final Node newNode = new Node<>(pred, e, succ); //相应节点succ的双向链补全指向待插入节点 succ.prev = newNode; if (pred == null) //如果相应节点为空,则将待插入元素设置成集合的头节点,如果原先集合有内容,这一顿操作就会造成链表断裂 first = newNode; else //双向链表闭环,将当前节点succ的前置节点的next设置为新插入的节点 pred.next = newNode; size++; modCount++;}

unlinkFirst(E element) 删除集合头结点

//该方法仅有两处被调用的地方,分别是pollFirst()和poll(),都是需要拿到集合的头节点并且删除头节点的操作private E unlinkFirst(Node f) { // assert f == first && f != null; //获取当前待删除Node存储的数据值,用于完成方法后返回 final E element = f.item; //获取到当前待删除Node的下一个节点,用于替换当前节点 final Node next = f.next; //清理当前Node的相关信息,等待GC回收 f.item = null; f.next = null; // help GC //将当前待删除Node的下一个节点赋值给集合的first节点 first = next; if (next == null) //nextNode为空标志当前集合为空,上面删除的是集合中的唯一元素 last = null; else //集合不为空时,将集合的头节点的prev斩断,如果不执行这一步,头节点的prev还是指向待删除的但是内容已经清空的这个节点 //个人觉得这里的代码写成first.prev=null可读性会更好 next.prev = null; size--; modCount++; return element;}

unlinkLast(Node l) 删除集合尾节点

//代码逻辑和unlinkFirst类似,只是需要逆向处理private E unlinkLast(Node l) { // assert l == last && l != null; final E element = l.item; final Node 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;}

unlink(Node x) 在集合中某个Node节点的值

//简单的说就是剪短旧链 让x.pref.next=x.next x.next.pref=x.prefE unlink(Node x) { // assert x != null; final E element = x.item; final Node next = x.next; final Node 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;}