跟踪LinkedList源码，通过分析双向链表实现原理，自定义一个双向链表
2024-09-05 15:44:09
1.LinkedList实现的基本原理
LinkedList是一个双向链表，它主要有两个表示头尾节点的成员变量first 、last，因其有头尾两个节点，所以从头或从尾操作数据都非常容易快捷。LinkedList通过内部类Node来保存元素 ,一个Node对象表示链表的一个节点，有多少个元素就需要多少个Node节点。如果要添加元素，则新建一个Node节点，保存这个元素，同时指定其前驱节点和后继节点的引用。若要删除一个元素，则将取消此元素对应的Node节点在链表中的前驱后继关系。
2.ListedList实现的关键 -——静态内部类Node
Node类有3个成员变量：
1）表示当前节点保存的元素item ，
2）表示后继节点的引用next
3)表示前驱节点的引用 prev
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;
}
}
Node类有这3个成员能够很清楚的表示自己的逻辑结构。首先它能确定自己的位置，属性prev 、next分别指定了前驱、后继节点分别是谁，指明了当前节点在链表结构中的位置；另外成员变量item明确了当前节点要保存的元素。
3.ListedList的成员变量
其成员变量主要是表示链表头 尾节点的两个成员变量：头节点first 、 尾节点last。
因为有头尾两个节点，可以很方便地从头部或从尾部这两个方向进行逻辑操作。
只用一个头节点可实现单向链表，它的效率不高，因为只能从单向从头到尾遍历，不能根据实际情况选择更优的遍历方向。
// 链表的所含元素个数
transient int size = 0; // 链表的头节点
transient Node<E> first;
// 链表的尾节点
transient Node<E> last;
/*
* 此属性在本类中没有，此属性是从父类AbstractSequentialList中继承而来
* 链表结构被修改的次数，防止在迭代遍历过程中，修改链表结构
*/
protected int modCount = 0;
4 .其构造方法
构造方法有两个，一个默认构造方法，将初始化一个空链表；另一个带单参数的构造方法，将初始化后，此链表将包含集合参数c的所有元素
public LinkedList() { } //头尾节点都是null的空链表
//初始化后，包含集合c所有元素的链表
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);//添加集合c所有元素
}
5.其常用的API
1). public boolean add(E e) 在尾部添加一个元素
此方法去调用了一个对链表尾部连接新元素的方法linkLast(E)
public boolean add(E e) {
linkLast(e);//在尾部链接一个新元素
return true;
}
此时去看看linkLast(E)的实现细节：
------- 在添加新元素时要注意特殊情况，即要考虑当前的链表为空、不含任何元素的可能，此时需要将当前新添加的节点设为头节点
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++;//添加一个元素，链表结构被修改一次，modCount自加一
}
2）public void add(int index, E element) 在指定下标处添加元素
此方法有两个分支，若插入的下标位置等于链表元素个数，则可直接在链表尾部添加要插入的元素；而其它一般情况则调用linkBefore（E，Node)方法，在指定某节点之前插入指定元素。
而linkBefore(E，Node)的方法参数又调用了Node<E> node(int)方法。
public void add(int index, E element) {
checkPositionIndex(index); //检查下标是否合法
if (index == size) //插入的位置index=size即可直接在链表尾部添加元素
linkLast(element);
else
//在指定的节点之前插入元素
linkBefore(element, node(index));
}
先来看看node(int)方法是如何根据下标查找到下标对应的Node节点
------- node(int)方法中有两个分支，根据index是否小于size的一半作为进入不同分支的条件。此分支条件是用来确定待查找的节点与头/尾节点的距离远近，若待查找的节点和头节点较近，就从头节点开始查找;若待查找的节点与尾节点较近，则从尾节点开始遍历查找。这主要是从遍历效率角度考虑的。
Node<E> node(int index) {
//index作为循环遍历停止的条件
if (index < (size >> 1)) { // 如果index小于size的一半，则从头部开始向后查找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next; //将当前节点的后继节点赋值给当前节点
return x;
} else { // 如果index大于size的一半，则从尾部开始向前查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;//将当前节点的前驱节点赋值给当前节点
return x;
}
}
最后来看linkBefore（E，Node)如何在指定的节点前添加指定的元素
-------其中也对插入位置的进行了判断，如果是在头部插入节点，则需要将头节点的引用更新为待插入节点。
void linkBefore(E e, Node<E> succ) {
//插入点节点succ的前驱节点pred
final Node<E> pred = succ.prev;
/*
* 待插入的节点，
* 此节点将取代插入点节点succ，插入点succ将后移一位
* 此节点的前驱是插入点节点的前驱节点pred，其后继节点就是插入点节点succ
*/
final Node<E> newNode = new Node<>(pred, e, succ);
//插入点节点的前驱是待插入节点
succ.prev = newNode;
if (pred == null)
/*
* 插入点节点的前驱节点pred为为空，表明此时在头部直接插入节点
* 那么链表更新后，当前的待插入节点就是头节点
*/
first = newNode;
else
/*
* 插入点节点的前驱节点pred的后继节点是待插入节点
*/
pred.next = newNode;
size++;
modCount++;
}
3） public E remove(int index) 移除指定位置的元素
先利用node(int)方法，根据下标查找到对应的Node节点，再调用unlink(Node)方法,取消指定节点在链表中的链接关系。
public E remove(int index) {
checkElementIndex(index);//检查下标是否合法
/*
* 利用node(int)方法，根据下标查找到对应的Node节点
* 再调用unlink(Node)方法,取消指定节点在链表中的链接关系
*/
return unlink(node(index));
}
node(int)方法已经在之前已经分析过了，这里主要来看unlink(Node)方法的实现
------unlink(Node）方法比较复杂，但是将思路理清楚，也就不难理解了。
(1)因为待移除节点x将被删除，x的前驱prev和x的后继next都将不再依赖x这个中间连接者，所以要将前驱节点prev与后继节点next直接链接起来。LinkedList是双向链表，每个节点都要双向（前后）维护链接关系，即同时维护前驱与后继。那么prev、next两者都要更新链接关系，链表更新后prev的后继节点是next,即prev.next=next, 而next的前前驱节点又是prev,即next.prev=prev 。
(2)另外还要考虑待移除节点x是头节点或尾节点这种特殊情况（first=next或last=prev）。
(3)因为待移除节点x不会再被使用了，最后还要将待移除节点x的各个属性赋为null,便于GC回收内存资源（x.item=null ;x.prev=null;x.next=null）。
E unlink(Node<E> x) {
//保存待移除节点储存的元素，最后要返回这个被移除的元素
final E element = x.item;
//待移除节点的后继节点
final Node<E> next = x.next;
//待移除节点的前驱节点
final Node<E> prev = x.prev;
/**
* 维护待移除节点的前节点驱prev的链接关系
*/
if (prev == null) {
/*
* 待移除节点的前驱prev为空，表明待移除节点是头节点
* 当待移除节点是头节点时，移除元素更新后，待移除节点的后继节点next就是链表更新后的头节点
* 此时待移除节点的前驱节点本来就为空，不用再去赋为空值
*/
first = next;
} else {
/* 在其他一般情况下（非头节点），更新后
* 待移除节点的前驱节点prev的后继节点 就是待移除节点的后继节点next
* 将待移除节点x的属性prev赋为空，便于最后的垃圾回收
*/
prev.next = next;
x.prev = null;
}
/*
* 维护待移除节点的后继节点的链接关系
*/
if (next == null) {
/*
* 待移除节点的后继next为空，表明待移除节点是尾节点
* 当待移除节点是尾节点，移除元素更新后，待移除节点的前驱节点prev就是链表更新后的尾节点
* 此时待移除节点的后继节点本来就为空，不用再去赋为空值
*/
last = prev;
} else {
/* 在其他一般情况下（非尾节点），移除更新后
* 待移除节点的后继节点next的前驱节点 就是的待移除节点的前驱节点prev
* 将待移除节点x的属性next赋为空，便于最后的垃圾回收
*/
next.prev = prev;
x.next = null;
}
x.item = null; //将待移除节点储存的元素引用赋空
size--;
modCount++;//链表结构被修改，modCount自加
return element;//返回被移除元素
}
4） public E remove(Object o) 根据元素的引用移除元素
根据元素是否为空进入不同的分支。从头元素开始向后遍历，若链表中的一个元素与o相等，则调用unlink(Node)方法移除当前节点，退出循环并返回true；若遍历了所有元素，没有任何一个元素与o相等，则返回false，移除指定元素失败。
public boolean remove(Object o) {
if (o == 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;
}
5）public E set(int index, E element) 替换指定下标对应的元素
（1）找到下标index对应的节点
（2）保存index下标位置的原元素值
（3) 将节点的item属性更新为element
public E set(int index, E element) {
checkElementIndex(index);//检查下标
Node<E> x = node(index); //查找下标index对应的节点
E oldVal = x.item; //保存原值
x.item = element;//将下标index对应节点所保存的元素值更新
return oldVal;
}
6）public E get(int index) 获取指定下标对应的元素
找到下标index对应的节点，返回此节点的item属性。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
7) public int indexOf(Object o) 根据元素值确定其第一次出现的位置下标
从头节点开始向后遍历，若找到这个元素则退出循环并返回当前遍历的下标，若不存在此元素返回-1.
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;
}
8) public int lastIndexOf(Object o) 根据元素值确定其最后一次出现的位置下标
与“public int indexOf(Object o)”的实现原理基本一致，只有遍历的方向不同而已，此方法是从尾节点向前遍历
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;
}
9）public void clear() 清空所有元素
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;//不含任何元素，size设为0
modCount++;
}
10) public boolean addAll(int index, Collection<? extends E> c) 在指定下标处插入所有集合元素
此方法也对一些特殊情况做了判断分支处理，如在链表的尾部添加元素，或是在链表的头部添加元素等。
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);//检查下标
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0) //集合c没有任何元素，不用添加任何一个元素，直接返回false。
return false;
//pred表示插入点原节点的前驱节点， succ表示插入点的原节点，
Node<E> pred, succ;
if (index == size) {
/*
* index=size表明在链表的尾部批量添加元素
* 前驱pred为尾节点
* 插入点的原节点succ不存在,则为null
*/
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;
}
6.总结源码经验，仿写双向链表
一个集合的基本功能是增删改查，总结一下这些功能的大致思路：
1）”增“元素： 可以在链表的尾部增加元素或在链表的中部插入元素。在尾部添加元素需要维护原尾部节点和新添加节点的相互链接关系；而在中部插入新元素需要维护新插入节点、插入点原节点、插入入节点前驱节点 这三个节点间的相互链接关系。可以统一起来看，"增"元素都是插入元素，需要维护新插入节点、新插入节点的前/后节点间的相互链接关系（在尾部添加元素时，其后继节点为空而已）。
2）“删”元素：维护待删节点的前后节点的相互链接关系，即将前后节点直接链接起来，另外还要将待删节点的各属性赋空（利于垃圾回收）。同时得考虑特殊情况下——在头部或尾部删除节点，此时还要更新头节点或尾节点的引用。
3）“改”元素：先根据索引或元素值找到对应的Node节点，再重设该节点的item属性。
4）“查”元素：根据索引，循环遍历找到对应的Node节点，获取该节点的item属性。
和LinkedList相似的双向链表：
package collection; import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException; public class LinkList<E> implements Iterable<E>, List<E> {
// 链表的所含元素个数
private int size = 0;
// 链表的头节点
private Node<E> head = null;
// 链表的尾节点
private Node<E> tail = null;
/*
* 链表结构被修改的次数，防止在迭代遍历过程中，修改链表结构
*/
int modCount = 0; /**
* 添加一个元素
*
* @param e
* @return
*/
public boolean add(E e) {
return linkTail(e);
} /**
* 在链表尾部新链接一个元素
*
* @param e
* @return
*/
private boolean linkTail(E e) {
final Node<E> oldTail = tail; final Node<E> newNode = new Node<>(oldTail, e, null);
tail = newNode;
if (oldTail == null)
head = newNode;
else {
oldTail.next = newNode;
} modCount++;
size++;
return true;
} /**
* 移除指定下标处的元素
*
* @param index
* @return
*/
public E remove(int index) {
checkElementIndex(index);
Node<E> nodeRemove = fastNodeAt(index);// 快速查找到指定下标对应的节点
return unlink(nodeRemove); // 取消这个节点在链表结构中链接
} /**
* 根据下标快速查找节点
*/
private Node<E> fastNodeAt(int index) {
if (index < size >> 1) {// 如果index小于size的一半，则从头部开始查找
Node<E> current = head; for (int i = 0; i < index; i++)
current = current.next;
return current; } else {// 如果index大于size的一半，则从尾部开始查找
Node<E> current = tail;
for (int i = size - 1; i > index; i--)
current = current.prev;
return current; }
} /**
* 取消指定节点在链表结构中的链接
*/
private E unlink(Node<E> node) { Node<E> prev = node.prev;
Node<E> next = node.next;
E oldData = node.data; /*
* 维护被移除节点的前驱节点的链接关系
*/
if (prev == null) {
/**
* 当被移除节点是头节点时，更新后的头节点就是被移除节点的下一节点
* 此时被移除节点的前节点本来就为空，不用再去赋为空值
*/
head = next;
} else {
prev.next = next;// 更新后，被移除节点的前节点对应的 后节点是 被移除节点的后节点
// 被移除节点的前节点赋空，若不赋空则一直存在对前置节点的引用，可能出现内存泄漏
node.prev = null;
}
/*
* 维护被移除节点的后继节点的链接关系
*/
if (next == null) {
/**
* 当被移除节点是尾节点时，更新后的尾节点就是被移除节点的前驱节点
* 此时被移除节点的后继节点本来就为空，不用再去赋为空值
*/
tail = prev;
} else {
// 更新后，被移除节点的后继接节点对应的前驱结点 就被移除节点的前驱结点
next.prev = prev;
node.next = null;
}
node.data = null;
// node=null;
size--;
modCount++;
return oldData;
} /**
* 更新指定下标处的元素，
*
* @param index
* @param e
* @return 原元素值
*/
public E set(int index, E e) {
checkElementIndex(index);// 快速查找到指定下标对应的节点
Node<E> node = fastNodeAt(index);
E oldData = node.data; // 保存老值
node.data = e;
return oldData;
} /**
* 获取指定下标的元素
*
* @param index
* @return
*/
public E get(int index) {
checkElementIndex(index);
return fastNodeAt(index).data;
} /**
* 指定元素第一次出现的下标位置
*
* @param obj
* @return
*/
public int indexOf(Object obj) {
if (size == 0)// 不含任何元素，返回-1
return -1;
int index = 0;
E curElement;
for (Node<E> next = head; next != null; next = next.next) {// 从头节点开始遍历
curElement = next.data;
if (curElement == obj || (curElement != null && curElement.equals(obj)))
// 找到了对应的元素，返回当前下标
return index;
index++;
}
return -1;// 没找到对应的元素
} public Node<E> nodeOf(Object obj) {
if (size == 0)
return null;
E curElement;
for (Node<E> next = head; next != null; next = next.next) {// 从头节点开始遍历
curElement = next.data;
if (curElement == obj || (curElement != null && curElement.equals(obj))) {
return next; }
}
return null;
} /**
* 返回指定元素最后一次出现的下标位置
*
* @param obj
* @return
*/
public int lastIndexOf(Object obj) {
if (size == 0)// 不含任何元素，返回-1
return -1;
E curElement;
int index = 0;
for (Node<E> prev = tail; prev != null; prev = prev.prev) {// 从尾节点开始遍历
curElement = prev.data;
if (curElement == obj || (curElement != null && curElement.equals(obj)))
return index;
index++;
}
return -1;
} public boolean remove(Object obj) {
if (size == 0)// 不含任何元素，false
return false;
E curElement;
for (Node<E> next = head; next != null; next = next.next) {// 从头节点开始遍历
curElement = next.data;
if (curElement == obj || (curElement != null && curElement.equals(obj))) {
unlink(next);
return true;
}
}
return false;
} public int size() {
return size;
} public boolean isEmpty() {
return size == 0;
} public void add(int index, E e) { checkElementPosition(index);
if (index == size) {
linkTail(e);
} else {
linkBefore(index, e);
}
} private boolean linkBefore(int index, E e) {
Node<E> node = fastNodeAt(index);
Node<E> prev = node.prev;
Node<E> newNode = new Node<>(prev, e, node); if (prev == null) {
head = newNode; } else {
prev.next = newNode; }
node.prev = newNode;
size++;
modCount++;
return true;
} // private Node<E> nodeAt(int index) {
// Node<E> targetNode = null;
// if (index < (size >> 1)) {// 如果index小于size的一半，则从头部开始查找这个元素
// Node<E> next = null;
// int i = 0;
// for (Node<E> current = head; current != null;) {
// if (i == index) {
// targetNode = current;
// break;
// }
// next = current.next;
// current = next;
// i++;
// }
// } else {
// Node<E> prev = null;
// int i = size - 1;
// for (Node<E> current = tail; current != null;) {
// if (i == index) {
// targetNode = current;
// break;
// }
// prev = current.prev;
// current = prev;
// i--;
// }
// }
// return targetNode;
// } /*
* 检查元素下标对应的元素是否存在
*
*/
private void checkElementIndex(int index) {
if (index >= size || index < 0)
throw new IndexOutOfBoundsException(indexOutRangeMsg(index)); } /*
* 检查在插入元素时，插入位置是否正确
*
*/
private void checkElementPosition(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(indexOutRangeMsg(index)); } private String indexOutRangeMsg(int index) {
return " index [" + index + "] , size [" + size + "]";
} // 表示节点的静态内部类
private static class Node<E> {
// 前一个节点
private Node<E> prev;
// 下一个节点
private Node<E> next;
// 当前节点存储的数据
private E data; public Node(Node<E> prev, E data, Node<E> next) {
super();
this.prev = prev;
this.next = next;
this.data = data;
} } @Override
public Iterator<E> iterator() { return new SimpleIterator();
} private class SimpleIterator implements Iterator<E> {
private int desireModCount = modCount;// 预期的的修改次数
private Node<E> nextNode = head;// 下次遍历的节点
private Node<E> lastRetNode = null;// 最终使用的节点
private int nextIndex = 0;// 下标 @Override
public boolean hasNext() { return nextIndex < size;
} @Override
public E next() {
checkModCount();
if (!hasNext())
throw new NoSuchElementException();
lastRetNode = nextNode;
E data = lastRetNode.data;
nextNode = nextNode.next;
nextIndex++;
return data;
} @Override
public void remove() {
checkModCount();
if (lastRetNode == null)
throw new IllegalStateException("");
Node<E> lastNode = lastRetNode.next;
LinkList.this.unlink(lastRetNode); if (lastNode == lastRetNode)
nextNode = lastNode;
else
nextIndex--; lastRetNode = null;
desireModCount = modCount; } /*
* 校验在迭代过程中，是否使用了非迭代的方式改变了链表结构
*/
private void checkModCount() {
if (desireModCount != modCount)
throw new IllegalStateException("迭代过程中的结构被改变了");
}
} @Override
public boolean contains(Object o) { return indexOf(o) != -1;
} @Override
public Object[] toArray() {
if (size == 0)
return new Object[] {};
Object[] objs = new Object[size];
int i = 0;
for (Node<E> next = head; next != null; next = next.next) {
objs[i] = next.data;
i++;
}
return objs;
} @SuppressWarnings("unchecked")
@Override
public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = head; x != null; x = x.next)
result[i++] = x.data; return a;
} @Override
public boolean containsAll(Collection<?> c) {
if (c == null)
throw new NullPointerException(); for (Object o : c) {
if (indexOf(o) == -1)
return false;
}
return true;
} @Override
public boolean addAll(Collection<? extends E> c) {
if (c == null)
throw new NullPointerException(); return addAll(size, c);
} @Override
public boolean addAll(int index, Collection<? extends E> c) {
checkElementPosition(index);
if (c.size() == 0)
return false;
Node<E> prev, insertPoint;
if (index == size) {
prev = tail;
insertPoint = null;
} else {
insertPoint = fastNodeAt(index);
prev = insertPoint.prev;
} Object[] elementsAdd = c.toArray(); for (Object o : elementsAdd) {
@SuppressWarnings("unchecked")
E e = (E) o;
Node<E> newNode = new Node<E>(prev, e, null);
if (prev == null)
head = newNode;
else
prev.next = newNode;
prev = newNode;
} if (insertPoint == null)
tail = prev;
else {
prev.next = insertPoint;
insertPoint.prev = prev;
} size += elementsAdd.length;
modCount++;
return true;
} @Override
public boolean removeAll(Collection<?> c) {
if (c == null)
throw new NullPointerException();
boolean removeFlag = false;
Iterator<E> itor = this.iterator();
while (itor.hasNext()) {
if (c.contains(itor.next())) {
itor.remove();
removeFlag = true; } }
return removeFlag;
} @Override
public boolean retainAll(Collection<?> c) { if (c == null)
throw new NullPointerException();
boolean retainFlag = false;
Iterator<E> itor = this.iterator();
while (itor.hasNext()) {
if (!c.contains(itor.next())) {
itor.remove();
retainFlag = true;
}
}
return retainFlag;
} @Override
public void clear() {
if (size == 0)
return;
for (Node<E> curNode = head; curNode != null;) {
Node<E> nextNode = curNode.next;
curNode.prev = null;
curNode.data = null;
curNode.next = null;
curNode = nextNode;
}
size = 0;
head = null;
tail = null;
modCount++;
} @Override
public ListIterator<E> listIterator() {
throw new UnsupportedOperationException(); } @Override
public ListIterator<E> listIterator(int index) { throw new UnsupportedOperationException();
} @Override
public List<E> subList(int fromIndex, int toIndex) { throw new UnsupportedOperationException();
} }
最新文章
- 用Javascript动态添加删除HTML元素实例 (转载)
- [开发笔记]-Visual Studio 2012中为创建的类添加注释的模板
- Open CASCADE 基础类(Foundation Classes)
- HDU2088JAVA2
- Asp.Net 构架(Http Handler 介绍) - Part.2
- STS(Spring Tool Suite)使用前准备
- SignalR 聊天室实例详解（服务器端推送版）
- js 前端操作的分页路由设计
- PXE 实现自动装机
- 自学Linux Shell4.2-监测磁盘空间mount umount df du
- C# Chart控件的使用总结1
- java内存模型：简单理解
- 对io进行分流
- CR与LF
- spring study
- dubbo注册zookeeper保错原因
- 二、Linux 静态IP,动态IP配置
- pacific-atlantic-water-flow（不错）
- Oracle邮件推送函数
- Web端优秀图表控件