- 浏览: 249231 次
- 性别:
- 来自: 北京
博客专栏
-
Java并发包源码解析
浏览量:98046
最新评论
-
746238836:
整个RingBuffer内部做了大量的缓存行填充,前后各填充了 ...
disruptor-3.3.2源码解析(2)-队列 -
xiangshouxiyang:
群加不了。。。
Jdk1.7 ForkJoin框架源码解析汇总 -
有贝无患:
acquire方法里面为什么tryAcquire会被调用多次 ...
Jdk1.6 JUC源码解析(6)-locks-AbstractQueuedSynchronizer -
zwy_qz:
library_call.cpp 里面的内联操作 inline ...
Jdk1.6 JUC源码解析(1)-atomic-AtomicXXX -
sunwang810812:
您好,正在学习您的文章,中间有一段,一直没明白:“privat ...
Jdk1.6 JUC源码解析(6)-locks-AbstractQueuedSynchronizer
ArrayList的插入和删除元素的操作会花费线性时间,那么有没有插入和删除元素比较省时的集合呢,看下LinkedList这个实现。
老样子,先看看它实现了那些接口。
之前看过的接口不看了。先看下java.util.Deque。
这个接口扩展了java.util.Queue,Queue也是Java Collections Framework中一个重要的接口,它表示了队列。当然队列本身也属于集合(java.util.Collection是更高层次的抽象)。
Queue提供了添加、删除和获取元素的方法,每种方法提供2个版本。如添加元素,add和offer都可以完成这个操作,区别在于add方法如果添加失败会抛出异常,而offer方法则会返回false。Queue接口只提供队列的抽象概念,但并没有定义元素的操作顺序。其实现可以提供先入先出或者先入后出(栈)这样的性质。
大概了解了java.util.Queue后继续看java.util.Deque。既然Deque扩展了Queue,那它本质上也是队列喽。原来Deque是“double ended queue”的缩写,也就是双端队列的意思,单词读音为“deck”(蛋壳儿。。。)。 so,这个接口定义了在队列两端操作(添加、删除和获取)元素的方法。
像Queue接口一样,Deque也对这些操作方法提供了2个版本。
接下来看一下java.util.AbstractSequentialList这个抽象类,这个类的作用和java.util.AbstractList作用一样,提供一些“骨架”实现。区别在于这个类提供了“按次序访问”的基础,而AbstractList提供了“自由访问”的基础。也就是说,如果我们要实现一个基于链表的集合的话,可以继承这个类;要实现基于数组的集合的话,就继承AbstractList类。
好了,在看LinkedList的源代码之前,还是先思考一下,如果自己实现LinkedList要怎么做。既然是链表,那么内部一定会有一个“链”,而“链”是由“环”组成,说明内部会有“环”这样的概念。每个环都和下一个环相扣,有两个特殊的环,首环和尾环。首先,没有任意一环的下一环是首环,尾环没有下一环;然后,首环和尾环上是不携带数据的(当然普通环也是可以保存null元素滴)。如果再从代码上考虑一下,每一个环都有下一个环的引用,这样可以构成一个链。但每个环也可以即有上一个环的引用,又有下一个环的引用,也可以构成链。它们有什么区别呢?其实这就是所谓的单向链表和双向链表,java.util.LinkedList内部使用双向链表实现。那可以使用单向链表实现吗?那就试试吧。
首先要有头节点和尾节点,设想一下,如果没有它们,我们要保存的数据该放哪。。。然后还是要有一个size的私有变量,这样一些方法就好实现了。
“环”的实现很简单。是一个内部类。
之前在总结ArrayList的时候,看到了当在集合尾部插入元素时,操作时间为常数时间(假设没有进行数组扩展);但当往集合首部插入元素时,内部数组中所有的元素都得往后移动一个位置(内部进行数组的拷贝),这样会花费O(n)的时间。我们看下单向链表实现里的情况。
可以看到,当在集合首部插入元素时,操作时间为常数时间;但当在集合尾部插入元素时,由于我们访问内部数据的入口只有内部的header和tail,又因为是单向链,我们要在集合尾部插入元素时,需要改变tail前一个元素的next,而要找到tail的前一个元素,需要从header开始往下找,所以操作时间还是O(n),看来单向链表还是不能达到我们的目的。。。
好啦,还是看看LinkedList怎么玩儿的吧。
在LinkedList中,只有一个首节点。当集合为空时,首节点的上一个节点和下一个节点都指向自己。可以想到,Linked内部的双向链表是一个环状结构,header作为起点和终点。
看一下LinkedList的添加元素方法:
再看看删除方法:
可见在LinkedList首部和尾部添加和删除元素,操作时间都为常数时间。而在LinkedList中访问元素呢。
尽管做了一些优化,但当要访问元素越靠近链表中间位置时,要花费的时间越长。所以在LinkedList中,基于位置(Index)的操作都是低效的。
OK,小总结一下。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内部采用双向链表实现,在表的两端进行插入和删除操作花费常数时间;基于位置的操作时低效的,当然查找元素也是低效的。
- 单向链表实现的List.zip (1.9 KB)
- 下载次数: 3
发表评论
-
Jdk1.6 Collections Framework源码解析(12)-TreeMap、TreeSet
2016-01-03 16:06 2096Jdk1.6 Collections Framework ... -
Jdk1.6 Collections Framework源码解析(11)-EnumSet
2015-12-29 18:25 1773Jdk1.6 Collections Framework源 ... -
Jdk1.6 JUC源码解析(26)-ConcurrentSkipListMap、ConcurrentSkipListSet
2015-11-03 03:08 5266Jdk1.6 JUC源码解析(26)-Concurrent ... -
Jdk1.6 JUC源码解析(25)-ConcurrentHashMap
2015-10-30 19:02 2482Jdk1.6 JUC源码解析(25)-Co ... -
Jdk1.6 集合框架源码解析汇总
2015-10-29 22:05 3385Jdk1.6 集合框架源码解析汇总 非并发: ... -
Jdk1.6 JUC源码解析(24)-ConcurrentLinkedQueue
2015-10-29 19:02 1837Jdk1.6 JUC源码解析(24)-ConcurrentL ... -
Jdk1.6 JUC源码解析(23)-CopyOnWriteArrayList、CopyOnWriteArraySet
2015-10-29 18:55 1747Jdk1.6 JUC源码解析(23)-Cop ... -
Jdk1.6 JUC源码解析(22)-LinkedBlockingDeque
2015-10-29 18:47 1540Jdk1.6 JUC源码解析(22)-LinkedBloc ... -
Jdk1.6 JUC源码解析(18)-DelayQueue
2015-10-27 19:25 2299Jdk1.6 JUC源码解析(18)-DelayQueue ... -
Jdk1.6 JUC源码解析(15)-SynchronousQueue
2015-10-26 19:19 2498Jdk1.6 JUC源码解析(15)-Synchronou ... -
Jdk1.6 JUC源码解析(14)-PriorityBlockingQueue
2015-10-25 03:22 2242Jdk1.6 JUC源码解析(14)-Pr ... -
Jdk1.6 JUC源码解析(13)-LinkedBlockingQueue
2015-10-24 22:28 1780Jdk1.6 JUC源码解析(13)-LinkedBloc ... -
Jdk1.6 JUC源码解析(12)-ArrayBlockingQueue
2015-10-23 20:03 2123Jdk1.6 JUC源码解析(12)-Ar ... -
Jdk1.6 Collections Framework源码解析(10)-EnumMap
2013-09-09 14:55 1436看这个类之前,先看一下Java的枚举——Enu ... -
Jdk1.6 Collections Framework源码解析(9)-PriorityQueue
2013-09-03 20:37 2031开发中有时会遇到这样的情况。要求某个调度器去调 ... -
Jdk1.6 Collections Framework源码解析(8)-WeakHashMap
2013-09-02 11:43 2024总结这个类之前,首先看一下Java引用的相关知 ... -
Jdk1.6 Collections Framework源码解析(7)-HashSet、LinkedHashSet
2013-08-28 11:34 1612本篇总结一 ... -
Jdk1.6 Collections Framework源码解析(6)-IdentityHashMap
2013-08-27 14:10 1557这篇总结一下java.util.Identit ... -
Jdk1.6 Collections Framework源码解析(5)-LinkedHashMap
2013-08-20 14:28 1742前面总结了java.util.HashMap, ... -
Jdk1.6 Collections Framework源码解析(4)-HashMap
2013-08-19 13:59 1936开发中常常 ...
相关推荐
aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-...
1.okhttp3.8源码使用jdk1.6重新编译,已集成了okio,在javaweb项目中使用,未在安卓项目中使用 2.okhttp3.8源码使用jdk1.6重新编译_okhttp3.8.0-jdk1.6.jar
2部分: jdk-1.6-windows-64-01 jdk-1.6-windows-64-02
JDK 1.6 64位(jdk-6u45-windows-x64(1.6 64))
java环境搭建 jdk6(包含jre)64位 jdk-6u45-windows-x64
三部分: jdk-1.6-linux-64-1 jdk-1.6-linux-64-2 jdk-1.6-linux-64-3
JDK-1.6-Windows-32位 纯官方安装版 JDK-1.6-Windows-32位 纯官方安装版
三部分: jdk-1.6-linux-64-1 jdk-1.6-linux-64-2 jdk-1.6-linux-64-3
三部分: jdk-1.6-linux-64-1 jdk-1.6-linux-64-2 jdk-1.6-linux-64-3
jdk1.6-jdk-6u43-windows32-i586
logback-cfca-jdk1.6-3.1.0.0.jar
1、okhttp3.8源码使用jdk1.6重新编译,已集成了okio,仅在javaweb项目中使用。 2、另附json-20160810.jar
jdk-1.6-linux-32-1 jdk-1.6-linux-32-2 jdk-1.6-linux-32-3
jdk1.6 源码
解决JDK1.6下的Base64报错问题,资源文件里有jar包,及替换方法
jdk-1.6-windows-32-1 jdk-1.6-windows-32-2 jdk-1.6-windows-32-3
适用平台:windows x64 jdk版本:1.6 安装方式:双击安装即可
jdk1.6,jdk1.7,jdk1.8以及jre1.6,jre1.7,jre1.8
jdk-1.6-linux-32-1 jdk-1.6-linux-32-2 jdk-1.6-linux-32-3