LinkedList详解
原文链接http://zhhll.icu/2021/01/04/java%E5%9F%BA%E7%A1%80/%E9%9B%86%E5%90%88/LinkedList%E8%AF%A6%E8%A7%A3/
LinkedList详解
LinkedList是List接口的一个主要的实现类之一。以java8为例来了解一下LinkedList的源码实现
继承关系
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
继承了AbstractSequentialList，实现了List接口、Deque接口、Cloneable接口、Serializable接口
关键变量
/*** 链表的长度*/transient int size = 0;/** * 头节点 * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */transient Node<E> first;/** * 尾结点 * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */transient Node<E> last;// 这里用到了一个内部类Node，看到Node的结构就知道是一个双向链表了，保存了前驱节点和后继节点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 LinkedList() {}/** * 传入一个集合作为参数 */public LinkedList(Collection<? extends E> c) { this(); addAll(c);}public boolean addAll(Collection<? extends E> c) { return addAll(size, c);}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; // index == size时表示是从链表尾部添加元素，所以前置节点为当前链表的尾结点 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); // 前置节点为null，表示这是头节点 if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; }// succ == null,说明是从尾部添加的，将最后一个节点赋给尾结点 if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true;}// 获取index位置的节点Node<E> node(int index) { // assert isElementIndex(index);// index小于链表长度的一半，从链表头部开始遍历 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // index不小于链表长度的一半，从链表尾部开始遍历 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; }}
add方法
// 逻辑比较简单，与上边addAll类似，一通插public void add(int index, E element) { checkPositionIndex(index);// index == size表示在链表尾部添加 if (index == size) linkLast(element); else // 否则在中间插入 先找到index所在位置的节点 linkBefore(element, node(index));}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++;}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; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++;}
remove方法
LinkedList的remove方法比较
public E remove(int index) { // 检测该索引位置是否符合要求 index >= 0 && index < size checkElementIndex(index); return unlink(node(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; }}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;// 前驱节点为null，表示为头节点，头节点指向后继节点即可 if (prev == null) { first = next; } else { // 前驱节点的后继节点指向该元素的后继节点 prev.next = next; x.prev = null; }// 后继节点为null，表示为尾节点，尾节点指向前驱节点即可 if (next == null) { last = prev; } else { // 后继节点的前驱节点指向该元素的前驱节点 next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element;}
迭代器
LinkedList使用的迭代器是其父类AbstractSequentialList中的iterator方法
// AbstractSequentialList类方法public Iterator<E> iterator() { return listIterator();}// LinkedList类方法public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index);}// 与ArrayList的迭代器不同的是，ArrayList的迭代器实现的是Iterator接口 而LinkedList为ListIterator接口，相当于ArrayList的listIterator()方法// Iterator只能向前遍历，ListIterator可以向前也可以向后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; 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; } 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(); }}
由于本身的博客百度没有收录，博客地址http://zhhll.icu
赞 (0)