一、概要
- Java中底层数据结构是链表、双端链表，Android中数据结构是双向循环链表
- 非线程安全数据结构,允许元素为null
- 继承了抽象类AbstractSequentialList，它是AbstractList的一个子类。实现了List<E>, Deque<E>(双端队列抽象), Cloneable, Serializable的接口。
- 由于底层数据结构是链表，所以增删元素的时候只需要修改元素的指针即可，时间效率比较高，因为不需要预留空间，所以空间效率也比较高。
- 没有时间RandomAccess，表示在随机访问上效率比较低。所以随机访问时时间效率也不高。在随机访问数据上做过优化，如果查找的位置位于链表的前半部从前向后遍历，如果位于链表的后半部，从后向前遍历
二、构造函数
Java
transient int size = 0;//大小
/**
* Pointer to first node.开始节点
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.最后的节点
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
//默认构造函数
public LinkedList() {
}
//集合数据构造函数
public LinkedList(Collection<? extends E> c) {
this();//调用默认构造函数
addAll(c);//将集合中的数据全部加入当前对象
}
节点信息
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;
}
}
结构展示
Java内LinkedList结构信息
Android
transient int size = 0;
transient Link<E> voidLink;//void节点，该节点的next是首节点，该节点的前节点是尾节点，如果集合为空，那么void的首尾节点都是自己
public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
public LinkedList(Collection<? extends E> collection) {
this();
addAll(collection);
}
节点信息
private static final class Link<ET> {
ET data;
Link<ET> previous, next;//前后节点
Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
previous = p;
next = n;
}
}
结构信息
Android内LinkedList结构信息
三、增加元素
3.1 普通增加一个对象
默认增加是指在链表的尾部增加一个对象
Java
public boolean add(E e) {
linkLast(e);
return true;//增加成功，返回true
}
void linkLast(E e) {
final Node<E> l = last;//获取尾节点
//创建节点，节点的前节点指向已有的尾节点，后节点指向空
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;//将尾节点指向新创建的节点
if (l == null)//如果上一尾节点为空，表示链表没有数据，那么newNode表示第一添加的节点
first = newNode;//所以首节点也会指向新创建的节点
else//如果上一尾节点不为空，表示链表中有数据
l.next = newNode;//上一节点的后节点就需要修改为新节点
size++;//size增加
modCount++;//修改次数增加
}
Android
public boolean add(E object) {
return addLastImpl(object);
}
private boolean addLastImpl(E object) {
Link<E> oldLast = voidLink.previous;//获取v的前节点，刚开始的时候为v自己
//创建新的节点，新节点前节点是老链表的有效尾节点，后节点为voidLink
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
voidLink.previous = newLink;//将v节点的前节点设为新节点
oldLast.next = newLink;//将老的尾节点后节点设为新节点
size++;//size变大
modCount++;//修改数增加
return true;
}
3.2 在某一位置增加一个对象
Java
public void add(int index, E element) {
checkPositionIndex(index);//数组越界判断
if (index == size)//如果插入位置为size大小位置
linkLast(element);//直接在最后插入即可
else
linkBefore(element, node(index));
}
//获取node的节点
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
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++;
}
Android
public void add(int location, E object) {
if (location >= 0 && location <= size) {//判断是否越界
Link<E> link = voidLink;//获取voidLink
if (location < (size / 2)) {//如果位置位于链表的前一半，那么从前向后开始查找
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {//如果位置位于链表的后一半，那么从后向前开始查找
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;//获得查找到位置前节点
//创建新的节点，前后节点分别是：查找到的节点原前节点和查找到的节点
Link<E> newLink = new Link<E>(object, previous, link);
previous.next = newLink;//将原前节点的后节点设为新节点
link.previous = newLink;//将查找到的节点的前节点设为新节点
//不用担心previous为null，因为Android中数据结构是双向循环链表
//那么在0位置添加的时候，previous指向了voidLink，不为空
//不用担心link为null，因为Android中数据结构是双向循环链表
//那么在size位置添加的时候，link还是指向了voidLink，不为空
size++;
modCount++;
} else {
throw new IndexOutOfBoundsException();
}
}
3.3 增加集合中的全部对象
Java
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
Android
public boolean addAll(Collection<? extends E> collection) {
int adding = collection.size();
if (adding == 0) {
return false;
}
//判断集合是否是自己，如果是就将集合修改为ArrayList
Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;
Link<E> previous = voidLink.previous;//获取尾部节点，最后节点
//遍历集合
for (E e : elements) {
//创建新节点，新节点的前节点是尾部节点，后节点为空，因为后节点不宜在循环过程中设置为voidLink
Link<E> newLink = new Link<E>(e, previous, null);
//将前节点的后节点设置为新节点
previous.next = newLink;
//最后的节点就变成了新节点
previous = newLink;
}
previous.next = voidLink;//将最后节点的后节点设为voidLink
voidLink.previous = previous;//将voidLink的前节点设为尾节点
size += adding;
modCount++;
return true;
}
3.4 在某一位置增加集合中的全部对象
Java
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 = node(index);//插入位置的节点，该节点在数据插入后会变成插入节点的后节点
pred = succ.prev;//插入位置的前节点，该节点在数据插入后会变成插入节点的前节点
}
for (Object o : a) {//循环遍历数组
@SuppressWarnings("unchecked")
E e = (E) o;//获取对象
//创建对象，该对象的前节点是pred，后节点为空
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;//修改size
modCount++;//修改数量增加
return true;
}
Android
public boolean addAll(int location, Collection<? extends E> collection) {
if (location < 0 || location > size) {//判断是否越界
throw new IndexOutOfBoundsException();
}
int adding = collection.size();
if (adding == 0) {//判断插入集合的数量
return false;
}
//判断插入的数据是否是自己，如果是将集合改为ArrayList
Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;
//获取插入位置的节点，做过简单优化
Link<E> previous = voidLink;
if (location < (size / 2)) {
for (int i = 0; i < location; i++) {
previous = previous.next;
}
} else {
for (int i = size; i >= location; i--) {
previous = previous.previous;
}
}
//此时previous是插入位置的前节点
//此时next是插入位置的后节点
Link<E> next = previous.next;
for (E e : elements) {//循环插入集合中的数据
//创建新节点，新节点的前节点指向原来的前节点
Link<E> newLink = new Link<E>(e, previous, null);
//将前节点的后节点设为新节点
previous.next = newLink;
previous = newLink;//前节点变化成新节点
}
//将前节点的后节点设置为原插入节点信息
previous.next = next;
//将原插入节点的前节点设置为最新的前节点
next.previous = previous;
size += adding;//修改size
modCount++;//修改modCount
return true;
}
四、删除元素
4.1 默认删除
调用的删除第一个节点的方法，具体参考13.2.1
Java
public E remove() {
return removeFirst();//调用删除第一个
}
Android
public E remove() {
return removeFirstImpl();
}
4.2 删除一个一个位置的元素
Java
node(index)具体参考3.2中Java代码
public E remove(int index) {
checkElementIndex(index);//判断是否越界
return unlink(node(index));//删除对应位置的节点
}
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;//获取删除节点的前节点
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;//将删除节点的item置空
size--;
modCount++;
return element;
}
Android
删除的节点连接信息，以及删除节点的值均未置空。。。
public E remove(int location) {
if (location >= 0 && location < size) {//判断是否越界
Link<E> link = voidLink;//获取voidLink
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
//此时previous是删除位置节点的前节点
//此时next是删除位置节点的后节点
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;//将删除节点前节点的后节点设为删除节点的后节点
next.previous = previous;//将删除节点后节点的前节点设为删除节点的前节点
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}
4.3 删除一个对象
Java
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);//具体参考4.2中Java代码
return true;
}
}
} else {//如果不为空，则从前向后查找第一个equals的节点
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
Android
public boolean remove(Object object) {
return removeFirstOccurrenceImpl(object);
}
private boolean removeFirstOccurrenceImpl(Object o) {
//获取迭代器
Iterator<E> iter = new LinkIterator<E>(this, 0);
return removeOneOccurrence(o, iter);
}
//删除一个在迭代器中出现的值
private boolean removeOneOccurrence(Object o, Iterator<E> iter) {
while (iter.hasNext()) {//是否有下一个
E element = iter.next();//下一个值
//如果为空则删除第一个空值，如果不为空则删除第一个相等的值
if (o == null ? element == null : o.equals(element)) {
iter.remove();
return true;
}
}
return false;
}
五、修改元素
Java
public E set(int index, E element) {
checkElementIndex(index);//检查数组越界
Node<E> x = node(index);//查找元素
E oldVal = x.item;//提取旧值
x.item = element;//修改值
return oldVal;//返回旧值
}
Android
public E set(int location, E object) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
//优化元素的查找
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
E result = link.data;
link.data = object;//修改元素数据
return result;
}
throw new IndexOutOfBoundsException();
}
六、查询元素
获取某一个位置的值
Java
public E get(int index) {
checkElementIndex(index);
return node(index).item;//查找之后获取值
}
Android
public E get(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
//优化查找
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
return link.data;
}
throw new IndexOutOfBoundsException();
}
七、包含元素
Java
public boolean contains(Object o) {
return indexOf(o) != -1;//判断序号是否为-1
}
public int indexOf(Object o) {
int index = 0;
if (o == null) {//从前向后查询，第一个null值，将该值的序号返回，如果没有返回-1
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {//从前向后查询，第一个equals的值，将该值的序号返回，如果没有返回-1
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) {//从后向前查询，第一个null值，将该值的序号返回，如果没有返回-1
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {//从后向前查询，第一个equals的值，将该值的序号返回，如果没有返回-1
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
Android
public boolean contains(Object object) {
Link<E> link = voidLink.next;
if (object != null) {//从前向后查找 第一个equals值，如果有返回true，没有返回false
while (link != voidLink) {//判断获取的link不是voidLin，用于判断链表是否有数据
if (object.equals(link.data)) {
return true;
}
link = link.next;
}
} else {//从前向后查找 第一个null值，如果有返回true，没有返回false
while (link != voidLink) {
if (link.data == null) {
return true;
}
link = link.next;
}
}
return false;
}
@Override
public int indexOf(Object object) {
int pos = 0;
Link<E> link = voidLink.next;
if (object != null) {//从前向后查找 第一个equals值，如果有返回该值的序号，没有返回-1
while (link != voidLink) {
if (object.equals(link.data)) {
return pos;
}
link = link.next;
pos++;
}
} else {//从前向后查找 第一个null值，如果有返回该值的序号，没有返回-1
while (link != voidLink) {
if (link.data == null) {
return pos;
}
link = link.next;
pos++;
}
}
return -1;
}
@Override
public int lastIndexOf(Object object) {
int pos = size;
Link<E> link = voidLink.previous;
if (object != null) {//从后向前查找 第一个equals值，如果有返回该值的序号，没有返回-1
while (link != voidLink) {
pos--;
if (object.equals(link.data)) {
return pos;
}
link = link.previous;
}
} else {//从后向前查找 第一个null值，如果有返回该值的序号，没有返回-1
while (link != voidLink) {
pos--;
if (link.data == null) {
return pos;
}
link = link.previous;
}
}
return -1;
}
八、集合的size
Java
public int size() {
return size;
}
Android
@Override
public int size() {
return size;
}
九、判空
没有实现判空，如果调用isEmpty()，调用的是AbstractCollection.java内的方法
十、其他
10.1 清空
Java
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
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++;
}
Android
voidLink前后指针直接指向自己，等待链表自动回收
@Override
public void clear() {
if (size > 0) {
size = 0;
voidLink.next = voidLink;
voidLink.previous = voidLink;
modCount++;
}
}
10.2 转换成数组
Java
public Object[] toArray() {
Object[] result = new Object[size];//创建新数组
int i = 0;
for (Node<E> x = first; x != null; x = x.next)//循环将集合的值放入数组
result[i++] = x.item;
return result;
}
@SuppressWarnings("unchecked")
public <T> 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<E> x = first; x != null; x = x.next)//循环将集合的值放入数组
result[i++] = x.item;
if (a.length > size)//将size位置设为空，表示size位置
a[size] = null;
return a;
}
Android
@Override
public Object[] toArray() {
int index = 0;
Object[] contents = new Object[size];//创建新数组
Link<E> link = voidLink.next;
while (link != voidLink) {//循环获取值，将值放入数组
contents[index++] = link.data;
link = link.next;
}
return contents;
}
@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] contents) {
int index = 0;
if (size > contents.length) {//传入数组长度不够
Class<?> ct = contents.getClass().getComponentType();
contents = (T[]) Array.newInstance(ct, size);//创建新数组并copy赋值
}
Link<E> link = voidLink.next;
while (link != voidLink) {//循环将值放入数组
contents[index++] = (T) link.data;
link = link.next;
}
if (index < contents.length) {//数组的长度过长，将size位置的值设为空
contents[index] = null;
}
return contents;
}
十一、迭代器
11.1 普通迭代器iterator()
Java
LinkedList本身没有实现iterator()的方法，调用该API实际调用的是抽象类AbstractSequentialList的API，该API调用的是AbstractList中的listIterator()方法，而且listIterator()这个方法实际调用的是listIterator(int index)这个方法，这个方法在LinkedList中被重载了，所以这个迭代器本质上是ListIterator，而且具体代码参考listIterator(int index)
AbstractSequentialList.java
public Iterator<E> iterator() {
return listIterator();//调用抽象类AbstractList的API
}
AbstractList.java
public ListIterator<E> listIterator() {
return listIterator(0);
}
public ListIterator<E> listIterator(final int index) {
rangeCheckForAdd(index);//判断是否越界
return new ListItr(index);
}
Android
LinkedList本身没有实现iterator()的方法，调用该API实际调用的是抽象类AbstractSequentialList的API，这个API直接调用的是listIterator(0)，这样由于LinkedList中重载了listIterator(int index)方法，所以结论等同于Java中的结论，具体参考11.2中的代码
AbstractSequentialList
@Override
public Iterator<E> iterator() {
return listIterator(0);
}
11.2 List特有迭代器ListIterator
Java
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;//下一个的游标，最后返回数据所在的位置，从1开始，0表示无数据
private int expectedModCount = modCount;//期望修改次数
ListItr(int index) {
// assert isPositionIndex(index);
//index==size表示指针越界，那么下一个位置就是null
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.next;//指针后移
nextIndex++;//下标增加
return lastReturned.item;//返回相应的值
}
public boolean hasPrevious() {
return nextIndex > 0;//是否有前节点
}
public E previous() {
checkForComodification();//检查是否修改过
if (!hasPrevious())//判断是否有前节点
throw new NoSuchElementException();
//next==null表示，表示游标指向了size，那么最后一个返回值应该就是last
//否则依次向前移动
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)//如果next==null表示，游标移到了最后位置，直接在最后添加即可。
linkLast(e);
else
linkBefore(e, next);//要么在next之前添加
nextIndex++;//最后位置增加
expectedModCount++;//修改值
}
//配合Lambda表达式使用，遍历
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();
}
}
Android
@Override
public ListIterator<E> listIterator(int location) {
return new LinkIterator<E>(this, location);
}
private static final class LinkIterator<ET> implements ListIterator<ET> {
int pos, expectedModCount;//数据位置，期望修改值
final LinkedList<ET> list;//链表
Link<ET> link, lastLink;//link当前位置，lastLink表示最后返回值
//link用于移动，lastLink用于记录
//lastLink还可以避免重复删除
LinkIterator(LinkedList<ET> object, int location) {
list = object;//将集合赋值
expectedModCount = list.modCount;//设置期望修改次数
if (location >= 0 && location <= list.size) {
// pos ends up as -1 if list is empty, it ranges from -1 to
// list.size - 1
// if link == voidLink then pos must == -1
link = list.voidLink;//link初始指向voidLink
if (location < list.size / 2) {//将link指向游标位置前一位
for (pos = -1; pos + 1 < location; pos++) {
link = link.next;
}
} else {
for (pos = list.size; pos >= location; pos--) {
link = link.previous;
}
}
} else {
throw new IndexOutOfBoundsException();
}
}
public void add(ET object) {
if (expectedModCount == list.modCount) {//判断集合中的数据是否增删过
Link<ET> next = link.next;//获取link位置的数据
Link<ET> newLink = new Link<ET>(object, link, next);//创建新的节点
link.next = newLink;//在link后位置插入新的节点
next.previous = newLink;//将原来后续位置的前节点修改为新节点
link = newLink;//将link向后移动一位
lastLink = null;//最后返回值设为空，避免重复删除
pos++;//位置增加
expectedModCount++;//增加修改次数
list.size++;//修改size
list.modCount++;//修改链表的修改次数
} else {
throw new ConcurrentModificationException();
}
}
public boolean hasNext() {//是否有后置节点
return link.next != list.voidLink;//等于voidLink表示链表没有后置节点了
}
public boolean hasPrevious() {//是否有前置节点
return link != list.voidLink;//等于voidLink表示链表没有前置节点了
}
public ET next() {//取出下一个值
if (expectedModCount == list.modCount) {//判断是否修改过
LinkedList.Link<ET> next = link.next;//向后移动
if (next != list.voidLink) {//判断下一个值是否是voidLink，是否还有值
lastLink = link = next;//将下一个值修改为最后取出的值
pos++;//位置增加
return link.data;//返回数据
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}
public int nextIndex() {//下一个的位置
return pos + 1;
}
public ET previous() {//是否有前置节点
if (expectedModCount == list.modCount) {//中间是否修改过值
if (link != list.voidLink) {//判断当前节点是否是voidLink
lastLink = link;//记录值
link = link.previous;//向前移动
pos--;
return lastLink.data;//返回数据
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}
public int previousIndex() {
return pos;//当前位置的前置节点
}
public void remove() {
if (expectedModCount == list.modCount) {//是否修改过
if (lastLink != null) {//最后的值部位空
Link<ET> next = lastLink.next;//记录最后值的后置节点
Link<ET> previous = lastLink.previous;//记录最后值的前置节点
next.previous = previous;//将最后值的前置节点修改为最后值的前置节点
previous.next = next;//将最后值的后置节点修改为最后值的后置节点
if (lastLink == link) {//判断link是否等于最后取得的值，如果等于将位置减掉
pos--;
}
link = previous;//将link向前移动一位
lastLink = null;//避免重复删除
expectedModCount++;
list.size--;
list.modCount++;
} else {
throw new IllegalStateException();
}
} else {
throw new ConcurrentModificationException();
}
}
public void set(ET object) {//设置值
if (expectedModCount == list.modCount) {
if (lastLink != null) {
lastLink.data = object;//将link指向位置的值修改为目标值
} else {
throw new IllegalStateException();
}
} else {
throw new ConcurrentModificationException();
}
}
}
11.3 倒序遍历
Java
Since 1.6 开始 将ListItr完全倒序执行
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
Android
从后向前遍历，没有使用正序遍历的倒用，从新写了实现
public Iterator<E> descendingIterator() {
return new ReverseLinkIterator<E>(this);
}
private class ReverseLinkIterator<ET> implements Iterator<ET> {
private int expectedModCount;
private final LinkedList<ET> list;
private Link<ET> link;
private boolean canRemove;
ReverseLinkIterator(LinkedList<ET> linkedList) {
list = linkedList;
expectedModCount = list.modCount;
link = list.voidLink;
canRemove = false;
}
public boolean hasNext() {
return link.previous != list.voidLink;
}
public ET next() {
if (expectedModCount == list.modCount) {
if (hasNext()) {
link = link.previous;
canRemove = true;
return link.data;
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}
public void remove() {
if (expectedModCount == list.modCount) {
if (canRemove) {
Link<ET> next = link.previous;
Link<ET> previous = link.next;
next.next = previous;
previous.previous = next;
link = previous;
list.size--;
list.modCount++;
expectedModCount++;
canRemove = false;
return;
}
throw new IllegalStateException();
}
throw new ConcurrentModificationException();
}
}
十二、遍历
- 采用for循环遍历
LinkedList<String> ll = new LinkedList<>();
......
for (int i = 0; i < ll.size(); i++) {
System.out.println(ll.get(i));
}
...
- 采用for-each循环遍历
LinkedList<String> ll = new LinkedList<>();
......
for (String str:ll) {
System.out.println(str);
}
...
- 使用普通迭代器遍历，内部实际使用的是ListIterator遍历
LinkedList<String> ll = new LinkedList<>();
......
Iterator<String> it = ll.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
System.out.println(it instanceof ListIterator);
...
- 使用ListIterator遍历，可向前向后遍历
LinkedList<String> ll = new LinkedList<>();
......
ListIterator<String> lit = ll.listIterator();
while(lit.hasNext()){
System.out.println(lit.next());
}
while(lit.hasPrevious()){
System.out.println(lit.previous());
}
...
- 使用倒序遍历，只能向前遍历
LinkedList<String> ll = new LinkedList<>();
......
Iterator<String> dit =ll.descendingIterator();
while (dit.hasNext()) {
System.out.println(dit.next());
}
......
十三、双端队列
实现了双端队列的一些方法，例如在对列的首尾位置添加，首尾位置移除等
双端队列简单来说，就是可以在首部或者尾部两个方向排队
13.1 增加
13.1.1 在首部增加
Java
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;//获取首节点
//创建新节点，新节点的首节点前节点为空，后节点为原首节点
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;//首节点设为新节点
if (f == null)//如果原来的首节点为空，也表示链表中没有数据，这条数据是插入的第一条数据，所以尾节点也是该条数据
last = newNode;
else//原首节点不为空，就将原首节点的前节点设为新节点
f.prev = newNode;
size++;
modCount++;
}
Android
public void addFirst(E object) {
addFirstImpl(object);
}
private boolean addFirstImpl(E object) {
//老的首节点
Link<E> oldFirst = voidLink.next;
//新节点，新节点的前节点为voidLink，后节点为原首节点
Link<E> newLink = new Link<E>(object, voidLink, oldFirst);
//将voidLink的后节点设置为新节点
voidLink.next = newLink;
oldFirst.previous = newLink;//将原首节点的前节点设为新节点
size++;//增加size
modCount++;//修改modCount
return true;
}
13.1.2 在尾部增加
Java和Android中的算法都与Add算法一样
Java
public void addLast(E e) {
linkLast(e);
}
Android
public void addLast(E object) {
addLastImpl(object);
}
13.1.3 其他增加
Java
since 1.5
public boolean offer(E e) {
return add(e);
}
/**
* Inserts the specified element at the front of this list.
*
* @param e the element to insert
* @return {@code true} (as specified by {@link Deque#offerFirst})
* @since 1.6
*/
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
/**
* Inserts the specified element at the end of this list.
*
* @param e the element to insert
* @return {@code true} (as specified by {@link Deque#offerLast})
* @since 1.6
*/
public boolean offerLast(E e) {
addLast(e);
return true;
}
Android
public boolean offer(E o) {
return addLastImpl(o);
}
/**
* {@inheritDoc}
*
* @see java.util.Deque#offerFirst(java.lang.Object)
* @since 1.6
*/
public boolean offerFirst(E e) {
return addFirstImpl(e);
}
/**
* {@inheritDoc}
*
* @see java.util.Deque#offerLast(java.lang.Object)
* @since 1.6
*/
public boolean offerLast(E e) {
return addLastImpl(e);
}
13.2 删除
13.2.1 删除第一个节点
Java
public E removeFirst() {
final Node<E> f = first;
if (f == null)//判断链表是否为空
throw new NoSuchElementException();
return unlinkFirst(f);
}
//将第一个移除链接
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;//获取第一个的值
final Node<E> next = f.next;//获取第一个的first
f.item = null;//将第一个节点的值置空
f.next = null; // help GC，将第一个节点的后节点置空
first = next;//将首节点设为第一个节点的后节点
if (next == null)//如果后节点为空，表示后续没有节点，链表置空
last = null;//将尾节点设空
else
next.prev = null;//将后节点的前节点置空，清除了原首节点与链表的连接关系
size--;
modCount++;
return element;
}
Android
感觉第一个节点没有置空，不知道是否会影响内存回收，而且第一个节点还是能指向链表
public E removeFirst() {
return removeFirstImpl();
}
private E removeFirstImpl() {
Link<E> first = voidLink.next;//获取首节点
if (first != voidLink) {//如果首节点不是voidLink
Link<E> next = first.next;//获取首节点的后节点
voidLink.next = next;//voidLink的后节点设为原首节点的后节点
next.previous = voidLink;//后节点的前节点设为voidLink
size--;//修改size
modCount++;//修改值增加
return first.data;//返回数据
}
//如果首节点为voidLink表示该集合为空，抛出异常
throw new NoSuchElementException();
}
13.2.2 删除第一个出现在链表中的节点
Java
since 1.6，调用13.2.1中的java代码
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
Android
since 1.6 ，具体参考4.3中的Android代码
public boolean removeFirstOccurrence(Object o) {
return removeFirstOccurrenceImpl(o);
}
13.2.3 删除最后一个节点
Java
public E removeLast() {
final Node<E> l = last;
if (l == null)//判断尾节点是否为空
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
// assert l == last && l != 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;
}
Android
删除节点与链表的连接，删除节点的值均未被置空
public E removeLast() {
return removeLastImpl();
}
private E removeLastImpl() {
Link<E> last = voidLink.previous;//获取voidLink的前节点，也就是尾节点
if (last != voidLink) {//如果不是只有voidLink
Link<E> previous = last.previous;//获取删除节点的前节点
voidLink.previous = previous;//将voidLink的前节点置为删除节点的前节点，这样删除节点的前节点就变成了尾节点
previous.next = voidLink;//将删除节点前节点的后节点设为voidLink
size--;
modCount++;
return last.data;
}
throw new NoSuchElementException();
}
13.2.4 删除最后一个出现在链表中节点
Java
since 1.6
public boolean removeLastOccurrence(Object o) {
if (o == null) {//如果删除的值为空，从后向前查找第一null值
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);//具体参考4.2中Java代码
return true;
}
}
} else {//如果不为空，则从后向前查找第一个equals的节点
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
Android
since 1.6
public boolean removeLastOccurrence(Object o) {
//获取反向迭代器，迭代器具体参考下面的迭代器相关代码
Iterator<E> iter = new ReverseLinkIterator<E>(this);
return removeOneOccurrence(o, iter);//具体参考13.2.1中Android代码
}
13.2.5 其他删除
Java
/**
* Retrieves and removes the head (first element) of this list.
*
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
*/
public E remove() {
return removeFirst();
}
/**
* Retrieves and removes the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/**
* Retrieves and removes the first element of this list,
* or returns {@code null} if this list is empty.
*
* @return the first element of this list, or {@code null} if
* this list is empty
* @since 1.6
*/
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/**
* Retrieves and removes the last element of this list,
* or returns {@code null} if this list is empty.
*
* @return the last element of this list, or {@code null} if
* this list is empty
* @since 1.6
*/
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
Android
public E poll() {
return size == 0 ? null : removeFirst();
}
public E remove() {
return removeFirstImpl();
}
/**
* {@inheritDoc}
*
* @see java.util.Deque#pollFirst()
* @since 1.6
*/
public E pollFirst() {
return (size == 0) ? null : removeFirstImpl();
}
/**
* {@inheritDoc}
*
* @see java.util.Deque#pollLast()
* @since 1.6
*/
public E pollLast() {
return (size == 0) ? null : removeLastImpl();
}
13.3 查询
Java
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
*/
public E element() {
return getFirst();
}
/**
* Retrieves, but does not remove, the first element of this list,
* or returns {@code null} if this list is empty.
*
* @return the first element of this list, or {@code null}
* if this list is empty
* @since 1.6
*/
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* Retrieves, but does not remove, the last element of this list,
* or returns {@code null} if this list is empty.
*
* @return the last element of this list, or {@code null}
* if this list is empty
* @since 1.6
*/
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
Android
public E peek() {
return peekFirstImpl();
}
private E peekFirstImpl() {
Link<E> first = voidLink.next;
return first == voidLink ? null : first.data;
}
/**
* {@inheritDoc}
*
* @see java.util.Deque#peekFirst()
* @since 1.6
*/
public E peekFirst() {
return peekFirstImpl();
}
/**
* {@inheritDoc}
*
* @see java.util.Deque#peekLast()
* @since 1.6
*/
public E peekLast() {
Link<E> last = voidLink.previous;
return (last == voidLink) ? null : last.data;
}
十四、栈
Java
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* Pushes an element onto the stack represented by this list. In other
* words, inserts the element at the front of this list.
*
* <p>This method is equivalent to {@link #addFirst}.
*
* @param e the element to push
* @since 1.6
*/
public void push(E e) {
addFirst(e);
}
/**
* Pops an element from the stack represented by this list. In other
* words, removes and returns the first element of this list.
*
* <p>This method is equivalent to {@link #removeFirst()}.
*
* @return the element at the front of this list (which is the top
* of the stack represented by this list)
* @throws NoSuchElementException if this list is empty
* @since 1.6
*/
public E pop() {
return removeFirst();
}
Android
public E peek() {
return peekFirstImpl();
}
/**
* {@inheritDoc}
*
* @see java.util.Deque#pop()
* @since 1.6
*/
public E pop() {
return removeFirstImpl();
}
/**
* {@inheritDoc}
*
* @see java.util.Deque#push(java.lang.Object)
* @since 1.6
*/
public void push(E e) {
addFirstImpl(e);
}
十五、总结
- LinkedList实现了双端队列的方法，双端队列简单来讲就是可以在头尾排队
- 双端队列包含栈的实现方法，所以LinkedList也可以当做栈使用
- java.util.Stack.java继承的是Vector，这个栈不太好用，JDK1.6之后使用LinkedList代替了，因为这个栈是直接继承了Vector，正常的表现方法应该抽象出一个接口出来，在使用具体的实现实现栈的功能。这个栈在1.0版本已经存在，也没办法修改。
- 在Android虽说数据结构表现上是双向循环链表，但并未提供双向循环API。
- 关于迭代器比ArrayList增加了一种倒序迭代器，而且普通迭代器和ListIterator是同一种实现，在Java中的倒序迭代器实际利用了ListIterator迭代器反向迭代
其他文章
容器解析
ArrayList解析
LinkedList解析
TreeMap解析(上)
TreeMap解析(下)
HashMap解析
LinkedHasMap解析(下)
Set解析
