双向链表：就是有双向指针，即双向的链域。链结点的结构：┌────┬────┬────────┐│data│next│previous│└────┴────┴────────┘双向链表不必是双端链表(持有对最后一个链结点的引用)，双端链表插入时是双向的。有两条链：一条从头到尾，一条从尾到头，删除遍历时也是双向的。/***双向链表*/publicclassDoublyLinkedList{privateLinkhead;//首结点privateLinkrear;//尾部指针publicDoublyLinkedList(){}publicTpeekHead(){if(head!=null){returnhead.data;}returnnull;}publicbooleanisEmpty(){returnhead==null;}publicvoidinsertFirst(Tdata){//插入到链头LinknewLink=newLink(data);if(isEmpty()){//为空时，第1次插入的新结点为尾结点rear=newLink;}else{head.previous=newLink;//旧头结点的上结点等于新结点}newLink.next=head;//新结点的下结点旧头结点head=newLink;//赋值后，头结点的下结点是旧头结点，上结点null}publicvoidinsertLast(Tdata){//在链尾插入LinknewLink=newLink(data);if(isEmpty()){head=newLink;}else{rear.next=newLink;}newLink.previous=rear;rear=newLink;//赋值后，尾结点的上结点是旧尾结点，下结点null}publicTdeleteHead(){//删除链头if(isEmpty())returnnull;Linktemp=head;head=head.next;//变更首结点，为下一结点if(head!=null){head.previous=null;}else{rear=null;}returntemp.data;}publicTdeleteRear(){//删除链尾if(isEmpty())returnnull;Linktemp=rear;rear=rear.previous;//变更尾结点，为上一结点if(rear!=null){rear.next=null;}else{head=null;}returntemp.data;}publicTfind(Tt){//从头到尾findif(isEmpty()){returnnull;}Linkfind=head;while(find!=null){if(!find.data.equals(t)){find=find.next;}else{break;}}if(find==null){returnnull;}returnfind.data;}publicTdelete(Tt){if(isEmpty()){returnnull;}Linkcurrent=head;while(!current.data.equals(t)){current=current.next;if(current==null){returnnull;}}if(current==head){head=head.next;if(head!=null){head.previous=null;}}elseif(current==rear){rear=rear.previous;if(rear!=null){rear.next=null;}}else{//中间的非两端的结点，要移除currentcurrent.next.previous=current.previous;current.previous.next=current.next;}returncurrent.data;}publicbooleaninsertAfter(Tkey,Tdata){//插入在key之后,key不存在returnfalseif(isEmpty()){returnfalse;}Linkcurrent=head;while(!current.data.equals(key)){current=current.next;if(current==null){returnfalse;}}LinknewLink=newLink(data);if(current==rear){rear=newLink;}else{newLink.next=current.next;current.next.previous=newLink;}current.next=newLink;newLink.previous=current;returntrue;}publicvoiddisplayList4Head(){//从头开始遍历System.out.println("List(first-->last):");Linkcurrent=head;while(current!=null){current.displayLink();current=current.next;}}publicvoiddisplayList4Rear(){//从尾开始遍历System.out.println("List(last-->first):");Linkcurrent=rear;while(current!=null){current.displayLink();current=current.previous;}}classLink{//链结点Tdata;//数据域Linknext;//后继指针，结点链域Linkprevious;//前驱指针，结点链域Link(Tdata){this.data=data;}voiddisplayLink(){System.out.println("thedatais"data.toString());}}publicstaticvoidmain(String[]args){DoublyLinkedListlist=newDoublyLinkedList();list.insertLast(1);list.insertFirst(2);list.insertLast(3);list.insertFirst(4);list.insertLast(5);list.displayList4Head();IntegerdeleteHead=list.deleteHead();System.out.println("deleteHead:"deleteHead);list.displayList4Head();IntegerdeleteRear=list.deleteRear();System.out.println("deleteRear:"deleteRear);list.displayList4Rear();System.out.println("find:"list.find(6));System.out.println("find:"list.find(3));System.out.println("deletefind:"list.delete(6));System.out.println("deletefind:"list.delete(1));list.displayList4Head();System.out.println("----在指定key后插入----");list.insertAfter(2,8);list.insertAfter(2,9);list.insertAfter(9,10);list.displayList4Head();}}