本文共 20222 字,大约阅读时间需要 67 分钟。
双链表实现了List和Deque接口。 实现所有可选列表操作,并允许所有元素(包括null )。
所有的操作都能像双向列表一样预期。 索引到列表中的操作将从开始或结束遍历列表,以更接近指定的索引为准。
请注意,此实现不同步。 如果多个线程同时访问链接列表,并且至少有一个线程在结构上修改列表,则必须在外部进行同步。 (结构修改是添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。)
这通常通过在自然封装列表的对象上进行同步来实现。 如果没有这样的对象存在,列表应该使用 Collections.synchronizedList 方法“包装”。 这最好在创建时完成,以防止意外的不同步访问列表:List list = Collections.synchronizedList(new LinkedList(...));
这个类的 iterator 和 listIterator 方法返回的迭代器是故障快速的 :如果列表在迭代器创建之后的任何时间被结构化地修改,除了通过迭代器自己的remove或add方法之外,
迭代器将会抛出一个ConcurrentModificationException 。 因此,面对并发修改,迭代器将快速而干净地失败,而不是在未来未确定的时间冒着任意的非确定性行为。请注意,迭代器的故障快速行为无法保证,因为一般来说,在不同步并发修改的情况下,无法做出任何硬性保证。
失败快速迭代器尽力投入ConcurrentModificationException 。 因此,编写依赖于此异常的程序的正确性将是错误的:迭代器的故障快速行为应仅用于检测错误。(以上来自 Java8 api)
首先看一下 LinkedList 的继承关系:
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable{ }
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable{ transient int size = 0;// list中的元素个数 /** * 链表头节点 * 不变式: (first == null && last == null) || (first.prev == null && first.item != null) */ transient Node first; /** * 链表尾节点 * 不变式: (first == null && last == null) || (last.next == null && last.item != null) */ transient Node last; private static class Node { E item;// 实际存放的元素 Node next;// 后一个节点 Node prev;// 前一个节点 // 构造函数元素顺序分别为前,自己,后。就像排队一样 Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } } }
由于采用的是链表结构,所以不像 ArrayList 一样,有指定容量的构造方法
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable{ /** * 构造一个空列表. */ public LinkedList() { } /** * 构造一个包含指定 collection 中的元素的列表,这些元素按其 collection 的迭代器返回的顺序排列 */ public LinkedList(Collection c) { this();// 什么都不做 addAll(c);// 将 c 集合里的元素添加进链表 } /** * 按照指定集合的迭代器返回的顺序将指定集合中的所有元素追加到此列表的末尾。 */ public boolean addAll(Collection c) { return addAll(size, c); } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * 判断参数是迭代器或添加操作的有效位置的索引。 */ private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } /** * 从指定位置开始,将指定集合中的所有元素插入此列表。 * 将当前位置的元素(如果有)和任何后续元素向右移动(增加其索引)。 * 新元素将按照指定集合的迭代器返回的顺序出现在列表中。 */ public boolean addAll(int index, Collection c) { checkPositionIndex(index);// 检查索引是否正确,即在 0 <= index <= size Object[] a = c.toArray();// 将 collection 转为数组 int numNew = a.length; if (numNew == 0) return false; Node pred, succ;// 声明 pred 为"当前要插入节点的前一个节点",succ 为"当前要插入节点的后一个节点" if (index == size) { // 说明要插入元素的位置就在链表的末尾,后置元素为null,前一个元素就是last succ = null; pred = last; } else { // 说明在链表的中间插入,这时 pred 为原来 index 的 prev,succ 为原来的元素 succ = node(index);// 利用双向链表的特性,进行更快的遍历 pred = succ.prev; } for (Object o : a) { // 遍历数组,逐个添加 @SuppressWarnings("unchecked") E e = (E) o; Node newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode;// 将新节点作为pred,为下一个元素插入做准备 } if (succ == null) { // 如果后继元素为空,那么插入完后的最后一个元素,就 pred 就是 last last = pred; } else { // 否则就维护最后一个元素和之前的元素之间的关系 pred.next = succ; succ.prev = pred; } size += numNew; modCount++;// 链表结构发生改动 return true; } /** * 返回指定元素索引处的(非空)节点 * 利用双向链表的特性,进行更快的遍历 * 双向链表和索引值联系起来:通过一个计数索引值来实现 * 当我们调用get(int index)时,首先会比较“index”和“双向链表长度的1/2”; * 若前者大,则从链表头开始往后查找,直到 index 位置; * 否则,从链表末尾开始先前查找,直到 index 位置. */ Node node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { // 如果index在链表的前半部分,则从头部节点开始遍历 Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // 如果index在链表的后半部分,则从尾部节点开始遍历 Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }}
作为链表,添加新元素就是在链表的末尾插入新元素。
注意,如果末尾元素是 null ,又该如何处理?
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable{ /** * 将指定的元素追加到此列表的末尾。 */ public boolean add(E e) { linkLast(e); return true; } /** * 链接 e 作为最后一个元素。 */ void linkLast(E e) { final Node l = last;// 记录last节点 final Node newNode = new Node<>(l, e, null);// 初始化新的节点 last = newNode; if (l == null)// 末尾元素是 null,是个空列表 first = newNode; else l.next = newNode; size++; modCount++;// 链表结构发生改动 }}
LinkedList 还有其他的增加方法:
处理思路:
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable{ public boolean remove(Object o) { if (o == null) { // 是否为 null 的判断 // 从头节点遍历链表寻找第一个 x(null) 元素 for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x);// 取消链接 x(null) 元素,重新维护删除元素后的前后关系 return true; } } } else { // 与上面的逻辑相同 for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /** * Unlinks non-null node x. */ E unlink(Node x) { // assert x != null; final E element = x.item; // 局部保存被删除节点的前后节点 final Node next = x.next; final Node prev = x.prev; if (prev == null) { // prev 为 null 说明 x 节点为 first 节点,则删除后,next 为 first first = next; } else { // 否则 prev的下一个元素为x的next prev.next = next; x.prev = null;// 设为 null,方便GC } if (next == null) { // next 为null说明x节点为 last 节点,则删除后,next 为 prev last = prev; } else { // 否则 next 的上一个元素为x的prev next.prev = prev; x.next = null;// 设为 null,方便GC } x.item = null;// 设为 null,方便GC size--; modCount++;// 链表结构发生改变 return element;//返回被删除节点的数据体 }}
其他的移除方法:
查询的方法非常简单,
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable{ public E get(int index) { checkElementIndex(index);// 检查索引index 是否在 [0,size] 区间内 return node(index).item;//利用双向链表的特性,进行更快的遍历 }}
其它的查询方法:
关于集合的快速失败机制的详细了解可以
iterator() 调用的其实是 listIterator() 方法,对于不同的实现类,都会实现不同的方法,但是其原理是一致的,
都是为了防止多线程操作同一个集合而出现的问题public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable{ public ListIterator listIterator(int index) { checkPositionIndex(index);// 检查索引的正确性[0, size] return new ListItr(index); } private class ListItr implements ListIterator { private Node lastReturned;// 记录上次返回的元素 private Node next;// 记录下一个元素 private int nextIndex; private int expectedModCount = modCount;// 用来判断迭代过程中,是否有对元素的改动(fail-fast) ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index);//初始化next,以便在next方法中返回 nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification();// 判断是否有对元素的改动,有则抛出异常 if (!hasNext()) throw new NoSuchElementException(); lastReturned = next;// next()当中的next元素就是要返回的结果 next = next.next; nextIndex++; return lastReturned.item; } // 省略其它代码。。。 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }}
LinkedList 作为 FIFO(先进先出) 的队列, 下表的方法等效:
队列方法 | 等效方法 |
---|---|
add(e) | addLast(e) |
offer(e) | offerLast(e) |
remove() | removeFirst() |
poll() | pollFirst() |
element() | getFirst() |
peek() | peekFirst() |
LinkedList 作为 LIFO(后进先出) 的栈, 下表的方法等效:
栈方法 | 等效方法 |
---|---|
push(e) | addFirst(e) |
pop() | removeFirst() |
peek() | peekFirst() |
LinkedList 支持多种遍历方式。建议不要采用随机访问的方式去遍历LinkedList,而采用逐个遍历的方式。
迭代器遍历
for(Iterator iter = list.iterator(); iter.hasNext();) iter.next();
快速随机访问
int size = list.size();for (int i=0; i
foreach
for (Integer integ:list) ;
通过 pollFirst() 来遍历 LinkedList
while(list.pollFirst() != null) ;
通过pollLast()来遍历LinkedList
while(list.pollLast() != null) ;
通过removeFirst()来遍历LinkedList
try { while(list.removeFirst() != null) ;} catch (NoSuchElementException e) { }
通过removeLast()来遍历LinkedList
try { while(list.removeLast() != null) ;} catch (NoSuchElementException e) { }
测试以上7种循环方式的效率的代码:
package com.littlefxc.examples.base.collections;import java.util.Iterator;import java.util.LinkedList;import java.util.NoSuchElementException;/** * 测试LinkedList的几种遍历方式和效率 * * @author fengxuechao */public class LinkedListThruTest { public static void main(String[] args) { // 通过Iterator遍历LinkedList iterator(getLinkedList()); // 通过快速随机访问遍历LinkedList randomAccess(getLinkedList()); // 通过for循环的变种来访问遍历LinkedList foreach(getLinkedList()); // 通过PollFirst()遍历LinkedList while_pollFirst(getLinkedList()); // 通过PollLast()遍历LinkedList while_pollLast(getLinkedList()); // 通过removeFirst()遍历LinkedList while_removeFirst(getLinkedList()); // 通过removeLast()遍历LinkedList while_removeLast(getLinkedList()); } private static LinkedList getLinkedList() { LinkedList llist = new LinkedList(); for (int i = 0; i < 100000; i++) llist.addLast(i); return llist; } /** * 通过快迭代器遍历LinkedList */ private static void iterator(LinkedListlist) { 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("通过Iterator遍历LinkedList:" + interval + " ms"); } /** * 通过快速随机访问遍历LinkedList */ private static void randomAccess(LinkedList list) { if (list == null) return; // 记录开始时间 long start = System.currentTimeMillis(); int size = list.size(); for (int i = 0; i < size; i++) { list.get(i); } // 记录结束时间 long end = System.currentTimeMillis(); long interval = end - start; System.out.println("通过快速随机访问遍历LinkedList:" + interval + " ms"); } /** * 通过另外一种for循环来遍历LinkedList */ private static void foreach(LinkedList list) { if (list == null) return; // 记录开始时间 long start = System.currentTimeMillis(); for (Integer integ : list) ; // 记录结束时间 long end = System.currentTimeMillis(); long interval = end - start; System.out.println("通过for循环的变种来访问遍历LinkedList:" + interval + " ms"); } /** * 通过pollFirst()来遍历LinkedList */ private static void while_pollFirst(LinkedList list) { if (list == null) return; // 记录开始时间 long start = System.currentTimeMillis(); while (list.pollFirst() != null) ; // 记录结束时间 long end = System.currentTimeMillis(); long interval = end - start; System.out.println("通过PollFirst()遍历LinkedList:" + interval + " ms"); } /** * 通过pollLast()来遍历LinkedList */ private static void while_pollLast(LinkedList list) { if (list == null) return; // 记录开始时间 long start = System.currentTimeMillis(); while (list.pollLast() != null) ; // 记录结束时间 long end = System.currentTimeMillis(); long interval = end - start; System.out.println("通过PollLast()遍历LinkedList:" + interval + " ms"); } /** * 通过removeFirst()来遍历LinkedList */ private static void while_removeFirst(LinkedList 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("通过removeFirst()遍历LinkedList:" + interval + " ms"); } /** * 通过removeLast()来遍历LinkedList */ private static void while_removeLast(LinkedList 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("通过removeLast()遍历LinkedList:" + interval + " ms"); }}
运行结果:
通过Iterator遍历LinkedList:4 ms通过快速随机访问遍历LinkedList:3606 ms通过for循环的变种来访问遍历LinkedList:4 ms通过PollFirst()遍历LinkedList:4 ms通过PollLast()遍历LinkedList:3 ms通过removeFirst()遍历LinkedList:3 ms通过removeLast()遍历LinkedList:4 ms
由此可见,遍历LinkedList时,千万不要通过随机访问去遍历LinkedList!
package com.littlefxc.examples.base.collections;import java.util.LinkedList;/** * @author fengxuechao * @date 2019-05-22 */public class LinkedListTest { public static void main(String[] args) { // 测试LinkedList的API testLinkedListAPIs() ; // 将LinkedList当作 LIFO(后进先出)的堆栈 useLinkedListAsLIFO(); // 将LinkedList当作 FIFO(先进先出)的队列 useLinkedListAsFIFO(); } /* * 测试LinkedList中部分API */ private static void testLinkedListAPIs() { String val = null; //LinkedList llist; //llist.offer("10"); // 新建一个LinkedList LinkedList llist = new LinkedList(); //---- 添加操作 ---- // 依次添加1,2,3 llist.add("1"); llist.add("2"); llist.add("3"); // 将“4”添加到第一个位置 llist.add(1, "4"); System.out.println("\nTest \"addFirst(), removeFirst(), getFirst()\""); // (01) 将“10”添加到第一个位置。 失败的话,抛出异常! llist.addFirst("10"); System.out.println("llist:"+llist); // (02) 将第一个元素删除。 失败的话,抛出异常! System.out.println("llist.removeFirst():"+llist.removeFirst()); System.out.println("llist:"+llist); // (03) 获取第一个元素。 失败的话,抛出异常! System.out.println("llist.getFirst():"+llist.getFirst()); System.out.println("\nTest \"offerFirst(), pollFirst(), peekFirst()\""); // (01) 将“10”添加到第一个位置。 返回true。 llist.offerFirst("10"); System.out.println("llist:"+llist); // (02) 将第一个元素删除。 失败的话,返回null。 System.out.println("llist.pollFirst():"+llist.pollFirst()); System.out.println("llist:"+llist); // (03) 获取第一个元素。 失败的话,返回null。 System.out.println("llist.peekFirst():"+llist.peekFirst()); System.out.println("\nTest \"addLast(), removeLast(), getLast()\""); // (01) 将“20”添加到最后一个位置。 失败的话,抛出异常! llist.addLast("20"); System.out.println("llist:"+llist); // (02) 将最后一个元素删除。 失败的话,抛出异常! System.out.println("llist.removeLast():"+llist.removeLast()); System.out.println("llist:"+llist); // (03) 获取最后一个元素。 失败的话,抛出异常! System.out.println("llist.getLast():"+llist.getLast()); System.out.println("\nTest \"offerLast(), pollLast(), peekLast()\""); // (01) 将“20”添加到第一个位置。 返回true。 llist.offerLast("20"); System.out.println("llist:"+llist); // (02) 将第一个元素删除。 失败的话,返回null。 System.out.println("llist.pollLast():"+llist.pollLast()); System.out.println("llist:"+llist); // (03) 获取第一个元素。 失败的话,返回null。 System.out.println("llist.peekLast():"+llist.peekLast()); // 将第3个元素设置300。不建议在LinkedList中使用此操作,因为效率低! llist.set(2, "300"); // 获取第3个元素。不建议在LinkedList中使用此操作,因为效率低! System.out.println("\nget(3):"+llist.get(2)); // ---- toArray(T[] a) ---- // 将LinkedList转行为数组 String[] arr = (String[])llist.toArray(new String[0]); for (String str:arr) System.out.println("str:"+str); // 输出大小 System.out.println("size:"+llist.size()); // 清空LinkedList llist.clear(); // 判断LinkedList是否为空 System.out.println("isEmpty():"+llist.isEmpty()+"\n"); } /** * 将LinkedList当作 LIFO(后进先出)的堆栈 */ private static void useLinkedListAsLIFO() { System.out.println("--BEGIN--堆栈测试"); System.out.println("\nuseLinkedListAsLIFO"); // 新建一个LinkedList LinkedList stack = new LinkedList(); // 将1,2,3,4添加到堆栈中 stack.push("1"); stack.push("2"); stack.push("3"); stack.push("4"); // 打印“栈” System.out.println("stack:"+stack); // 删除“栈顶元素” System.out.println("stack.pop():"+stack.pop()); // 取出“栈顶元素” System.out.println("stack.peek():"+stack.peek()); // 打印“栈” System.out.println("stack:"+stack); System.out.println("--END--堆栈测试"); } /** * 将LinkedList当作 FIFO(先进先出)的队列 */ private static void useLinkedListAsFIFO() { System.out.println("--BEGIN--队列测试"); System.out.println("\nuseLinkedListAsFIFO"); // 新建一个LinkedList LinkedList queue = new LinkedList(); // 将10,20,30,40添加到队列。每次都是插入到末尾 queue.add("10"); queue.add("20"); queue.add("30"); queue.add("40"); // 打印“队列” System.out.println("queue:"+queue); // 删除(队列的第一个元素) System.out.println("queue.remove():"+queue.remove()); // 读取(队列的第一个元素) System.out.println("queue.element():"+queue.element()); // 打印“队列” System.out.println("queue:"+queue); System.out.println("--END--队列测试"); }}
Node
。Node
是双向链表节点所对应的数据结构, 它包括的属性有:当前节点所包含的值,上一个节点,下一个节点。转载地址:http://ltxzb.baihongyu.com/