Java源码解析LinkedList
本文基于jdk1.8进行分析。
LinkedList和ArrayList都是常用的java集合。ArrayList是数组，Linkedlist是链表，是双向链表。它的节点的数据结构如下。
privatestaticclassNode{ Eitem; Node next; Node prev; Node(Node prev,Eelement,Node next){ this.item=element; this.next=next; this.prev=prev; } }
成员变量如下。它有头节点和尾节点2个指针。
transientintsize=0; /** *Pointertofirstnode. *Invariant:(first==null&&last==null)|| *(first.prev==null&&first.item!=null) **/ transientNodefirst; /** *Pointertolastnode. *Invariant:(first==null&&last==null)|| *(last.next==null&&last.item!=null) **/ transientNode last;
下面看一下主要方法。首先是get方法。如下图。链表的get方法效率很低，这一点需要注意，也就是说，我们可以用for循环get(i)的方式去遍历ArrayList，但千万不要这样去遍历Linkedlist。因为Linkedlist进行get时，需要把从头结点或尾节点一个一个的找到第i个元素，效率很低。遍历LinkedList时应该使用foreach方式。
/**
*Returnstheelementatthespecifiedpositioninthislist.
*@paramindexindexoftheelementtoreturn
*@returntheelementatthespecifiedpositioninthislist
*@throwsIndexOutOfBoundsException{@inheritDoc}
**/
publicEget(intindex){
checkElementIndex(index);
returnnode(index).item;
}
/**
*Returnsthe(non-null)Nodeatthespecifiedelementindex.
**/
Nodenode(intindex){
//assertisElementIndex(index);
if(index<(size>>1)){
Nodex=first;
for(inti=0;ix=last;
for(inti=size-1;i>index;i--)
x=x.prev;
returnx;
}
}
下面是add方法，add方法把待添加的元素添加到链表末尾即可。
/** *Appendsthespecifiedelementtotheendofthislist. *Thismethodisequivalentto{@link#addLast}. *@parameelementtobeappendedtothislist *@return{@codetrue}(asspecifiedby{@linkCollection#add}) **/ publicbooleanadd(Ee){ linkLast(e); returntrue; } /** *Linkseaslastelement. **/ voidlinkLast(Ee){ finalNode
l=last; finalNode newNode=newNode<>(l,e,null); last=newNode; if(l==null) first=newNode; else l.next=newNode; size++; modCount++; }
Thisistheend。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对毛票票的支持。如果你想了解更多相关内容请查看下面相关链接
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。