1、LinkedList-底层使用数组实现
1、LinkedList 是一个继承于AbstractSequentialList的双向链表。
1-1、AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些函数。这些接口都是随机访问List的。
1-2、若需要通过AbstractSequentialList自己实现一个列表,只需要扩展此类,并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表,则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。
2、存储的数据结构是链表:
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
//(集合中)双向链表中节点的个数。
transient int size = 0;
/**
* Pointer to first node.
* 头节点 first
* 头节点 first 的 prev = null
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* 尾节点 last
* 尾节点 last 的 next = null
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
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;
}
}
}
2、LinkedList-构造方法
1、LinkedList提供了两种方式的构造器:
//构造一个空的LinkedList
public LinkedList() {
}
//接收一个Collection参数c,默认构造方法构造一个空的链表,并通过addAll将c中的元素全部添加到链表中。
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
2、所以我们构建LinkedList实例是可以:
LinkedList<E> list = new LinkedList<E>(); // 普通创建方法
==>
LinkedList<E> list = new LinkedList(Collection<? extends E> c); // 使用集合创建链表
3、LinkedList-内部方法
1、LinkedList-关键的几个内部方法(头部添加删除,尾部添加删除,获取指定节点,指定节点的添加删除),时间复杂度为O(1)
//节点是一个双向节点,私有的静态内部类
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;
}
}
/**
* Links e as first element.
* e作为第一个元素,即该元素插入到头部[作为头节点]
* 所有的遍历都是从这两个节点开始的
*/
private void linkFirst(E e) {
//获取头节点
final Node<E> f = first;
//新建一个节点,新节点的前指针指向null,尾指针指向之前的头元素first[看构造器方法]
final Node<E> newNode = new Node<>(null, e, f);
first = newNode; //头节点的next指针指向新建的节点
//如果头节点是空的,则说明是空列表,新建的节点作为头节点,则将last节点的next修改指向新建的节点
if (f == null)
last = newNode;
else
f.prev = newNode;//原来的头节点的前指针指向新建的节点
size++;
modCount++;
}
/**
* Links e as last element.
* e作为最后一个元素,即该元素插入到尾部[作为尾节点]
* 所有的遍历都是从这两个节点开始的
*/
void linkLast(E e) {
//获取尾节点
final Node<E> l = last;
//新建一个节点,新节点的尾指针指向null,前指针指向之前的尾元素last[看构造器方法]
final Node<E> newNode = new Node<>(l, e, null);
//将尾节点的next指针指向新建的节点
last = newNode;
if (l == null)
first = newNode; //为空时就说明此链表中没有数据,头结点也变更为新增的节点
else
l.next = newNode; //原来的尾节点变为倒数第2个,原理尾节点后驱指向新增的节点
size++;
modCount++;
}
/**
* Inserts element e before non-null Node succ.
* 在 非空的指定节点 前面插入一个元素,这里假设 指定节点不为 null。
* @param e 需要插入的元素
* @param succ 指定的节点
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 获取指定节点 succ 前面的一个节点
final Node<E> pred = succ.prev;
//新建一个节点,头部指向 succ 前面的节点,尾部指向 succ 节点,数据为 e
final Node<E> newNode = new Node<>(pred, e, succ);
//让 succ 节点头部指向 新建的节点
succ.prev = newNode;
if (pred == null)
first = newNode;//如果 succ 前面的节点为空,说明 succ 就是第一个节点,那现在新建的节点就变成第一个节点了
else
pred.next = newNode;//如果前面有节点,让前面的节点后指针指向新建节点
size++;
modCount++;
}
/**
* Unlinks non-null first node f.
* 删除头节点(Node<E> f)并返回该节点上的数据,假设不为 null
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//获取数据,一会儿返回,假设不为 null。
final E element = f.item;
//获取头节点后面的一个节点
final Node<E> next = f.next;
//使头节点上数据为空,尾部指向空
f.item = null;
f.next = null; // help GC
//现在头节点后边的节点变成第一个了
first = next;
//如果头节点后面的节点为 null,说明移除这个节点后,链表里没节点了
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
/**
* Unlinks non-null last node l.
* 删除尾部节点(Node<E> l)并返回,假设不为空
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
//获取数据,一会儿返回,假设不为 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.
* 删除某个指定节点
*/
E unlink(Node<E> x) {
// assert x != null;
//获取数据,一会儿返回,假设不为 null。
final E element = x.item;
//获取指定节点后面的节点
final Node<E> next = x.next;
//获取指定节点前面的节点
final Node<E> prev = x.prev;
//如果前面没有节点,说明 x 是第一个
if (prev == null) {
first = next;
} else {
//前面有节点,让前面节点跨过 x 直接指向 x 后面的节点
prev.next = next;
x.prev = null;
}
//如果后面没有节点,说 x 是最后一个节点
if (next == null) {
last = prev;
} else {
//后面有节点,让后面的节点指向 x 前面的
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
/**
* Returns the (non-null) Node at the specified element index.
* 获取指定位置的节点
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//二分一下,如果小于 size 的一半,从头开始遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
//大于 size 一半,从尾部倒着遍历
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
4、LinkedList-公开方法-添加方法
/**
* 将指定的元素追加到此列表的末尾。
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param 要附加到此列表的元素
* @return 添加成功则返回true
*/
public boolean add(E e) {
linkLast(e);
return true;
}
//在指定位置添加元素
public void add(int index, E element) {
//检查 指示参数是否是迭代器或add操作。
checkPositionIndex(index);
//指定位置也有可能是在尾部
//该元素插入到尾部[作为尾节点]
if (index == size)
linkLast(element);
else
linkBefore(element, node(index)); //在 非空的指定节点 前面插入一个元素
}
//添加一个集合的元素
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* 将指定集合中的所有元素插入列表,从指定位置开始。
*
* @param 插入第一个元素的索引
* @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 如果指定的集合为null,@将引发NullPointerException
*/
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 指向 index 位置的节点,pred 指向它前一个
succ = node(index);
pred = succ.prev;
}
//遍历要添加内容的数组
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//创建新节点,头指针指向 pred
Node<E> newNode = new Node<>(pred, e, null);
//如果 pred 为空,说明新建的这个是头节点
if (pred == null)
first = newNode;
else
pred.next = newNode; //pred 指向新建的节点
//pred 后移一位
pred = newNode;
}
//添加完后需要修改尾指针
if (succ == null) {
//如果 succ 为空,说明要插入的位置就是尾部,现在 pred 已经到最后了
last = pred;
} else {
//否则 pred 指向后面的元素
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
//添加到头部,时间复杂度为 O(1)
public void addFirst(E e) {
//调用内部方法,将该元素插入到头部[作为头节点]
linkFirst(e);
}
//添加到尾部,时间复杂度为 O(1)
public void addLast(E e) {
//调用内部方法,将该元素插入到尾部[作为尾节点]
linkLast(e);
}
继承自双端队列(Deque)的添加方法:
//入栈,其实就是在头部添加元素
public void push(E e) {
addFirst(e);
}
//安全的添加操作,在尾部添加
public boolean offer(E e) {
return add(e);
}
//在头部添加
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//尾部添加
public boolean offerLast(E e) {
addLast(e);
return true;
}
5、LinkedList-公开方法-删除方法
//删除头部节点
public E remove() {
return removeFirst();
}
//删除指定位置节点
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//删除包含指定元素的节点,这就得遍历了
public boolean remove(Object o) {
if (o == null) {
//遍历终止条件,不等于 null
for (Node<E> x = first; x != null; x = x.next) {
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;
}
//删除头部元素
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 removeFirstOccurrence(Object o) {
return remove(o);
}
//删除最后一次出现的指定元素,倒过来遍历
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
继承自双端队列(Deque)的删除方法:
public E pop() {
return removeFirst();
}
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、LinkedList-公开方法-修改方法
1、公开的修改方法,只有一个 set :
//找到这个节点,替换数据就好了
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
7、LinkedList-公开方法-查询方法
//挨个遍历,获取第一次出现位置
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;
}
//是否包含指定元素
public boolean contains(Object o) {
return indexOf(o) != -1;
}
//获取指定位置的元素,需要遍历
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//获取第一个元素,很快
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
继承自双端队列(Deque)的查询方法:
//获取第一个,同时删除它
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//也是获取第一个,和 poll 不同的是不删除
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//长得一样嘛
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//最后一个元素,也很快
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
8、LinkedList-公开方法-清除方法
1、清除全部元素其实只需要把首尾都置为 null, 这个链表就已经是空的,因为无法访问元素。但是为了避免浪费空间,需要把中间节点都置为 null:
public void clear() {
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++;
}
8、LinkedList-迭代器
1、LinkedList,内部实现的迭代器(Iterator)。
1-1、LinkedList 实现了一个倒序迭代器 DescendingIterator;
1-2、还实现了一个 ListIterator ,名叫 ListItr迭代器[???]。
1-3、还有个 LLSpliterator 继承自 Spliterator, JDK8加入的。
8-1、LinkedList-迭代器-DescendingIterator 倒序迭代器
1、DescendingIterator 倒序迭代器:
/**
* @since 1.6
*/
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
/**
* Adapter to provide descending iterators via ListItr.previous
*/
private class DescendingIterator implements Iterator<E> {
// ListItr迭代器
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
8-2、LinkedList-迭代器-ListItr迭代器
1、ListItr迭代器
/**
* 返回此列表中元素的列表迭代器。从列表中指定的位置开始。
* 面对如果是并发修改,迭代器会迅速而彻底地失败
*
* @param index index of the first element to be returned from the
* list-iterator (by a call to {@code next})
* @return a ListIterator of the elements in this list (in proper
* sequence), starting at the specified position in the list
* @throws IndexOutOfBoundsException {@inheritDoc}
* @see List#listIterator(int)
*/
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
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();
}
}
8-3、LinkedList-迭代器-LLSpliterator迭代器
1、使用 Iterator 的时候,我们可以顺序地遍历容器中的元素,使用 Spliterator 的时候,我们可以将元素分割成多份,分别交于不于的线程去遍历,以提高效率。
2、使用 Spliterator 每次可以处理某个元素集合中的一个元素 — 不是从 Spliterator 中获取元素,而是使用 tryAdvance() 或 forEachRemaining() 方法对元素应用操作。
3、Spliterator 还可以用于估计其中保存的元素数量,而且还可以像细胞分裂一样变为一分为二。这些新增加的能力让流并行处理代码可以很方便地将工作分布到多个可用线程上完成。
/**
* Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
* and <em>fail-fast</em> {@link Spliterator} over the elements in this
* list.
*
* <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and
* {@link Spliterator#ORDERED}. Overriding implementations should document
* the reporting of additional characteristic values.
*
* @implNote
* The {@code Spliterator} additionally reports {@link Spliterator#SUBSIZED}
* and implements {@code trySplit} to permit limited parallelism..
*
* @return a {@code Spliterator} over the elements in this list
* @since 1.8
*/
@Override
public Spliterator<E> spliterator() {
return new LLSpliterator<E>(this, -1, 0);
}
/** A customized variant of Spliterators.IteratorSpliterator */
static final class LLSpliterator<E> implements Spliterator<E> {
static final int BATCH_UNIT = 1 << 10; // batch array size increment
static final int MAX_BATCH = 1 << 25; // max batch array size;
final LinkedList<E> list; // null OK unless traversed
Node<E> current; // current node; null until initialized
int est; // size estimate; -1 until first needed
int expectedModCount; // initialized when est set
int batch; // batch size for splits
LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
this.list = list;
this.est = est;
this.expectedModCount = expectedModCount;
}
final int getEst() {
int s; // force initialization
final LinkedList<E> lst;
if ((s = est) < 0) {
if ((lst = list) == null)
s = est = 0;
else {
expectedModCount = lst.modCount;
current = lst.first;
s = est = lst.size;
}
}
return s;
}
public long estimateSize() { return (long) getEst(); }
public Spliterator<E> trySplit() {
Node<E> p;
int s = getEst();
if (s > 1 && (p = current) != null) {
int n = batch + BATCH_UNIT;
if (n > s)
n = s;
if (n > MAX_BATCH)
n = MAX_BATCH;
Object[] a = new Object[n];
int j = 0;
do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
current = p;
batch = j;
est = s - j;
return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
}
return null;
}
public void forEachRemaining(Consumer<? super E> action) {
Node<E> p; int n;
if (action == null) throw new NullPointerException();
if ((n = getEst()) > 0 && (p = current) != null) {
current = null;
est = 0;
do {
E e = p.item;
p = p.next;
action.accept(e);
} while (p != null && --n > 0);
}
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
}
public boolean tryAdvance(Consumer<? super E> action) {
Node<E> p;
if (action == null) throw new NullPointerException();
if (getEst() > 0 && (p = current) != null) {
--est;
E e = p.item;
current = p.next;
action.accept(e);
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}
public int characteristics() {
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
9、LinkedList-源码分析-总结
1、概念知识-总结
1-1、LinkedList 实际上是通过双向链表去实现的。
它包含一个非常重要的内部类:Node。Node是双向链表节点所对应的数据结构,它包括的属性有:当前节点所包含的值,上一个节点,下一个节点。
1-2、从LinkedList的实现方式中可以发现,它不存在LinkedList容量不足的问题。
1-3、LinkedList的克隆函数,即是将全部元素克隆到一个新的LinkedList对象中。
1-4、由于LinkedList实现了Deque,而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式:一种形式在操作失败时抛出异常,另一种形式返回一个特殊值(null 或 false,具体取决于操作)
1-4-1、总结如下:
第一个元素(头部) 最后一个元素(尾部)
抛出异常 特殊值 抛出异常 特殊值
插入 addFirst(e) offerFirst(e) addLast(e) offerLast(e)
移除 removeFirst() pollFirst() removeLast() pollLast()
检查 getFirst() peekFirst() getLast() peekLast()
1-5、LinkedList可以作为FIFO(先进先出)的队列,作为FIFO的队列时,如下的方法等价:
队列方法 等效方法
add(e) addLast(e)
offer(e) offerLast(e)
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()
1-6、LinkedList可以作为LIFO(后进先出)的栈,作为LIFO的栈时,如下的方法等价:
栈方法 等效方法
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()
2、对LinkedList遍历,使用foreach方式,而不是for循环方式
https://www.cnblogs.com/skywang12345/p/3308807.html
https://blog.csdn.net/u011240877/article/details/52876543