LinkedList源码解析

　　1。概述
　　LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。2。类图
　　LinkedList类图3。属性transientintsize0；first始终不变：1、集合没有元素：firstnulllastnull2、集合添加了元素：first。prevnullfirst。item！nulltransientNodeElast始终不变：1、集合没有元素：firstnulllastnull2、集合添加了元素：（last。nextnulllast。item！null）transientNodeEprivatestaticclassNodeE｛ENodeENodeENode（NodeEprev，Eelement，NodeEnext）｛this。this。this。｝｝4。无参构造构造一个空集合publicLinkedList（）｛｝5。添加元素5。1添加元素添加元素到链表末尾publicbooleanadd（Ee）｛linkLast（e）；｝firstlastfirstablastvoidlinkLast（Ee）｛finalNodeE创建节点finalNodeEnewNodenewNode（l，e，null）；last始终指向尾节点lastnewN首次添加元素if（lnull）first始终指向头节点firstnewNelsel。nextnewNmodC｝privatestaticclassNodeE｛ENodeENodeENode（NodeEprev，Eelement，NodeEnext）｛this。this。this。｝｝5。2指定位置添加元素publicvoidadd（intindex，Eelement）｛checkPositionIndex（index）；如果indexsize，直接在末尾添加，等同于add（e）方法if（indexsize）linkLast（element）；elselinkBefore（element，node（index））；｝返回需要修改节点的位置NodeEnode（intindex）｛根据当前添加元素的位置判断是从头开始找还是尾开始找if（index（size1））｛NodeEfor（inti0；i）xx。｝else｛NodeEfor（intisize1；i）xx。｝｝将前一个节点nextnewNode将后一个节点prenewNodevoidlinkBefore（Ee，NodeEsucc）｛assertsucc！finalNodeEpredsucc。finalNodeEnewNodenewNode（pred，e，succ）；succ。prevnewNif（prednull）firstnewNelsepred。nextnewNmodC｝
　　add操作6。获取元素6。1获取第一个元素publicEgetFirst（）｛finalNodeEif（fnull）thrownewNoSuchElementException（）；returnf。｝6。2获取最后一个元素publicEgetLast（）｛finalNodeEif（lnull）thrownewNoSuchElementException（）；returnl。｝7移除元素publicbooleanremove（Objecto）｛if（onull）｛for（NodeEx！xx。next）｛if（x。itemnull）｛unlink（x）；｝｝｝else｛for（NodeEx！xx。next）｛if（o。equals（x。item））｛unlink（x）；｝｝｝｝Eunlink（NodeEx）｛assertx！finalEelementx。finalNodeEnextx。finalNodeEprevx。if（prevnull）｛｝else｛prev。x。｝if（nextnull）｛｝else｛next。x。｝x。modC｝
　　remove操作8小结LinkedList是链表结构，所以不存在扩容。LinkedList基于节点实现的双向链表的List，每个节点都指向前一个和后一个节点从而形成链表。LinkedList随机访问平均时间复杂度是O（n），查找指定元素的平均时间复杂度是多少O（n）。LinkedList移除指定位置的元素的最好时间复杂度是O（1），最坏的时间复杂度是O（n），平均时间复杂度是O（n）。LinkedList添加元素的最好时间复杂度是O（1），最坏时间复杂度是O（n），平均时间复杂度是O（n）。