LinkedList同时实现了List接口和Deque接口,也就是说它既可以看作一个顺序容器,又可以看作一个队列(Queue),同时又可以看作一个栈(Stack)。这样看来,LinkedList简直就是个全能冠军。当你需要使用栈或者队列时,可以考虑使用LinkedList,一方面是因为Java官方已经声明不建议使用Stack类,更遗憾的是,Java里根本没有一个叫做Queue的类(它是个接口名字)。关于栈或队列,现在的首选是ArrayDeque,它有着比LinkedList(当作栈或队列使用时)有着更好的性能。
LinkedList底层通过双向链表实现,本节将着重讲解插入和删除元素时双向链表的维护过程,也即是之间解跟List接口相关的函数,而将Queue和Stack以及Deque相关的知识放在下一节讲。双向链表的每个节点用内部类Node表示。LinkedList通过first
和last
引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元,当链表为空的时候first
和last
null
next; Nodeprev, E element, NodeCollections.synchronizedList
方法对其进行包装。add方法有两个版本,一个是add(E e)
,该方法在LinkedList的末尾插入元素,因为有last
指向链表末尾,在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可;另一个是add(int index, E element)
,该方法是在指定下表处插入元素,需要先通过线性查找找到具体位置,然后修改相关引用完成插入操作。add(E e)
//add(E e) public boolean add(E e) { final Nodel = last; final Nodenode(int index)
函数有一点小小的trick,因为链表双向的,可以从开始往后找,也可以从结尾往前找,具体朝那个方向找取决于条件index < (size >> 1)
,也即是index是靠近前端还是后端。removeremove
方法也有两个版本,一个是删除跟指定元素相等的第一个元素remove(Object o)
,另一个是删除指定下标处的元素remove(int index)
两个删除操作都要1.先找到要删除元素的引用,2.修改相关引用,完成删除操作。在寻找被删元素引用的时候调用的是元素的方法,而使用的是下标计数,两种方式都是线性时间复杂度。在步骤2中,两个revome
unlink(Node方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。//unlink(Nodex) { final E element = x.item; final Nodenext = x.next; final Nodeget(int index)
得到指定下标处元素的引用,通过调用上文中提到的node(int index)
方法实现。set(int index, E element)
方法将指定下标处的元素修改成指定值,也是先通过node(int index)
找到对应下表元素的引用,然后修改Node
中public E set(int index, E element) { checkElementIndex(index); Node联系客服