Jdk1.6 Collections Framework源码解析(2)ITeye - 乐橙lc8

Jdk1.6 Collections Framework源码解析(2)ITeye

2019年02月23日10时19分17秒 | 作者: 鸿畴 | 标签: 元素,链表,节点 | 浏览: 1307

  ArrayList的刺进和删去元素的操作会花费线性时刻,那么有没有刺进和删去元素比较省时的调集呢,看下LinkedList这个完结。
  老样子,先看看它完结了那些接口。
public class LinkedList E 
 extends AbstractSequentialList E 
 implements List E , Deque E , Cloneable, java.io.Serializable

  之前看过的接口不看了。先看下java.util.Deque。
public interface Deque E extends Queue E 

  这个接口扩展了java.util.Queue,Queue也是Java Collections Framework中一个重要的接口,它表明了行列。当然行列自身也归于调集(java.util.Collection是更高层次的笼统)。
public interface Queue E extends Collection E {
 boolean add(E e);
 boolean offer(E e);
 E remove();
 E poll();
 E element();
 E peek();

  Queue供给了增加、删去和获取元素的办法,每种办法供给2个版别。如增加元素,add和offer都能够完结这个操作,差异在于add办法假如增加失利会抛出反常,而offer办法则会回来false。Queue接口只供给行列的笼统概念,但并没有界说元素的操作次第。其完结能够供给先入先出或许先入后出(栈)这样的性质。

  大约了解了java.util.Queue后持续看java.util.Deque。已然Deque扩展了Queue,那它本质上也是行列喽。本来Deque是“double ended queue”的缩写,也就是双端行列的意思,单词读音为“deck”(蛋壳儿。。。)。 so,这个接口界说了在行列两头操作(增加、删去和获取)元素的办法。
public interface Deque E extends Queue E {
 void addFirst(E e);
 void addLast(E e);
 boolean offerFirst(E e);
 boolean offerLast(E e);
 E removeFirst();
 E removeLast();
 E pollFirst();
 E pollLast();
 E getFirst();
 E getLast();
 E peekFirst();
 E peekLast();
 boolean removeFirstOccurrence(Object o);
 boolean removeLastOccurrence(Object o);
 void push(E e);
 E pop();
 Iterator E descendingIterator();

  像Queue接口相同,Deque也对这些操作办法供给了2个版别。

  接下来看一下java.util.AbstractSequentialList这个笼统类,这个类的效果和java.util.AbstractList效果相同,供给一些“骨架”完结。差异在于这个类供给了“按次第拜访”的根底,而AbstractList供给了“自在拜访”的根底。也就是说,假如咱们要完结一个根据链表的调集的话,能够承继这个类;要完结根据数组的调集的话,就承继AbstractList类。

  好了,在看LinkedList的源代码之前,仍是先考虑一下,假如自己完结LinkedList要怎样做。已然是链表,那么内部必定会有一个“链”,而“链”是由“环”组成,阐明内部会有“环”这样的概念。每个环都和下一个环相扣,有两个特别的环,首环和尾环。首要,没有恣意一环的下一环是首环,尾环没有下一环;然后,首环和尾环上是不带着数据的(当然一般环也是能够保存null元素滴)。假如再从代码上考虑一下,每一个环都有下一个环的引证,这样能够构成一个链。但每个环也能够即有上一个环的引证,又有下一个环的引证,也能够构成链。它们有什么差异呢?其实这就是所谓的单向链表和双向链表,java.util.LinkedList内部运用双向链表完结。那能够运用单向链表完结吗?那就试试吧。
  首要要有头节点和尾节点,想象一下,假如没有它们,咱们要保存的数据该放哪。。。然后仍是要有一个size的私有变量,这样一些办法就好完结了。
 * 单向链表完结的LinkedList
 * 每个节点含有本节点元素及指向下一个节点的链,
 * 最终一个节点的next链为空。
 * @author BrokenDreams
public class LinkedList E 
 extends AbstractSequentialList E 
 implements List E ,Deque E {
 //头节点
 private Entry E header = new Entry E (null, null);
 //尾节点
 private Entry E tail = new Entry E (null, null);
 private transient int size = 0;
 public LinkedList() {
 header.next = tail;
 public LinkedList(Collection ? extends E c){
 this();
 addAll(c);

  “环”的完结很简单。是一个内部类。
private static class Entry E {
 E element;
 Entry E next;
 public Entry(E element, Entry E next) {
 super();
 this.element = element;
 this.next = next;

  之前在总结ArrayList的时分,看到了当在调集尾部刺进元素时,操作时刻为常数时刻(假定没有进行数组扩展);但当往调集首部刺进元素时,内部数组中所有的元素都得往后移动一个方位(内部进行数组的复制),这样会花费O(n)的时刻。咱们看下单向链表完结里的状况。
 @Override
 public boolean add(E e) {
 if(size  0){
 addAfter(e, header);
 return true;
 Entry E node = header.next;
 while(node != null){
 if(node.next  tail){
 addAfter(e, node);
 return true;
 node = node.next;
 //never here
 return false;
 private Entry E addAfter(E e, Entry E entry){
 Entry E newEntry = new Entry E (e, null);
 Entry E nextEntry = entry.next;
 entry.next = newEntry;
 newEntry.next = nextEntry;
 size++;
 modCount++;
 return newEntry;
 @Override
 public void addFirst(E e) {
 addAfter(e, header);

  能够看到,当在调集首部刺进元素时,操作时刻为常数时刻;但当在调集尾部刺进元素时,由于咱们拜访内部数据的进口只要内部的header和tail,又由于是单向链,咱们要在调集尾部刺进元素时,需求改动tail前一个元素的next,而要找到tail的前一个元素,需求从header开端往下找,所以操作时刻仍是O(n),看来单向链表仍是不能到达咱们的意图。。。

  好啦,仍是看看LinkedList怎样玩儿的吧。
public class LinkedList E 
 extends AbstractSequentialList E 
 implements List E , Deque E , Cloneable, java.io.Serializable
 private transient Entry E header = new Entry E (null, null, null);
 private transient int size = 0;
 * Constructs an empty list.
 public LinkedList() {
 header.next = header.previous = header;

private static class Entry E {
 E element;
 Entry E next;
 Entry E previous;
 Entry(E element, Entry E next, Entry E previous) {
 this.element = element;
 this.next = next;
 this.previous = previous;

  在LinkedList中,只要一个首节点。当调集为空时,首节点的上一个节点和下一个节点都指向自己。能够想到,Linked内部的双向链表是一个环状结构,header作为起点和结尾。
看一下LinkedList的增加元素办法:
 * Inserts the specified element at the beginning of this list.
 * @param e the element to add
 public void addFirst(E e) {
 addBefore(e, header.next);
 * Appends the specified element to the end of this list.
 * p This method is equivalent to {@link #add}.
 * @param e the element to add
 public void addLast(E e) {
 addBefore(e, header);
 * Appends the specified element to the end of this list.
 * p This method is equivalent to {@link #addLast}.
 * @param e element to be appended to this list
 * @return tt true /tt (as specified by {@link Collection#add})
 public boolean add(E e) {
 addBefore(e, header);
 return true;
 private Entry E addBefore(E e, Entry E entry) {
 Entry E newEntry = new Entry E (e, entry, entry.previous);
 newEntry.previous.next = newEntry;
 newEntry.next.previous = newEntry;
 size++;
 modCount++;
 return newEntry;

  再看看删去办法:
 * 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();
 * Removes and returns the first element from this list.
 * @return the first element from this list
 * @throws NoSuchElementException if this list is empty
 public E removeFirst() {
 return remove(header.next);
 * Removes and returns the last element from this list.
 * @return the last element from this list
 * @throws NoSuchElementException if this list is empty
 public E removeLast() {
 return remove(header.previous);
 private E remove(Entry E 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;

  可见在LinkedList首部和尾部增加和删去元素,操作时刻都为常数时刻。而在LinkedList中拜访元素呢。
 * Returns the element at the specified position in this list.
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 public E get(int index) {
 return entry(index).element;
 * Removes the element at the specified position in this list. Shifts any
 * subsequent elements to the left (subtracts one from their indices).
 * Returns the element that was removed from the list.
 * @param index the index of the element to be removed
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 public E remove(int index) {
 return remove(entry(index));
 * Returns the indexed entry.
 private Entry E entry(int index) {
 if (index 0 || index = size)
 throw new IndexOutOfBoundsException("Index: "+index+
 ", Size: "+size);
 Entry E e = header;
 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;

  虽然做了一些优化,但当要拜访元素越接近链表中心方位时,要花费的时刻越长。所以在LinkedList中,根据方位(Index)的操作都是低效的。
  OK,小总结一下。LinkedList内部选用双向链表完结,在表的两头进行刺进和删去操作花费常数时刻;根据方位的操作时低效的,当然查找元素也是低效的。
版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表乐橙lc8立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章