搭建正规网站,小程序开发难不难,建设银陕西省分行网站,专门做评论的网站LinkedList简介LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList 实现 List 接口#xff0c;能对它进行队列操作。LinkedList 实现 Deque 接口#xff0c;即能将LinkedList当作双端队列使用。LinkedList 实…LinkedList简介LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList 实现 List 接口能对它进行队列操作。LinkedList 实现 Deque 接口即能将LinkedList当作双端队列使用。LinkedList 实现了Cloneable接口即覆盖了函数clone()能克隆。LinkedList 实现java.io.Serializable接口这意味着LinkedList支持序列化能通过序列化去传输。LinkedList 是非同步的。LinkedList构造函数// 默认构造函数
LinkedList()// 创建一个LinkedList保护Collection中的全部元素。
LinkedList(Collection? extends E collection)LinkedList的API LinkedList的API
boolean add(E object)
void add(int location, E object)
boolean addAll(Collection? extends E collection)
boolean addAll(int location, Collection? extends E collection)
void addFirst(E object)
void addLast(E object)
void clear()
Object clone()
boolean contains(Object object)
IteratorE descendingIterator()
E element()
E get(int location)
E getFirst()
E getLast()
int indexOf(Object object)
int lastIndexOf(Object object)
ListIteratorE listIterator(int location)
boolean offer(E o)
boolean offerFirst(E e)
boolean offerLast(E e)
E peek()
E peekFirst()
E peekLast()
E poll()
E pollFirst()
E pollLast()
E pop()
void push(E e)
E remove()
E remove(int location)
boolean remove(Object object)
E removeFirst()
boolean removeFirstOccurrence(Object o)
E removeLast()
boolean removeLastOccurrence(Object o)
E set(int location, E object)
int size()
T T[] toArray(T[] contents)
Object[] toArray()AbstractSequentialList简介在介绍LinkedList的源码之前先介绍一下AbstractSequentialList。毕竟LinkedList是AbstractSequentialList的子类。AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些函数。这些接口都是随机访问List的LinkedList是双向链表既然它继承于AbstractSequentialList就相当于已经实现了“get(int index)这些接口”。此外我们若需要通过AbstractSequentialList自己实现一个列表只需要扩展此类并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。LinkedList数据结构java.lang.Object ↳ java.util.AbstractCollectionE ↳ java.util.AbstractListE ↳ java.util.AbstractSequentialListE ↳ java.util.LinkedListEpublic class LinkedListE extends AbstractSequentialListE implements ListE, DequeE, Cloneable, java.io.Serializable {}LinkedList与Collection关系如下图LinkedList的本质是双向链表。(01) LinkedList继承于AbstractSequentialList并且实现了Dequeue接口。(02) LinkedList包含两个重要的成员header和size。header是双向链表的表头它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量 previous, next, element。其中previous是该节点的上一个节点next是该节点的下一个节点element是该节点所包含的值。size是双向链表中节点的个数。LinkedList源码解析LinkedList实际上是通过双向链表去实现的。既然是双向链表那么它的顺序访问会非常高效而随机访问效率比较低。 既然LinkedList是通过双向链表的但是它也实现了List接口{也就是说它实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”}。LinkedList是如何实现List的这些接口的如何将“双向链表和索引值联系起来的” 实际原理非常简单它就是通过一个计数索引值来实现的。例如当我们调用get(int location)时首先会比较“location”和“双向链表长度的1/2”若前者大则从链表头开始往后查找直到location位置否则从链表末尾开始先前查找直到location位置。 这就是“双线链表和索引值联系起来”的方法。package java.util;public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializable
{// 链表的表头表头不包含任何数据。Entry是个链表类数据结构。private transient EntryE header new EntryE(null, null, null);// LinkedList中元素个数private transient int size 0;// 默认构造函数创建一个空的链表public LinkedList() {header.next header.previous header;}// 包含“集合”的构造函数:创建一个包含“集合”的LinkedListpublic LinkedList(Collection? extends E c) {this();addAll(c);}// 获取LinkedList的第一个元素public E getFirst() {if (size0)throw new NoSuchElementException();// 链表的表头header中不包含数据。// 这里返回header所指下一个节点所包含的数据。return header.next.element;}// 获取LinkedList的最后一个元素public E getLast() {if (size0)throw new NoSuchElementException();// 由于LinkedList是双向链表而表头header不包含数据。// 因而这里返回表头header的前一个节点所包含的数据。return header.previous.element;}// 删除LinkedList的第一个元素public E removeFirst() {return remove(header.next);}// 删除LinkedList的最后一个元素public E removeLast() {return remove(header.previous);}// 将元素添加到LinkedList的起始位置public void addFirst(E e) {addBefore(e, header.next);}// 将元素添加到LinkedList的结束位置public void addLast(E e) {addBefore(e, header);}// 判断LinkedList是否包含元素(o)public boolean contains(Object o) {return indexOf(o) ! -1;}// 返回LinkedList的大小public int size() {return size;}// 将元素(E)添加到LinkedList中public boolean add(E e) {// 将节点(节点数据是e)添加到表头(header)之前。// 即将节点添加到双向链表的末端。addBefore(e, header);return true;}// 从LinkedList中删除元素(o)// 从链表开始查找如存在元素(o)则删除该元素并返回true// 否则返回false。public boolean remove(Object o) {if (onull) {// 若o为null的删除情况for (EntryE e header.next; e ! header; e e.next) {if (e.elementnull) {remove(e);return true;}}} else {// 若o不为null的删除情况for (EntryE e header.next; e ! header; e e.next) {if (o.equals(e.element)) {remove(e);return true;}}}return false;}// 将“集合(c)”添加到LinkedList中。// 实际上是从双向链表的末尾开始将“集合(c)”添加到双向链表中。public boolean addAll(Collection? extends E c) {return addAll(size, c);}// 从双向链表的index开始将“集合(c)”添加到双向链表中。public boolean addAll(int index, Collection? extends E c) {if (index 0 || index size)throw new IndexOutOfBoundsException(Index: index, Size: size);Object[] a c.toArray();// 获取集合的长度int numNew a.length;if (numNew0)return false;modCount;// 设置“当前要插入节点的后一个节点”EntryE successor (indexsize ? header : entry(index));// 设置“当前要插入节点的前一个节点”EntryE predecessor successor.previous;// 将集合(c)全部插入双向链表中for (int i0; inumNew; i) {EntryE e new EntryE((E)a[i], successor, predecessor);predecessor.next e;predecessor e;}successor.previous predecessor;// 调整LinkedList的实际大小size numNew;return true;}// 清空双向链表public void clear() {EntryE e header.next;// 从表头开始逐个向后遍历对遍历到的节点执行一下操作// (01) 设置前一个节点为null// (02) 设置当前节点的内容为null// (03) 设置后一个节点为“新的当前节点”while (e ! header) {EntryE next e.next;e.next e.previous null;e.element null;e next;}header.next header.previous header;// 设置大小为0size 0;modCount;}// 返回LinkedList指定位置的元素public E get(int index) {return entry(index).element;}// 设置index位置对应的节点的值为elementpublic E set(int index, E element) {EntryE e entry(index);E oldVal e.element;e.element element;return oldVal;}// 在index前添加节点且节点的值为elementpublic void add(int index, E element) {addBefore(element, (indexsize ? header : entry(index)));}// 删除index位置的节点public E remove(int index) {return remove(entry(index));}// 获取双向链表中指定位置的节点private EntryE entry(int index) {if (index 0 || index size)throw new IndexOutOfBoundsException(Index: index, Size: size);EntryE e header;// 获取index处的节点。// 若index 双向链表长度的1/2,则从前先后查找;// 否则从后向前查找。if (index (size 1)) {for (int i 0; i index; i)e e.next;} else {for (int i size; i index; i--)e e.previous;}return e;}// 从前向后查找返回“值为对象(o)的节点对应的索引”// 不存在就返回-1public int indexOf(Object o) {int index 0;if (onull) {for (Entry e header.next; e ! header; e e.next) {if (e.elementnull)return index;index;}} else {for (Entry e header.next; e ! header; e e.next) {if (o.equals(e.element))return index;index;}}return -1;}// 从后向前查找返回“值为对象(o)的节点对应的索引”// 不存在就返回-1public int lastIndexOf(Object o) {int index size;if (onull) {for (Entry e header.previous; e ! header; e e.previous) {index--;if (e.elementnull)return index;}} else {for (Entry e header.previous; e ! header; e e.previous) {index--;if (o.equals(e.element))return index;}}return -1;}// 返回第一个节点// 若LinkedList的大小为0,则返回nullpublic E peek() {if (size0)return null;return getFirst();}// 返回第一个节点// 若LinkedList的大小为0,则抛出异常public E element() {return getFirst();}// 删除并返回第一个节点// 若LinkedList的大小为0,则返回nullpublic E poll() {if (size0)return null;return removeFirst();}// 将e添加双向链表末尾public boolean offer(E e) {return add(e);}// 将e添加双向链表开头public boolean offerFirst(E e) {addFirst(e);return true;}// 将e添加双向链表末尾public boolean offerLast(E e) {addLast(e);return true;}// 返回第一个节点// 若LinkedList的大小为0,则返回nullpublic E peekFirst() {if (size0)return null;return getFirst();}// 返回最后一个节点// 若LinkedList的大小为0,则返回nullpublic E peekLast() {if (size0)return null;return getLast();}// 删除并返回第一个节点// 若LinkedList的大小为0,则返回nullpublic E pollFirst() {if (size0)return null;return removeFirst();}// 删除并返回最后一个节点// 若LinkedList的大小为0,则返回nullpublic E pollLast() {if (size0)return null;return removeLast();}// 将e插入到双向链表开头public void push(E e) {addFirst(e);}// 删除并返回第一个节点public E pop() {return removeFirst();}// 从LinkedList开始向后查找删除第一个值为元素(o)的节点// 从链表开始查找如存在节点的值为元素(o)的节点则删除该节点public boolean removeFirstOccurrence(Object o) {return remove(o);}// 从LinkedList末尾向前查找删除第一个值为元素(o)的节点// 从链表开始查找如存在节点的值为元素(o)的节点则删除该节点public boolean removeLastOccurrence(Object o) {if (onull) {for (EntryE e header.previous; e ! header; e e.previous) {if (e.elementnull) {remove(e);return true;}}} else {for (EntryE e header.previous; e ! header; e e.previous) {if (o.equals(e.element)) {remove(e);return true;}}}return false;}// 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器)public ListIteratorE listIterator(int index) {return new ListItr(index);}// List迭代器private class ListItr implements ListIteratorE {// 上一次返回的节点private EntryE lastReturned header;// 下一个节点private EntryE next;// 下一个节点对应的索引值private int nextIndex;// 期望的改变计数。用来实现fail-fast机制。private int expectedModCount modCount;// 构造函数。// 从index位置开始进行迭代ListItr(int index) {// index的有效性处理if (index 0 || index size)throw new IndexOutOfBoundsException(Index: index , Size: size);// 若 “index 小于 ‘双向链表长度的一半’”则从第一个元素开始往后查找// 否则从最后一个元素往前查找。if (index (size 1)) {next header.next;for (nextIndex0; nextIndexindex; nextIndex)next next.next;} else {next header;for (nextIndexsize; nextIndexindex; nextIndex--)next next.previous;}}// 是否存在下一个元素public boolean hasNext() {// 通过元素索引是否等于“双向链表大小”来判断是否达到最后。return nextIndex ! size;}// 获取下一个元素public E next() {checkForComodification();if (nextIndex size)throw new NoSuchElementException();lastReturned next;// next指向链表的下一个元素next next.next;nextIndex;return lastReturned.element;}// 是否存在上一个元素public boolean hasPrevious() {// 通过元素索引是否等于0来判断是否达到开头。return nextIndex ! 0;}// 获取上一个元素public E previous() {if (nextIndex 0)throw new NoSuchElementException();// next指向链表的上一个元素lastReturned next next.previous;nextIndex--;checkForComodification();return lastReturned.element;}// 获取下一个元素的索引public int nextIndex() {return nextIndex;}// 获取上一个元素的索引public int previousIndex() {return nextIndex-1;}// 删除当前元素。// 删除双向链表中的当前节点public void remove() {checkForComodification();EntryE lastNext lastReturned.next;try {LinkedList.this.remove(lastReturned);} catch (NoSuchElementException e) {throw new IllegalStateException();}if (nextlastReturned)next lastNext;elsenextIndex--;lastReturned header;expectedModCount;}// 设置当前节点为epublic void set(E e) {if (lastReturned header)throw new IllegalStateException();checkForComodification();lastReturned.element e;}// 将e添加到当前节点的前面public void add(E e) {checkForComodification();lastReturned header;addBefore(e, next);nextIndex;expectedModCount;}// 判断 “modCount和expectedModCount是否相等”依次来实现fail-fast机制。final void checkForComodification() {if (modCount ! expectedModCount)throw new ConcurrentModificationException();}}// 双向链表的节点所对应的数据结构。// 包含3部分上一节点下一节点当前节点值。private static class EntryE {// 当前节点所包含的值E element;// 下一个节点EntryE next;// 上一个节点EntryE previous;/*** 链表节点的构造函数。* 参数说明* element —— 节点所包含的数据* next —— 下一个节点* previous —— 上一个节点*/Entry(E element, EntryE next, EntryE previous) {this.element element;this.next next;this.previous previous;}}// 将节点(节点数据是e)添加到entry节点之前。private EntryE addBefore(E e, EntryE entry) {// 新建节点newEntry将newEntry插入到节点e之前并且设置newEntry的数据是eEntryE newEntry new EntryE(e, entry, entry.previous);newEntry.previous.next newEntry;newEntry.next.previous newEntry;// 修改LinkedList大小size;// 修改LinkedList的修改统计数用来实现fail-fast机制。modCount;return newEntry;}// 将节点从链表中删除private E remove(EntryE e) {if (e header)throw new NoSuchElementException();E result e.element;e.previous.next e.next;e.next.previous e.previous;e.next e.previous null;e.element null;size--;modCount;return result;}// 反向迭代器public IteratorE descendingIterator() {return new DescendingIterator();}// 反向迭代器实现类。private class DescendingIterator implements Iterator {final ListItr itr new ListItr(size());// 反向迭代器是否下一个元素。// 实际上是判断双向链表的当前节点是否达到开头public boolean hasNext() {return itr.hasPrevious();}// 反向迭代器获取下一个元素。// 实际上是获取双向链表的前一个节点public E next() {return itr.previous();}// 删除当前节点public void remove() {itr.remove();}}// 返回LinkedList的Object[]数组public Object[] toArray() {// 新建Object[]数组Object[] result new Object[size];int i 0;// 将链表中所有节点的数据都添加到Object[]数组中for (EntryE e header.next; e ! header; e e.next)result[i] e.element;return result;}// 返回LinkedList的模板数组。所谓模板数组即可以将T设为任意的数据类型public T T[] toArray(T[] a) {// 若数组a的大小 LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素)// 则新建一个T[]数组T[]的大小为LinkedList大小并将该T[]赋值给a。if (a.length size)a (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);// 将链表中所有节点的数据都添加到数组a中int i 0;Object[] result a;for (EntryE e header.next; e ! header; e e.next)result[i] e.element;if (a.length size)a[size] null;return a;}// 克隆函数。返回LinkedList的克隆对象。public Object clone() {LinkedListE clone null;// 克隆一个LinkedList克隆对象try {clone (LinkedListE) super.clone();} catch (CloneNotSupportedException e) {throw new InternalError();}// 新建LinkedList表头节点clone.header new EntryE(null, null, null);clone.header.next clone.header.previous clone.header;clone.size 0;clone.modCount 0;// 将链表中所有节点的数据都添加到克隆对象中for (EntryE e header.next; e ! header; e e.next)clone.add(e.element);return clone;}// java.io.Serializable的写入函数// 将LinkedList的“容量所有的元素值”都写入到输出流中private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {// Write out any hidden serialization magics.defaultWriteObject();// 写入“容量”s.writeInt(size);// 将链表中所有节点的数据都写入到输出流中for (Entry e header.next; e ! header; e e.next)s.writeObject(e.element);}// java.io.Serializable的读取函数根据写入方式反向读出// 先将LinkedList的“容量”读出然后将“所有的元素值”读出private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {// Read in any hidden serialization magics.defaultReadObject();// 从输入流中读取“容量”int size s.readInt();// 新建链表表头节点header new EntryE(null, null, null);header.next header.previous header;// 从输入流中将“所有的元素值”并逐个添加到链表中for (int i0; isize; i)addBefore((E)s.readObject(), header);}}总结(01)LinkedList实际上是通过双向链表去实现的。 它包含一个非常重要的内部类Entry。Entry是双向链表节点所对应的数据结构它包括的属性有当前节点所包含的值上一个节点下一个节点。(02) 从LinkedList的实现方式中可以发现它不存在LinkedList容量不足的问题。(03)LinkedList的克隆函数即是将全部元素克隆到一个新的LinkedList对象中。(04)LinkedList实现java.io.Serializable。当写入到输出流时先写入“容量”再依次写入“每一个节点保护的值”当读出输入流时先读取“容量”再依次读取“每一个元素”。(05) 由于LinkedList实现了Deque而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式一种形式在操作失败时抛出异常另一种形式返回一个特殊值null 或 false具体取决于操作总结起来如下表格第一个元素头部 最后一个元素尾部 抛出异常 特殊值 抛出异常 特殊值插入 addFirst(e) offerFirst(e) addLast(e) offerLast(e)移除 removeFirst() pollFirst() removeLast() pollLast()检查 getFirst() peekFirst() getLast() peekLast()(06) LinkedList可以作为FIFO(先进先出)的队列作为FIFO的队列时下表的方法等价队列方法 等效方法add(e) addLast(e)offer(e) offerLast(e)remove() removeFirst()poll() pollFirst()element() getFirst()peek() peekFirst()(07) LinkedList可以作为LIFO(后进先出)的栈作为LIFO的栈时下表的方法等价栈方法 等效方法 push(e) addFirst(e) pop() removeFirst() peek() peekFirst()LinkedList遍历方式LinkedList支持多种遍历方式。建议不要采用随机访问的方式去遍历LinkedList而采用逐个遍历的方式。for(Iterator iter list.iterator(); iter.hasNext();)iter.next();(02) 通过快速随机访问遍历LinkedListint size list.size();
for (int i0; isize; i) {list.get(i);
}
(03) 通过另外一种for循环来遍历LinkedListfor (Integer integ:list) ;(04) 通过pollFirst()来遍历LinkedListwhile(list.pollFirst() ! null);(05) 通过pollLast()来遍历LinkedListwhile(list.pollLast() ! null);
(06) 通过removeFirst()来遍历LinkedListtry {while(list.removeFirst() ! null);
} catch (NoSuchElementException e) {
}(07) 通过removeLast()来遍历LinkedListtry {while(list.removeLast() ! null);
} catch (NoSuchElementException e) {
}测试这些遍历方式效率的代码如下import java.util.List;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;/** desc 测试LinkedList的几种遍历方式和效率** author skywang*/
public class LinkedListThruTest {public static void main(String[] args) {// 通过Iterator遍历LinkedListiteratorLinkedListThruIterator(getLinkedList()) ;// 通过快速随机访问遍历LinkedListiteratorLinkedListThruForeach(getLinkedList()) ;// 通过for循环的变种来访问遍历LinkedListiteratorThroughFor2(getLinkedList()) ;// 通过PollFirst()遍历LinkedListiteratorThroughPollFirst(getLinkedList()) ;// 通过PollLast()遍历LinkedListiteratorThroughPollLast(getLinkedList()) ;// 通过removeFirst()遍历LinkedListiteratorThroughRemoveFirst(getLinkedList()) ;// 通过removeLast()遍历LinkedListiteratorThroughRemoveLast(getLinkedList()) ;}private static LinkedList getLinkedList() {LinkedList llist new LinkedList();for (int i0; i100000; i)llist.addLast(i);return llist;}/*** 通过快迭代器遍历LinkedList*/private static void iteratorLinkedListThruIterator(LinkedListInteger list) {if (list null)return ;// 记录开始时间long start System.currentTimeMillis();for(Iterator iter list.iterator(); iter.hasNext();)iter.next();// 记录结束时间long end System.currentTimeMillis();long interval end - start;System.out.println(iteratorLinkedListThruIterator interval ms);}/*** 通过快速随机访问遍历LinkedList*/private static void iteratorLinkedListThruForeach(LinkedListInteger list) {if (list null)return ;// 记录开始时间long start System.currentTimeMillis();int size list.size();for (int i0; isize; i) {list.get(i);}// 记录结束时间long end System.currentTimeMillis();long interval end - start;System.out.println(iteratorLinkedListThruForeach interval ms);}/*** 通过另外一种for循环来遍历LinkedList*/private static void iteratorThroughFor2(LinkedListInteger list) {if (list null)return ;// 记录开始时间long start System.currentTimeMillis();for (Integer integ:list);// 记录结束时间long end System.currentTimeMillis();long interval end - start;System.out.println(iteratorThroughFor2 interval ms);}/*** 通过pollFirst()来遍历LinkedList*/private static void iteratorThroughPollFirst(LinkedListInteger list) {if (list null)return ;// 记录开始时间long start System.currentTimeMillis();while(list.pollFirst() ! null);// 记录结束时间long end System.currentTimeMillis();long interval end - start;System.out.println(iteratorThroughPollFirst interval ms);}/*** 通过pollLast()来遍历LinkedList*/private static void iteratorThroughPollLast(LinkedListInteger list) {if (list null)return ;// 记录开始时间long start System.currentTimeMillis();while(list.pollLast() ! null);// 记录结束时间long end System.currentTimeMillis();long interval end - start;System.out.println(iteratorThroughPollLast interval ms);}/*** 通过removeFirst()来遍历LinkedList*/private static void iteratorThroughRemoveFirst(LinkedListInteger list) {if (list null)return ;// 记录开始时间long start System.currentTimeMillis();try {while(list.removeFirst() ! null);} catch (NoSuchElementException e) {}// 记录结束时间long end System.currentTimeMillis();long interval end - start;System.out.println(iteratorThroughRemoveFirst interval ms);}/*** 通过removeLast()来遍历LinkedList*/private static void iteratorThroughRemoveLast(LinkedListInteger list) {if (list null)return ;// 记录开始时间long start System.currentTimeMillis();try {while(list.removeLast() ! null);} catch (NoSuchElementException e) {}// 记录结束时间long end System.currentTimeMillis();long interval end - start;System.out.println(iteratorThroughRemoveLast interval ms);}}
iteratorLinkedListThruIterator8 ms
iteratorLinkedListThruForeach3724 ms
iteratorThroughFor25 ms
iteratorThroughPollFirst8 ms
iteratorThroughPollLast6 ms
iteratorThroughRemoveFirst2 ms
iteratorThroughRemoveLast2 ms由此可见遍历LinkedList时使用removeFist()或removeLast()效率最高。但用它们遍历时会删除原始数据若单纯只读取而不删除应该使用第3种遍历方式。无论如何千万不要通过随机访问去遍历LinkedList
