数据结构之双向链表的java实现

《数据结构之双向链表的java实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构之双向链表的Java实现单链表只能从前往后遍历，如果链表的长度较大，遍历到链表后半部分的时候想要往前查找，就只能回到开头，重新遍历了。　　双向链表提供了这个能力，即允许前向遍历，也允许后向遍历整个链表。原因是双向链表的每个节点都有两个指向其他节点的引用。但这也是其缺点，因为在插入、删除的时候需要处理四个链接点的引用，占用的空间也大了一些。如将头节点和尾节点链接起来，即成为双向循环链表。　　下面是java代码：　　packagetest;　　publicclassDoubleLink{　　publicLinkfirst;　　publicLinklast;　　publicDouble

2、Link（）{//构造器，初始化　　this.first=null;　　this.last=null;　　}　　publicbooleanisEmpty（）{//判断是否为空　　returnfirst==null;　　}　　publicvoidinsertFirst（intidata）{//将元素插入链表开头　　Linklink=newLink（idata）；　　if（isEmpty（））　　last=link;//如果为空，last需要改变　　else　　first.previous=link;//非空，则要在first前插入　　link.next=first;　　first=link

3、;　　}　　publicvoidinsertLast（intidata）{//插入链表结尾　　Linklink=newLink（idata）；　　if（isEmpty（））　　first=link;　　else　　last.next=link;　　link.previous=last;　　last=link;　　}　　publicbooleaninsertAfter（intkey,intidata）{//在某项元素后插入　　Linkcurrent=first;　　while（current.idata!=key）{//从头开始查找　　current=current.next;　　if（c

4、urrent==null）//到表尾也没有找到　　returnfalse;　　}　　Linklink=newLink（idata）；　　if（current==last）{　　link.next=null;　　last=link;　　}else{　　link.next=current.next;　　current.next.previous=link;　　}　　link.previous=current;　　current.next=link;　　returntrue;　　}　　publicLinkdelectKey（intkey）{//删除某项元素　　Linkcurrent=first

5、;　　while（current.idata!=key）{　　current=current.next;　　if（current==null）　　returnnull;　　}　　if（current==first）　　first=current.next;　　else　　current.previous.next=current.next;　　if（current==last）　　last=current.previous;　　else　　current.next.previous=current.previous;　　returncurrent;　　}　　publicLinkdelec

6、tFirst（）{//删除链表开头元素　　Linktemp=first;　　if（first.next==null）//只有一个元素　　last=null;　　else　　first.next.previous=null;//first节点的next字段引用的链节点的previous字段　　first=first.next;　　returntemp;　　}publicLinkdelectLast（）{//删除链表最后的元素　　Linktemp=last;　　if（first.next==null）　　first=null;　　else　　last.previous.next=null;　

7、　last=last.previous;　　returntemp;　　}　　publicvoidshowFirst（）{//前向展示　　Linkcurrent=last;　　while（current!=null）{　　current.showLink（）；　　current=current.previous;　　}　　}　　publicvoidshowLast（）{//后向展示　　Linkcurrent=first;　　while