linux内核源码剖析JavaLinkedList——源码剖析

LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。这样看来，LinkedList简直就是个全能冠军。当你需要使用栈或者队列的时候，首先应该考虑的就是LinkedList。因为Java官方已经声明不建议使用Stack类，推荐使用LinkedList，更遗憾的是，Java里根本没有一个叫做Queue的类（它是个接口名字）。LinkedList底层通过双向链表实现，本节将着重讲解插入和删除元素时双向链表的维护过程，也即是之间解跟List接口相关的函数，而将Queue和Stack以及Deque相关的知识放在下一节讲。双向链表的每个节点用内部类Node表示。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元，当链表为空的时候first和last都指向null。//Node内部类privatestaticclassNode{Eitem;Nodenext;Nodeprev;Node(Nodeprev,Eelement,Nodenext){this.item=element;this.next=next;this.prev=prev;}}LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步（synchronized），如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。方法剖析add()add()方法有两个版本，一个是add(Ee)，该方法在LinkedList的末尾插入元素，因为有last指向链表末尾，在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可；另一个是add(intindex,Eelement)，该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。结合上图，可以看出add(Ee)的逻辑非常简单。

本文来自投稿，不代表长河网立场,转载请注明出处： http://www.changhe99.com/a/AEd4QJ3O6o.html