javalinkedlist工作原理及实现-java开发java经验技巧

《javalinkedlist工作原理及实现-java开发java经验技巧》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、JavaLinkcdListIE作原理及实现-编程开发技术JavaLinkedList工作原理及实现原文出处：Yikun1.概述以双向链表实现。链表无容量限制，但XX向链表本身使用了更多空间，也需要额外的链表指针操作。按下标访问元素一get(i)/set(i,e)要悲剧的遍历链表将指针移动到位(如果i>数组大小的一半，会从末尾移起)。插入、删除元素时修改前后节点的指针即可，但还是要遍历部分链表的指针才能移动到下标所指的位置，只冇在链表两头的操作—add(),addFirst(),removeLast()iterator()remove()能省掉指针的

2、移动。LinkedList是一个简单的数据结构，与ArrayList不同的是，他是基于链表实现的。Doubly-linkedlistimplementationoftheListandDequeinterfaces.Implementsalloptionallistoperations,andpermitsallelements(includingnull).LinkedList1ist二newLinkedList();list,addC语文：1〃);list,add(z，数学:2〃);list,add(〃英语:3〃)

3、;firstlastlistLinkedList(▲firstLinkedListSNodet>▲item•语文V(id=35)t>▲nextLinkedListSNodc▲prevnull▲lastLinkedListSNodet>■item•英语:3°(id=41)▲nextnull>▲prevLinkedListSNodeOmodCount3▲size3[语文：1,数学；2,英语：3]2.set和get函数publicEset(intindex,Eelement){checkElementIndex(index);Nodcx二nod

4、e(index);EoldVal=x.item;x.item=element;returnoldVal;}publicEget(intindex){checkElementlndex(index);returnnode(index).item;}这两个函数都调用了node函数，该函数会以0(n/2)的性能去获取一个节点，貝体实现如下所示：Nodenode(intindex){//assertisElementTndex(index);if(index<(size>>1))Nodex=first;for(inti=0;i

5、)x二x.next;returnx;}else{Nodex=last;for(inti=size-1;i>index;i--)x二x.prev;returnx;就是判断index是在前半区间还是后半区间，如果在前半区间就从head搜索，而在后半区间就从怡il搜索。而不是一宜从头到尾的搜索。如此设计，将节点访问的复杂度由0(n)变为0(n/2)。参考资料LinkedList(JavaPlatformSE8)