双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
下面是在JAVA中实现双向链表
1 // firstLastList.java 2 // demonstrates list with first and last references 3 // to run this program: C>java FirstLastApp 4 //////////////////////////////////////////////////////////////// 5 class Link 6 { 7 public long dData; // data item 8 public Link next; // next link in list 9 // ------------------------------------------------------------- 10 public Link(long d) // constructor 11 { dData = d; } 12 // ------------------------------------------------------------- 13 public void displayLink() // display this link 14 { System.out.print(dData + " "); } 15 // ------------------------------------------------------------- 16 } // end class Link 17 //////////////////////////////////////////////////////////////// 18 class FirstLastList 19 { 20 private Link first; // ref to first link 21 private Link last; // ref to last link 22 // ------------------------------------------------------------- 23 public FirstLastList() // constructor 24 { 25 first = null; // no links on list yet 26 last = null; 27 } 28 // ------------------------------------------------------------- 29 public boolean isEmpty() // true if no links 30 { return first==null; } 31 // ------------------------------------------------------------- 32 public void insertFirst(long dd) // insert at front of list 33 { 34 Link newLink = new Link(dd); // make new link 35 36 if( isEmpty() ) // if empty list, 37 last = newLink; // newLink <-- last 38 newLink.next = first; // newLink --> old first 39 first = newLink; // first --> newLink 40 } 41 // ------------------------------------------------------------- 42 public void insertLast(long dd) // insert at end of list 43 { 44 Link newLink = new Link(dd); // make new link 45 if( isEmpty() ) // if empty list, 46 first = newLink; // first --> newLink 47 else 48 last.next = newLink; // old last --> newLink 49 last = newLink; // newLink <-- last 50 } 51 // ------------------------------------------------------------- 52 public long deleteFirst() // delete first link 53 { // (assumes non-empty list) 54 long temp = first.dData; 55 if(first.next == null) // if only one item 56 last = null; // null <-- last 57 first = first.next; // first --> old next 58 return temp; 59 } 60 // ------------------------------------------------------------- 61 public void displayList() 62 { 63 System.out.print("List (first-->last): "); 64 Link current = first; // start at beginning 65 while(current != null) // until end of list, 66 { 67 current.displayLink(); // print data 68 current = current.next; // move to next link 69 } 70 System.out.println(""); 71 } 72 // ------------------------------------------------------------- 73 } // end class FirstLastList 74 //////////////////////////////////////////////////////////////// 75 class FirstLastApp 76 { 77 public static void main(String[] args) 78 { // make a new list 79 FirstLastList theList = new FirstLastList(); 80 81 theList.insertFirst(22); // insert at front 82 theList.insertFirst(44); 83 theList.insertFirst(66); 84 85 theList.insertLast(11); // insert at rear 86 theList.insertLast(33); 87 theList.insertLast(55); 88 89 theList.displayList(); // display the list 90 91 theList.deleteFirst(); // delete first two items 92 theList.deleteFirst(); 93 94 theList.displayList(); // display again 95 } // end main() 96 } // end class FirstLastApp 97 ////////////////////////////////////////////////////////////////