一、概要
- Java中底層數(shù)據(jù)結構是鏈表、雙端鏈表，Android中數(shù)據(jù)結構是雙向循環(huán)鏈表
- 非線程安全數(shù)據(jù)結構,允許元素為null
- 繼承了抽象類AbstractSequentialList，它是AbstractList的一個子類。實現(xiàn)了List<E>, Deque<E>(雙端隊列抽象), Cloneable, Serializable的接口。
- 由于底層數(shù)據(jù)結構是鏈表，所以增刪元素的時候只需要修改元素的指針即可，時間效率比較高，因為不需要預留空間，所以空間效率也比較高。
- 沒有時間RandomAccess，表示在隨機訪問上效率比較低。所以隨機訪問時時間效率也不高。在隨機訪問數(shù)據(jù)上做過優(yōu)化，如果查找的位置位于鏈表的前半部從前向后遍歷，如果位于鏈表的后半部，從后向前遍歷
二、構造函數(shù)
Java
transient int size = 0;//大小
/**
* Pointer to first node.開始節(jié)點
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.最后的節(jié)點
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
//默認構造函數(shù)
public LinkedList() {
}
//集合數(shù)據(jù)構造函數(shù)
public LinkedList(Collection<? extends E> c) {
this();//調(diào)用默認構造函數(shù)
addAll(c);//將集合中的數(shù)據(jù)全部加入當前對象
}
節(jié)點信息
private static class Node<E> {
E item;
Node<E> next;//下一個節(jié)點
Node<E> prev;//前一個節(jié)點
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
結構展示
Java內(nèi)LinkedList結構信息
Android
transient int size = 0;
transient Link<E> voidLink;//void節(jié)點，該節(jié)點的next是首節(jié)點，該節(jié)點的前節(jié)點是尾節(jié)點，如果集合為空，那么void的首尾節(jié)點都是自己
public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
public LinkedList(Collection<? extends E> collection) {
this();
addAll(collection);
}
節(jié)點信息
private static final class Link<ET> {
ET data;
Link<ET> previous, next;//前后節(jié)點
Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
previous = p;
next = n;
}
}
結構信息
Android內(nèi)LinkedList結構信息
三、增加元素
3.1 普通增加一個對象
默認增加是指在鏈表的尾部增加一個對象
Java
public boolean add(E e) {
linkLast(e);
return true;//增加成功，返回true
}
void linkLast(E e) {
final Node<E> l = last;//獲取尾節(jié)點
//創(chuàng)建節(jié)點，節(jié)點的前節(jié)點指向已有的尾節(jié)點，后節(jié)點指向空
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;//將尾節(jié)點指向新創(chuàng)建的節(jié)點
if (l == null)//如果上一尾節(jié)點為空，表示鏈表沒有數(shù)據(jù)，那么newNode表示第一添加的節(jié)點
first = newNode;//所以首節(jié)點也會指向新創(chuàng)建的節(jié)點
else//如果上一尾節(jié)點不為空，表示鏈表中有數(shù)據(jù)
l.next = newNode;//上一節(jié)點的后節(jié)點就需要修改為新節(jié)點
size++;//size增加
modCount++;//修改次數(shù)增加
}
Android
public boolean add(E object) {
return addLastImpl(object);
}
private boolean addLastImpl(E object) {
Link<E> oldLast = voidLink.previous;//獲取v的前節(jié)點，剛開始的時候為v自己
//創(chuàng)建新的節(jié)點，新節(jié)點前節(jié)點是老鏈表的有效尾節(jié)點，后節(jié)點為voidLink
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
voidLink.previous = newLink;//將v節(jié)點的前節(jié)點設為新節(jié)點
oldLast.next = newLink;//將老的尾節(jié)點后節(jié)點設為新節(jié)點
size++;//size變大
modCount++;//修改數(shù)增加
return true;
}
3.2 在某一位置增加一個對象
Java
public void add(int index, E element) {
checkPositionIndex(index);//數(shù)組越界判斷
if (index == size)//如果插入位置為size大小位置
linkLast(element);//直接在最后插入即可
else
linkBefore(element, node(index));
}
//獲取node的節(jié)點
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;//獲取查到節(jié)點的前節(jié)點
//創(chuàng)建新節(jié)點，新節(jié)點和后節(jié)點分別為，查到的節(jié)點的前節(jié)點和查到的節(jié)點
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;//將查到的節(jié)點的前節(jié)點設為新節(jié)點
if (pred == null)//如果查到的節(jié)點原前節(jié)點為空，表示查到的節(jié)點為首節(jié)點
first = newNode;//將首節(jié)點設為新節(jié)點
else//如果查到的節(jié)點的原前節(jié)點存在，那么將原前節(jié)點的后節(jié)點設為新節(jié)點
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;//獲得查找到位置前節(jié)點
//創(chuàng)建新的節(jié)點，前后節(jié)點分別是：查找到的節(jié)點原前節(jié)點和查找到的節(jié)點
Link<E> newLink = new Link<E>(object, previous, link);
previous.next = newLink;//將原前節(jié)點的后節(jié)點設為新節(jié)點
link.previous = newLink;//將查找到的節(jié)點的前節(jié)點設為新節(jié)點
//不用擔心previous為null，因為Android中數(shù)據(jù)結構是雙向循環(huán)鏈表
//那么在0位置添加的時候，previous指向了voidLink，不為空
//不用擔心link為null，因為Android中數(shù)據(jù)結構是雙向循環(huán)鏈表
//那么在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;//獲取尾部節(jié)點，最后節(jié)點
//遍歷集合
for (E e : elements) {
//創(chuàng)建新節(jié)點，新節(jié)點的前節(jié)點是尾部節(jié)點，后節(jié)點為空，因為后節(jié)點不宜在循環(huán)過程中設置為voidLink
Link<E> newLink = new Link<E>(e, previous, null);
//將前節(jié)點的后節(jié)點設置為新節(jié)點
previous.next = newLink;
//最后的節(jié)點就變成了新節(jié)點
previous = newLink;
}
previous.next = voidLink;//將最后節(jié)點的后節(jié)點設為voidLink
voidLink.previous = previous;//將voidLink的前節(jié)點設為尾節(jié)點
size += adding;
modCount++;
return true;
}
3.4 在某一位置增加集合中的全部對象
Java
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);//檢查是否越界
Object[] a = c.toArray();//將集合轉換成數(shù)組
int numNew = a.length;
if (numNew == 0)//如果數(shù)組的數(shù)量為空表示集合為空集合。
return false;
Node<E> pred, succ;//插入位置的前后
if (index == size) {//如果插入位置為尾部
succ = null;//插入位置的節(jié)點，該節(jié)點在數(shù)據(jù)插入后會變成插入節(jié)點的尾節(jié)點，但是插入的是末尾所以為空
pred = last;//插入位置是末尾，所以插入數(shù)據(jù)之后插入數(shù)據(jù)的前節(jié)點是尾節(jié)點
} else {
succ = node(index);//插入位置的節(jié)點，該節(jié)點在數(shù)據(jù)插入后會變成插入節(jié)點的后節(jié)點
pred = succ.prev;//插入位置的前節(jié)點，該節(jié)點在數(shù)據(jù)插入后會變成插入節(jié)點的前節(jié)點
}
for (Object o : a) {//循環(huán)遍歷數(shù)組
@SuppressWarnings("unchecked")
E e = (E) o;//獲取對象
//創(chuàng)建對象，該對象的前節(jié)點是pred，后節(jié)點為空
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)//如果前節(jié)點為空，表示插入位置未首部
first = newNode;//所以首節(jié)點指向了新創(chuàng)建的節(jié)點
else
pred.next = newNode;//如果前節(jié)點不為空，那么前節(jié)點的后節(jié)點就是新創(chuàng)建的節(jié)點
pred = newNode;//將前節(jié)點修改為新節(jié)點，表示新節(jié)點已經(jīng)插入鏈表
}
if (succ == null) {//如果尾節(jié)點為空，表示插入位置是鏈表尾部
last = pred;//將尾節(jié)點設置為最新插入的節(jié)點
} else {
pred.next = succ;//將最新插入的節(jié)點的后節(jié)點設置為后節(jié)點
succ.prev = pred;//將后節(jié)點的前節(jié)點設置為最新插入的節(jié)點
}
size += numNew;//修改size
modCount++;//修改數(shù)量增加
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) {//判斷插入集合的數(shù)量
return false;
}
//判斷插入的數(shù)據(jù)是否是自己，如果是將集合改為ArrayList
Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;
//獲取插入位置的節(jié)點，做過簡單優(yōu)化
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是插入位置的前節(jié)點
//此時next是插入位置的后節(jié)點
Link<E> next = previous.next;
for (E e : elements) {//循環(huán)插入集合中的數(shù)據(jù)
//創(chuàng)建新節(jié)點，新節(jié)點的前節(jié)點指向原來的前節(jié)點
Link<E> newLink = new Link<E>(e, previous, null);
//將前節(jié)點的后節(jié)點設為新節(jié)點
previous.next = newLink;
previous = newLink;//前節(jié)點變化成新節(jié)點
}
//將前節(jié)點的后節(jié)點設置為原插入節(jié)點信息
previous.next = next;
//將原插入節(jié)點的前節(jié)點設置為最新的前節(jié)點
next.previous = previous;
size += adding;//修改size
modCount++;//修改modCount
return true;
}
四、刪除元素
4.1 默認刪除
調(diào)用的刪除第一個節(jié)點的方法，具體參考13.2.1
Java
public E remove() {
return removeFirst();//調(diào)用刪除第一個
}
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));//刪除對應位置的節(jié)點
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;//值
final Node<E> next = x.next;//獲取刪除節(jié)點的后節(jié)點
final Node<E> prev = x.prev;//獲取刪除節(jié)點的前節(jié)點
if (prev == null) {//如果刪除節(jié)點前節(jié)點為空，表示刪除的節(jié)點為首節(jié)點
first = next;//將首節(jié)點設為刪除節(jié)點的后節(jié)點
} else {//不是刪除首節(jié)點
prev.next = next;//將刪除節(jié)點的前節(jié)點的后節(jié)點設為刪除節(jié)點的后節(jié)點
x.prev = null;//將刪除節(jié)點前節(jié)點置空
}
if (next == null) {//如果刪除節(jié)點的后節(jié)點為空，表示刪除的節(jié)點是尾節(jié)點
last = prev;//將尾節(jié)點設為刪除節(jié)點的前節(jié)點
} else {//不是刪除尾節(jié)點
next.prev = prev;//將刪除節(jié)點后節(jié)點的前節(jié)點設為刪除節(jié)點的前節(jié)點
x.next = null;//將刪除節(jié)點的后節(jié)點置空
}
x.item = null;//將刪除節(jié)點的item置空
size--;
modCount++;
return element;
}
Android
刪除的節(jié)點連接信息，以及刪除節(jié)點的值均未置空。。。
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是刪除位置節(jié)點的前節(jié)點
//此時next是刪除位置節(jié)點的后節(jié)點
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;//將刪除節(jié)點前節(jié)點的后節(jié)點設為刪除節(jié)點的后節(jié)點
next.previous = previous;//將刪除節(jié)點后節(jié)點的前節(jié)點設為刪除節(jié)點的前節(jié)點
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}
4.3 刪除一個對象
Java
public boolean remove(Object o) {
if (o == null) {//如果為空，則從前向后查找第一個null值的節(jié)點
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);//具體參考4.2中Java代碼
return true;
}
}
} else {//如果不為空，則從前向后查找第一個equals的節(jié)點
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);
}
//刪除一個在迭代器中出現(xiàn)的值
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);//檢查數(shù)組越界
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;
//優(yōu)化元素的查找
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;//修改元素數(shù)據(jù)
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;
//優(yōu)化查找
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，用于判斷鏈表是否有數(shù)據(jù)
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;
}
九、判空
沒有實現(xiàn)判空，如果調(diào)用isEmpty()，調(diào)用的是AbstractCollection.java內(nèi)的方法
十、其他
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; ) {//循環(huán)遍歷置空
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 轉換成數(shù)組
Java
public Object[] toArray() {
Object[] result = new Object[size];//創(chuàng)建新數(shù)組
int i = 0;
for (Node<E> x = first; x != null; x = x.next)//循環(huán)將集合的值放入數(shù)組
result[i++] = x.item;
return result;
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)//傳入的數(shù)組長度不夠，從新創(chuàng)建數(shù)組并賦值
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)//循環(huán)將集合的值放入數(shù)組
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];//創(chuàng)建新數(shù)組
Link<E> link = voidLink.next;
while (link != voidLink) {//循環(huán)獲取值，將值放入數(shù)組
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) {//傳入數(shù)組長度不夠
Class<?> ct = contents.getClass().getComponentType();
contents = (T[]) Array.newInstance(ct, size);//創(chuàng)建新數(shù)組并copy賦值
}
Link<E> link = voidLink.next;
while (link != voidLink) {//循環(huán)將值放入數(shù)組
contents[index++] = (T) link.data;
link = link.next;
}
if (index < contents.length) {//數(shù)組的長度過長，將size位置的值設為空
contents[index] = null;
}
return contents;
}
十一、迭代器
11.1 普通迭代器iterator()
Java
LinkedList本身沒有實現(xiàn)iterator()的方法，調(diào)用該API實際調(diào)用的是抽象類AbstractSequentialList的API，該API調(diào)用的是AbstractList中的listIterator()方法，而且listIterator()這個方法實際調(diào)用的是listIterator(int index)這個方法，這個方法在LinkedList中被重載了，所以這個迭代器本質上是ListIterator，而且具體代碼參考listIterator(int index)
AbstractSequentialList.java
public Iterator<E> iterator() {
return listIterator();//調(diào)用抽象類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本身沒有實現(xiàn)iterator()的方法，調(diào)用該API實際調(diào)用的是抽象類AbstractSequentialList的API，這個API直接調(diào)用的是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;//下一個的游標，最后返回數(shù)據(jù)所在的位置，從1開始，0表示無數(shù)據(jù)
private int expectedModCount = modCount;//期望修改次數(shù)
ListItr(int index) {
// assert isPositionIndex(index);
//index==size表示指針越界，那么下一個位置就是null
next = (index == size) ? null : node(index);//將指針指向相應的位置
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;//是否有后續(xù)值
}
public E next() {
checkForComodification();//檢查是否修改過
if (!hasNext())//沒有后續(xù)值
throw new NoSuchElementException();
lastReturned = next;//最后返回值是next
next = next.next;//指針后移
nextIndex++;//下標增加
return lastReturned.item;//返回相應的值
}
public boolean hasPrevious() {
return nextIndex > 0;//是否有前節(jié)點
}
public E previous() {
checkForComodification();//檢查是否修改過
if (!hasPrevious())//判斷是否有前節(jié)點
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;//游標前置
}
//移除數(shù)據(jù)
public void remove() {
checkForComodification();//檢查是否修改過
if (lastReturned == null)//是否探尋到值，如果沒有探尋到值，自然不讓移除
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;//記錄下一個的值
unlink(lastReturned);//將數(shù)據(jù)移除
if (next == lastReturned)//將指針后移
next = lastNext;
else
nextIndex--;//向前移除數(shù)據(jù)
lastReturned = null;//避免連續(xù)移除
expectedModCount++;//增加修改次數(shù)
}
public void set(E e) {//修改值
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();//檢查是否修改數(shù)據(jù)
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;//數(shù)據(jù)位置，期望修改值
final LinkedList<ET> list;//鏈表
Link<ET> link, lastLink;//link當前位置，lastLink表示最后返回值
//link用于移動，lastLink用于記錄
//lastLink還可以避免重復刪除
LinkIterator(LinkedList<ET> object, int location) {
list = object;//將集合賦值
expectedModCount = list.modCount;//設置期望修改次數(shù)
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) {//判斷集合中的數(shù)據(jù)是否增刪過
Link<ET> next = link.next;//獲取link位置的數(shù)據(jù)
Link<ET> newLink = new Link<ET>(object, link, next);//創(chuàng)建新的節(jié)點
link.next = newLink;//在link后位置插入新的節(jié)點
next.previous = newLink;//將原來后續(xù)位置的前節(jié)點修改為新節(jié)點
link = newLink;//將link向后移動一位
lastLink = null;//最后返回值設為空，避免重復刪除
pos++;//位置增加
expectedModCount++;//增加修改次數(shù)
list.size++;//修改size
list.modCount++;//修改鏈表的修改次數(shù)
} else {
throw new ConcurrentModificationException();
}
}
public boolean hasNext() {//是否有后置節(jié)點
return link.next != list.voidLink;//等于voidLink表示鏈表沒有后置節(jié)點了
}
public boolean hasPrevious() {//是否有前置節(jié)點
return link != list.voidLink;//等于voidLink表示鏈表沒有前置節(jié)點了
}
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;//返回數(shù)據(jù)
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}
public int nextIndex() {//下一個的位置
return pos + 1;
}
public ET previous() {//是否有前置節(jié)點
if (expectedModCount == list.modCount) {//中間是否修改過值
if (link != list.voidLink) {//判斷當前節(jié)點是否是voidLink
lastLink = link;//記錄值
link = link.previous;//向前移動
pos--;
return lastLink.data;//返回數(shù)據(jù)
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}
public int previousIndex() {
return pos;//當前位置的前置節(jié)點
}
public void remove() {
if (expectedModCount == list.modCount) {//是否修改過
if (lastLink != null) {//最后的值部位空
Link<ET> next = lastLink.next;//記錄最后值的后置節(jié)點
Link<ET> previous = lastLink.previous;//記錄最后值的前置節(jié)點
next.previous = previous;//將最后值的前置節(jié)點修改為最后值的前置節(jié)點
previous.next = next;//將最后值的后置節(jié)點修改為最后值的后置節(jié)點
if (lastLink == link) {//判斷l(xiāng)ink是否等于最后取得的值，如果等于將位置減掉
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完全倒序執(zhí)行
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
從后向前遍歷，沒有使用正序遍歷的倒用，從新寫了實現(xiàn)
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循環(huán)遍歷
LinkedList<String> ll = new LinkedList<>();
......
for (int i = 0; i < ll.size(); i++) {
System.out.println(ll.get(i));
}
...
- 采用for-each循環(huán)遍歷
LinkedList<String> ll = new LinkedList<>();
......
for (String str:ll) {
System.out.println(str);
}
...
- 使用普通迭代器遍歷，內(nèi)部實際使用的是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());
}
......
十三、雙端隊列
實現(xiàn)了雙端隊列的一些方法，例如在對列的首尾位置添加，首尾位置移除等
雙端隊列簡單來說，就是可以在首部或者尾部兩個方向排隊
13.1 增加
13.1.1 在首部增加
Java
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;//獲取首節(jié)點
//創(chuàng)建新節(jié)點，新節(jié)點的首節(jié)點前節(jié)點為空，后節(jié)點為原首節(jié)點
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;//首節(jié)點設為新節(jié)點
if (f == null)//如果原來的首節(jié)點為空，也表示鏈表中沒有數(shù)據(jù)，這條數(shù)據(jù)是插入的第一條數(shù)據(jù)，所以尾節(jié)點也是該條數(shù)據(jù)
last = newNode;
else//原首節(jié)點不為空，就將原首節(jié)點的前節(jié)點設為新節(jié)點
f.prev = newNode;
size++;
modCount++;
}
Android
public void addFirst(E object) {
addFirstImpl(object);
}
private boolean addFirstImpl(E object) {
//老的首節(jié)點
Link<E> oldFirst = voidLink.next;
//新節(jié)點，新節(jié)點的前節(jié)點為voidLink，后節(jié)點為原首節(jié)點
Link<E> newLink = new Link<E>(object, voidLink, oldFirst);
//將voidLink的后節(jié)點設置為新節(jié)點
voidLink.next = newLink;
oldFirst.previous = newLink;//將原首節(jié)點的前節(jié)點設為新節(jié)點
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 刪除第一個節(jié)點
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;//將第一個節(jié)點的值置空
f.next = null; // help GC，將第一個節(jié)點的后節(jié)點置空
first = next;//將首節(jié)點設為第一個節(jié)點的后節(jié)點
if (next == null)//如果后節(jié)點為空，表示后續(xù)沒有節(jié)點，鏈表置空
last = null;//將尾節(jié)點設空
else
next.prev = null;//將后節(jié)點的前節(jié)點置空，清除了原首節(jié)點與鏈表的連接關系
size--;
modCount++;
return element;
}
Android
感覺第一個節(jié)點沒有置空，不知道是否會影響內(nèi)存回收，而且第一個節(jié)點還是能指向鏈表
public E removeFirst() {
return removeFirstImpl();
}
private E removeFirstImpl() {
Link<E> first = voidLink.next;//獲取首節(jié)點
if (first != voidLink) {//如果首節(jié)點不是voidLink
Link<E> next = first.next;//獲取首節(jié)點的后節(jié)點
voidLink.next = next;//voidLink的后節(jié)點設為原首節(jié)點的后節(jié)點
next.previous = voidLink;//后節(jié)點的前節(jié)點設為voidLink
size--;//修改size
modCount++;//修改值增加
return first.data;//返回數(shù)據(jù)
}
//如果首節(jié)點為voidLink表示該集合為空，拋出異常
throw new NoSuchElementException();
}
13.2.2 刪除第一個出現(xiàn)在鏈表中的節(jié)點
Java
since 1.6，調(diào)用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 刪除最后一個節(jié)點
Java
public E removeLast() {
final Node<E> l = last;
if (l == null)//判斷尾節(jié)點是否為空
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;//獲取節(jié)點的值
final Node<E> prev = l.prev;//獲取節(jié)點的前節(jié)點
l.item = null;//將刪除節(jié)點的值置為空
l.prev = null; // help GC，將刪除節(jié)點的前節(jié)點置為空
last = prev;//將尾節(jié)點設為刪除節(jié)點的前節(jié)點
if (prev == null)//如果前節(jié)點為空，表示鏈表已經(jīng)沒有數(shù)據(jù)了
first = null;
else
prev.next = null;//將刪除節(jié)點前節(jié)點的后節(jié)點置為空
size--;
modCount++;
return element;
}
Android
刪除節(jié)點與鏈表的連接，刪除節(jié)點的值均未被置空
public E removeLast() {
return removeLastImpl();
}
private E removeLastImpl() {
Link<E> last = voidLink.previous;//獲取voidLink的前節(jié)點，也就是尾節(jié)點
if (last != voidLink) {//如果不是只有voidLink
Link<E> previous = last.previous;//獲取刪除節(jié)點的前節(jié)點
voidLink.previous = previous;//將voidLink的前節(jié)點置為刪除節(jié)點的前節(jié)點，這樣刪除節(jié)點的前節(jié)點就變成了尾節(jié)點
previous.next = voidLink;//將刪除節(jié)點前節(jié)點的后節(jié)點設為voidLink
size--;
modCount++;
return last.data;
}
throw new NoSuchElementException();
}
13.2.4 刪除最后一個出現(xiàn)在鏈表中節(jié)點
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的節(jié)點
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實現(xiàn)了雙端隊列的方法，雙端隊列簡單來講就是可以在頭尾排隊
- 雙端隊列包含棧的實現(xiàn)方法，所以LinkedList也可以當做棧使用
- java.util.Stack.java繼承的是Vector，這個棧不太好用，JDK1.6之后使用LinkedList代替了，因為這個棧是直接繼承了Vector，正常的表現(xiàn)方法應該抽象出一個接口出來，在使用具體的實現(xiàn)實現(xiàn)棧的功能。這個棧在1.0版本已經(jīng)存在，也沒辦法修改。
- 在Android雖說數(shù)據(jù)結構表現(xiàn)上是雙向循環(huán)鏈表，但并未提供雙向循環(huán)API。
- 關于迭代器比ArrayList增加了一種倒序迭代器，而且普通迭代器和ListIterator是同一種實現(xiàn)，在Java中的倒序迭代器實際利用了ListIterator迭代器反向迭代
其他文章
容器解析
ArrayList解析
LinkedList解析
TreeMap解析(上)
TreeMap解析(下)
HashMap解析
LinkedHasMap解析(下)
Set解析
