package java.util;
import java.util.function.Consumer;
public class linkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
{
//成员变量，记录集合中元素个数
transient int size = 0;
//指向第一个节点的指针
transient Node first;
//指向最后一个节点的指针
transient Node last;
//空参构造函数
public linkedList() {
}
//有参构造函数，参数为集合，需要把参数中的数据按照集合的迭代器返回的顺序存放再linkedList中
public linkedList(Collection c) {
this();
//掉用addAll方法，
addAll(c);
}
//参数e 作为第一个元素，私有方法
//该方法的作用就是把元素e,存入链表的表头位置，作为链表的第一个节点
private void linkFirst(E e) {
//把链表原来的第一个元素赋值给新建的局部变量f
final Node f = first;
//用有参构造函数创建e元素对应的Node节点newNode，该节点的后序next属性为f
//也就是原来的成员变量first对象赋值给newNode的next变量，即原来的first元素为newNode的后序节点
final Node newNode = new Node<>(null, e, f);
//把newNode赋值给成员变量first,即新建的元素为链表的第一个元素
first = newNode;
//r如果f等于null,也就意味着原来的链表没有数据，那么把newNode赋值给集合的成员变量last
//即newNode即是链表的头元素，也是链表的尾元素，也就是该链表只有一个元素newNode
if (f == null)
last = newNode;
else
//如果f不等于null,则newNode赋值给f的成员变量prev,即新元素newNode为f元素的前序节点
f.prev = newNode;
//节点添加成功后，集合的元素个数size加1
size++;
//集合的修改次数加1
modCount++;
}
// 参数e 作为集合的最后一个元素
void linkLast(E e) {
//把链表原来的最后一个元素赋值给新建的局部变量l
final Node l = last;
//用有参构造函数创建e元素对应的Node节点newNode，该节点的前序prev属性为l
//也就是原来的成员变量last对象赋值给newNode的prev变量，即原来的last元素为newNode的前序节点
final Node newNode = new Node<>(l, e, null);
//把newNode赋值给成员变量last,即新建的元素为链表的最后一个元素
last = newNode;
//如果l等于null,也就意味着原来的链表没有数据，那么把newNode赋值给集合的成员变量first
//即newNode即是链表的头元素，也是链表的尾元素，也就是该链表只有一个元素newNode
if (l == null)
first = newNode;
else
//如果l不等于null,则newNode赋值给l的成员变量next,即新元素newNode为l元素的后序节点
l.next = newNode;
//节点添加成功后，集合的元素个数size加1
size++;
//集合的修改次数加1
modCount++;
}
//在非空的 Node节点succ之前插入元素 e
void linkBefore(E e, Node succ) {
// assert succ != null;
//获取元素succ的前序节点并赋值给局部变量pred
final Node pred = succ.prev;
//给元素e通过有参构造函数创建一个Node对象newNode
//该元素的前序节点为pred,后续节点为succ
final Node newNode = new Node<>(pred, e, succ);
//把succ的prev即succ的前序设置为newNode
succ.prev = newNode;
//如果pred为null即succ为原来链表的头元素，那么此时新增的节点newNode为现有集合的头元素
//所以newNode赋值给first
if (pred == null)
first = newNode;
else
//如果pred不等于null,则newNode赋值给pred的成员变量next,即新元素newNode为pred元素的后序节点
pred.next = newNode;
//节点添加成功后，集合的元素个数size加1
size++;
//集合的修改次数加1
modCount++;
}
//删除链表的头节点f
//该方法是私有方法，即在集合内部使用
//该方法逻辑不严谨，如果参数f不为头节点，那么就会把链表从f节点出断开
//如果是参数只能是头节点，那么就不用传参，在消息体中直接获取头节点即可
private E unlinkFirst(Node f) {
// assert f == first && f != null;
//获取头节点里的元素并赋值局部变量element
final E element = f.item;
//获取头节点的后续节点并赋值给局部变量next
final Node next = f.next;
//把头节点里的元素置null
f.item = null;
//把头节点里的next元素置null
f.next = null; // help GC
//把next赋值给成员变量first，也就是把f节点的后续节点设置为新链表的头节点
first = next;
//如果next等于null，那么意味着此时集合中没有元素了，则此时集合的last也为null
if (next == null)
last = null;
else
//否则next的prev即next的前序节点为null
next.prev = null;
//集合元素个数减一
size--;
//集合修改次数加1
modCount++;
//返回element
return element;
}
//删除链表的尾部节点
private E unlinkLast(Node l) {
// assert l == last && l != null;
//获取尾节点里的元素并赋值局部变量element
final E element = l.item;
//获取尾节点的前序节点赋值给新建的局部变量prev
final Node prev = l.prev;
//尾部节点中的元素item及前序节点prev置空
//因为l为尾部节点，所以l的next本来就是null，所以需要处理
l.item = null;
l.prev = null; // help GC
//链接的原来的尾部节点被去掉以后，
//那么原来的尾部节点的前序节点即prev就是新链接的尾部节点
last = prev;
//如果prev为null，则链接原来就只有一个节点l，
//l删除后就意味着此时集合中没有元素了，此时的first也为null
if (prev == null)
first = null;
else
//否则prev的next即prev的后续节点为null
prev.next = null;
//集合元素个数减一
size--;
//集合修改次数加1
modCount++;
//返回element
return element;
}
//删除链接非空节点 x，注意是非空节点，不是非空元素
E unlink(Node x) {
// assert x != null;
//获取节点中的元素，并赋值给局部变量element
final E element = x.item;
//获取节点的后序节点并赋值给局部变量next
final Node next = x.next;
//获取节点的前序节点并赋值给局部变量next
final Node prev = x.prev;
//如果x节点的前序节点为null则说明
//x为链接的头节点，那么把x删除掉，x的后序节点next就为链接新的头元素
//所以把next赋值给first
if (prev == null) {
//把next赋值给first
first = next;
} else {
//如果prev不为null,也就代表节点x不是头节点
//则把x后序节点赋值给x前序节点的next属性
//即x节点的前序节点与后序节点关联
prev.next = next;
//x节点的prev置为null
x.prev = null;
}
//如果x节点的后续节点为null则说明
//x为链表的尾部节点，那么把x删除掉，那x节点原来的前序节点prev就是链表的新的尾元素
//所以把prev赋值给last
if (next == null) {
//把prev赋值给last
last = prev;
} else {
//如果next不为null，则说明x不是尾部节点
//则把x节点的前序节点赋值给后序节点的prev属性，
//即把x的前序节点与x的后序节点关联
next.prev = prev;
//x节点的next置为null
x.next = null;
}
//x节点的item置为null
x.item = null;
//
//链表元素的个数减1
size--;
//集合修改次数加1
modCount++;
//返回x节点的元素
return element;
}
//获取集合的第一个节点的元素
public E getFirst() {
//把代表链接的第一个节点的成员变量first赋值给新建的局部变量f
final Node f = first;
//如果f等于null,即first等于null，则代表集合没有元素
//所以直接报异常
if (f == null)
throw new NoSuchElementException();
//如果f不等于null，则获取f节点元素item则直接返回
return f.item;
}
//获取集合的最后一个节点元素
public E getLast() {
//把代表链接的最后一个节点的成员变量last赋值给新建的局部变量l
final Node l = last;
//如果l为null，即last为null，则代表集合没有元素
//所以直接报异常
if (l == null)
throw new NoSuchElementException();
//如果l不等于null，则获取l节点元素item则直接返回
return l.item;
}
//删除并返回集合的第一个元素
public E removeFirst() {
//把代表链接的第一个节点的成员变量first赋值给新建的局部变量f
final Node f = first;
//如果f等于null,即first等于null，则代表集合没有元素
//所以直接报异常
if (f == null)
throw new NoSuchElementException();
//如果不为null，则调用unlinkFirst方法删除头节点，并返回头节点对应的元素
return unlinkFirst(f);
}
//删除并返回集合的最后一个元素
public E removeLast() {
//把代表链接的最后一个节点的成员变量last赋值给新建的局部变量l
final Node l = last;
//如果l为null，即last为null，则代表集合没有元素
//所以直接报异常
if (l == null)
throw new NoSuchElementException();
//如果不为null，则调用unlinkLast方法删除尾节点，并返回头节点对应的元素
return unlinkLast(l);
}
//在此列表的开头插入指定的元素。
public void addFirst(E e) {
//调用linkFirst方法
linkFirst(e);
}
//将指定的元素附加到此列表的末尾。
public void addLast(E e) {
//调用linkLast完成添加
linkLast(e);
}
//如果此列表包含指定的元素，则返回true
//更准确地说，当且仅当此列表时返回true
public boolean contains(Object o) {
//调用indexOf方法，只有方法返回的不等于-1则代表集合中存在要找的元素
//所以方法返回true
return indexOf(o) != -1;
}
//返回此列表中的元素数。
public int size() {
return size;
}
//将指定的元素附加到此列表的末尾。
//此方法等效于addLast只是addLast方法没有返回值
public boolean add(E e) {
//调用linkLast
linkLast(e);
return true;
}
//从此列表中删除第一次出现的指定元素（如果存在）.
//注意删除的是按照迭代顺序第一次出现的元素，如果集合中存在多个元素o，那么也只是删掉一个
public boolean remove(Object o) {
//判断对象o是否为null
if (o == null) {
//如果为null，则从头元素开始遍历集合
for (Node x = first; x != null; x = x.next) {
//如果找到要删除的元素对应的Node节点，则调用unlink删除节点
//并返回true
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
//如果不为null，则从头元素开始遍历集合
for (Node x = first; x != null; x = x.next) {
//如果找到要删除的元素对应的Node节点，则调用unlink删除节点
//并返回true
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
//如果没有删除元素则返回false
return false;
}
//该方法参数为集合，需要把参数中的元素按照参数集合的迭代器返回的顺序将集合中的所有元素追加到linkedList的末尾
public boolean addAll(Collection c) {
//调用重载方法，第一个参数为linkedList集合现有元素个数，第二参数为传过来的集合
//addAll(int index, Collection c) 方法 作用就是从指定位置开始，将指定集合中的所有元素插入此列表
return addAll(size, c);
}
//从指定位置开始，将指定集合中的所有元素插入此列表。
//将当前在该位置的元素（如果有）和任何后续元素向右移动（增加它们的索引）。
//新元素将按照指定集合的迭代器返回的顺序出现在列表中
public boolean addAll(int index, Collection c) {
//检测索引即元素要插入的位置是否合法
//此时index合法位置为 index >= 0 && index <= size
//等于0说明要插入的位置为链表第一个节点位置，
//等于size说明要插入的位置为链表最后一个元素的后边
checkPositionIndex(index);
//集合转换成数组，此处如果参数为null,则会报空指针异常的错误
Object[] a = c.toArray();
//获取数组长度并赋值给新建的局部变量numNew
int numNew = a.length;
//如果numNew等于0，即代表传过来的集合没有数据则直接返回false，代表linkedList没有新插入数据
if (numNew == 0)
return false;
//定义两个局部变量pred和succ
//pred 代表参数集合插入到linkedList集合后，参数集合的第一个元素的前序元素
Node pred, succ;
//如果index等于size,也就是插入的位置为链表最后一个元素的后边或者是空链表的第一个元素
if (index == size) {
//succ置为null
succ = null;
//last赋值pred
pred = last;
} else {
//index不等于size,说明插入的位置不是最后一个元素的后边
//此时就需要获取linkedList集合现在index位置上的元素，并把获取的元素赋值给succ
succ = node(index);
//把linkedList集合的index位置上的元素的前序元素赋值给pred
pred = succ.prev;
}
//循环遍历数组，获取元素
for (Object o : a) {
@SuppressWarnings("unchecked")
//元素类型强转
E e = (E) o;
//创建Node对象，pred为新元素的newNode前序节点，对象创建完成后newNode对象中的prev变量为pred
Node newNode = new Node<>(pred, e, null);
//pred判断pred是否为空
//为空则说明要插入的位置是链表的第一个元素的位置
//pred为空的情况只有是for循环的第一次循环
//并且要插入的元素位置为链表的第一个元素的位置的情况下会出现
if (pred == null)
//pred为空则说明此时的newNode为链表的第一个元素
//所以要把newNode对象赋值给linkedList集合的成员变量first
first = newNode;
else
//如果pred不等于空，则说明newNode不是链表的第一个元素
//并且pred就是newNode前序元素，所以pred中的next变量就是newNode对象
//而且newNode对象中的prev变量为pred
pred.next = newNode;
//以上步骤完成后局部变量pred重新赋值为newNode赋值完成后进行下一次循环
//下一次循环的元素（如果有）的前序节点就是本次循环创建的元素newNode
pred = newNode;
}
//循环完成，如果succ为空（注意for循环中没有操作succ）
//则说明要插入集合的第一个元素的位置是原来链表最后一个元素的后边，或者空链表的第一个元素
//所以参数集合元素插入完成后，参数集合的最后一个元素就是插入完成后linkedList集合的最后一个元素
//此时的pred指的是参数集合中的最后一个元素创建的Node对象
if (succ == null) {
//pred赋值给成员变量last
last = pred;
} else {
//如果succ不为空，succ赋值给pred.next，而pred赋值给succ.prev
//即原来链表的index位置的元素succ的前序节点为pred,也就是pred的后序接节点为succ
pred.next = succ;
succ.prev = pred;
}
//集合元素个数变成size+numNew
size += numNew;
//集合修改次数加1
modCount++;
//一切正常放回true
return true;
}
//从此列表中删除所有元素。 此调用返回后，列表将为空。
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
//遍历链表把链表中的每个Node中的item，next，prev都置为null，这样有利于jvm垃圾回收
for (Node x = first; x != null; ) {
Node next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
//成员变量first、last都置为null
first = last = null;
//集合元素数量置为0，即没有元素
size = 0;
//集合修改次数加1
modCount++;
}
// Positional Access Operations
//返回此列表中指定位置的元素
//即使按照指定索引获取元素
public E get(int index) {
//检查索引是否合理,即index是否是集合中现有元素的索引
checkElementIndex(index);
//index没问题的话，调用node查找index对应的节点
//节点查找成功后返回节点对应的item，即要查找的index位置上对应的元素
return node(index).item;
}
//用指定的元素替换此列表中指定位置的元素。
public E set(int index, E element) {
//检查索引是否合理,即index是否是集合中现有元素的索引
checkElementIndex(index);
//查找集合链表在index位置上的Node节点
Node x = node(index);
//获取Node节点中的元素，并赋值给新建的局部变量oldVal
E oldVal = x.item;
//把要替换的元素element赋值给index对那个的Node节点中的元素
x.item = element;
//返回旧元素
return oldVal;
}
//在此列表中的指定位置插入指定元素。
//将当前在该位置的元素（如果有）和任何后续元素向右移动
public void add(int index, E element) {
//检查index是否合法即判断index >= 0 && index <= size
//等于0是因为索引是从0开始的，等于size，是代表要插入的数据为原来集合链表的尾节点的后边
checkPositionIndex(index);
//index等于size时代表的要插入的数据为原来集合链表的尾节点后边
//此时该方法等同与addLast方法
if (index == size)
linkLast(element);
else
//如果index不等于size，则先调用node方法，查找index对应Node节点，
//然后调用linkBefore方法进行数据插入
linkBefore(element, node(index));
}
//移除此列表中指定位置的元素.
//将任何后续元素向左移动（从它们的索引中减去一个）。
//返回从列表中删除的元素。
public E remove(int index) {
//检查索引是否合理,即index是否是集合中现有元素的索引
checkElementIndex(index);
//先调用node方法更具index查找对应的Node节点，
//然后调用unlink删除该Node节点
return unlink(node(index));
}
//判断参数是否是现有元素的索引
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
//判断参数是否是迭代器或加法操作的有效位置的索引
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
//异常返回消息定义
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
//判断参数是否是现有元素的索引
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//检查位置索引
private void checkPositionIndex(int index) {
//如果不符合索引要求则抛出异常
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//根据索引查找对应的Node节点,采用折半查找
Node node(int index) {
//调用该方法时默认已经对index进行校验成功的
// assert isElementIndex(index);
//size >> 1代表着size除以2，即使size的一半
//判读index是否小于size的一半
if (index < (size >> 1)) {
//如果index小于size的一半，则从链表的表头开始查找
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//如果index大于size的一半，则从链表的表尾开始查找
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
// Search Operations
//返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1
public int indexOf(Object o) {
//定义局部变量index，index就是集合的索引，从0开始
int index = 0;
//判空
if (o == null) {
//如果为空，则从表头循环遍历，找到第一个元素为null的Node
//如果找到了返回index即元素对应的索引
//如果没找到则index加1，知道遍历完链表，如果遍历完成链表
//还么找到则返回-1
for (Node x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
//如果不为空，则从表头循环遍历，找到第一个元素为o的Node
//如果找到了返回index即元素对应的索引
//如果没找到则index加1，知道遍历完链表，如果遍历完成链表
//还么找到则返回-1
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
//没有找到返回-1
return -1;
}
//返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回 -1
//原理与indexOf一样，不同的是循环遍历是从链表的尾部开始的
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
// Queue operations.
//获取集合的第一个元素
//与getFirst类似，只是如果集合为空getFirst会抛出异常，
//但是peek不会抛出异常，只会返回null
//Deque接口的实现
public E peek() {
final Node f = first;
return (f == null) ? null : f.item;
}
//获取集合的第一个元素内部调用的是getFirst
//Deque接口的实现
public E element() {
return getFirst();
}
//删除第一个元素，并把第一个元素返回
//与removeFirst类似，只是如果集合为空removeFirst会抛出异常，
//但是poll不会抛出异常，只会返回null
//Deque接口的实现
public E poll() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}
//删除第一个元素，并把第一个元素返回
//内部调用removeFirst
//Deque接口的实现
public E remove() {
return removeFirst();
}
//添加指定元素作为此列表的尾部（最后一个元素）。
//内部调用add(e)方法
//Deque接口的实现
public boolean offer(E e) {
return add(e);
}
// Deque operations
//在此列表的前面插入指定的元素
//内部调用 addFirst(e)
//Deque接口的实现
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//在此列表的末尾插入指定的元素
//内部调用addLast
//Deque接口的实现
public boolean offerLast(E e) {
addLast(e);
return true;
}
//获取集合的第一个元素
//与peek实现相同
//Deque接口的实现
public E peekFirst() {
final Node f = first;
return (f == null) ? null : f.item;
}
//获取最后一个节点的元素
//Deque接口的实现
public E peekLast() {
final Node l = last;
return (l == null) ? null : l.item;
}
//检索并删除此列表的第一个元素，如果此列表为空，则返回null 。
//Deque接口的实现
public E pollFirst() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}
//检索并删除此列表的最后一个元素，如果此列表为空，则返回null 。
//Deque接口的实现
public E pollLast() {
final Node l = last;
return (l == null) ? null : unlinkLast(l);
}
//在表头添加元素
//Deque接口的实现
public void push(E e) {
addFirst(e);
}
//删除表头节点
//Deque接口的实现
public E pop() {
return removeFirst();
}
//删除元素o对应的节点，只删除第一个出现的
//内部调用remove（o）
//Deque接口的实现
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
//删除此列表中最后一次出现的指定元素o,遍历从表尾部开始遍历
//Deque接口的实现
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
public ListIterator listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator {
private Node lastReturned;
private Node 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 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 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();
}
}
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
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();
}
}
@SuppressWarnings("unchecked")
private linkedList superClone() {
try {
return (linkedList) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
public Object clone() {
linkedList 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 x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
@SuppressWarnings("unchecked")
public T[] toArray(T[] a) {
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
private static final long serialVersionUID = 876323262645176354L;
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 x = first; x != null; x = x.next)
s.writeObject(x.item);
}
@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());
}
@Override
public Spliterator spliterator() {
return new LLSpliterator(this, -1, 0);
}
static final class LLSpliterator implements Spliterator {
static final int BATCH_UNIT = 1 << 10; // batch array size increment
static final int MAX_BATCH = 1 << 25; // max batch array size;
final linkedList list; // null OK unless traversed
Node 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 list, int est, int expectedModCount) {
this.list = list;
this.est = est;
this.expectedModCount = expectedModCount;
}
final int getEst() {
int s; // force initialization
final linkedList 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 trySplit() {
Node 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 action) {
Node 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 action) {
Node 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;
}
}
}
