連結清單-雙向連結清單

import java.io.BufferedReader;
 import java.io.InputStreamReader;/**
  * Class DoubleLink 
  * Description 雙向連結清單提供了向前周遊和向後周遊的途徑。而普通連結清單隻能向後周遊.
  * Company OpenData 
  * Author Chenlly 
  * Date 09-02-07 
  * Version 1.0
  */
 class DLink {
  public int iData;
  public DLink next; // 後繼節點
  public DLink previous;// 前繼節點 // 構造函數
  public DLink(int iData) {
   this.iData = iData;
  } // 檢視節點資訊
  public void displayLink() {
   System.out.println("" + iData + ",");
  }
 }public class DoubleLink {
  private DLink firstLink; //雙向連結清單頭部
  private DLink lastLink;  //雙向連結清單尾部 // 構造函數
  public DoubleLink() {
   firstLink = null;
   lastLink = null;
  }
  
  //判斷連結清單是否為空
  public boolean isEmpty(){
   return firstLink == null;
  }
  
  // 建立新節點
  public DLink createDLink(int iData) {
   DLink dLink = new DLink(iData);
   return dLink;
  }
  
  
  // 在連結清單頭部插入新節點
  public void insertFirst(DLink dLink) {
   if (isEmpty()) {
    lastLink = dLink;//頭插法，lastLink就是第一個插入的節點
   } else {
    firstLink.previous = dLink;
    dLink.next = firstLink;
   }
   firstLink = dLink;
  }
  
  // 在連結清單尾部插入新節點
  public void insertLast(DLink dLink) {
   if (isEmpty()) {
    firstLink = dLink;//尾插法，firstLink就是第一個插入的節點
   } else {
    lastLink.next = dLink;
    dLink.previous = lastLink;
    lastLink = dLink;
   }
  }
  
  // 查找一個節點從頭周遊
  public DLink findByIDFromFirst(int key){
   DLink current = firstLink;
   while (current != null){
    if (current.iData == key){
     return current;
    } else {
     current = current.next;
    }
   }
   return null;
  }
  
  // 查找一個節點從尾周遊
  public DLink findByIDFromLast(int key){
   DLink current = lastLink;
   while (current != null){
    if (current.iData == key){
     return current;
    } else {
     current = current.previous;
    }
   }
   return null;
  }
  
  // 删除一個節點
  public DLink remove(int key) {
   DLink current = firstLink;
   if (current.iData == key){//被删除的節點是第一個節點
    firstLink = current.next;
   } else {
    if (current.next == null) {//被删除的節點是最後一個個節點
     current.previous.next = null;
    } else {被删除的節點既不是第一個也不是最後一個
     while ( current != null){
      if (current.iData == key){
       current.previous.next = current.next;
       current.next.previous = current.previous;
      } else {
       current = current.next;
      }
     }
    }
   }
   return null;
  } // 顯示雙向連結清單資訊從頭周遊
  public void displayFromFirst() {
   System.out.println("first-->last");
   DLink current = firstLink;
   if (isEmpty()){
    System.out.println("這是一個空連結清單");
   }
   while (current != null){
    current.displayLink();
    current = current.next;
   }
  }
  
  // 顯示雙向連結清單資訊從尾周遊
  public void displayFromLast() {
   System.out.println("last-->first");
   DLink current = lastLink;
   if (isEmpty()){
    System.out.println("這是一個空連結清單");
   }
   while (current != null){
    current.displayLink();
    current = current.previous;
   }
  }
  // 從鍵盤讀入資料
  public static String readStr() {
   InputStreamReader ir = new InputStreamReader(System.in);
   BufferedReader br = new BufferedReader(ir);
   String str = "";
   try {
    str = br.readLine();
   } catch (Exception ex) {
    ex.printStackTrace();
   }
   return str;
  } // 主調函數
  public static void main(String[] args) {
   System.out.println("請選擇操作序列");
   System.out.println("1 插入新節點");
   System.out.println("2 查找指定節點");
   System.out.println("3 删除指定的節點");
   System.out.println("4 顯示連結清單資訊");
   System.out.println("5 退出");
   DoubleLink dl = new DoubleLink();
   while (true){
   System.out.println("請選擇操作序列");
   int op = 0;
   try {
    op = Integer.parseInt(DoubleLink.readStr());
   } catch (Exception ex){
    System.out.println("輸入了無效字元");
    //ex.printStackTrace();
   } 
    switch (op){
     case 1:
      System.out.println("請選擇查找類别(a:頭插法，b:尾插法)");
      char ci = DoubleLink.readStr().charAt(0);
      System.out.println(""+ci);
      if (ci != 'a' && ci != 'b'){
       System.out.println("輸入有無"); break;
      }
      System.out.println("請輸入節點資訊");
      int iData = 0;
      try {
       iData = Integer.parseInt(DoubleLink.readStr());
      } catch (Exception ex){
       System.out.println("輸入了無效字元");
       //ex.printStackTrace();
      } 
      DLink dLink = dl.createDLink(iData);
      if (ci == 'a'){
       dl.insertFirst(dLink);
      } else {
       if (ci == 'b' ){
        dl.insertLast(dLink);
       }
      }
      break;
     case 2:
      if (dl.isEmpty()){
       System.out.println("這是一個空連結清單"); break; 
      }
      System.out.println("請輸入查找關鍵字Key值");
      int key = 0;
      try {
       key = Integer.parseInt(DoubleLink.readStr());
      } catch (Exception ex){
       System.out.println("輸入了無效字元");
       //ex.printStackTrace();
      }
      System.out.println("請選擇查找類别(a:從頭查找，b:從尾查找)");
      char cf = DoubleLink.readStr().charAt(0);
      DLink keyLink = null;
      if (cf == 'a'){
       keyLink = dl.findByIDFromFirst(key);
      } else {
       if (cf == 'b') {
        keyLink = dl.findByIDFromLast(key);
       } else {
        System.out.println("輸入有無"); break;
       }
      }
      if (keyLink != null){
       System.out.println("find the DLink is:" +keyLink.iData);
      } else {
       System.out.println(" not find the DLink by the key ");
      }
      break;
     case 3:
      if (dl.isEmpty()){
       System.out.println("這是一個空連結清單"); break; 
      }
      System.out.println("請輸入删除關鍵字Key值");
      int dkey = 0;
      try {
       dkey = Integer.parseInt(DoubleLink.readStr());
      } catch (Exception ex){
       System.out.println("輸入了無效字元");
       //ex.printStackTrace();
      }
      DLink dkeyLink = dl.remove(dkey);
      if (dkeyLink != null){
       System.out.println("節點" +dkeyLink.iData+ "已删除");
      } else {
       System.out.println("删除節點失敗");
      }
      break;
     case 4:
      System.out.println("請選擇查找類别(a:從頭周遊，b:從尾周遊)");
      char cd = DoubleLink.readStr().charAt(0);
      if (cd == 'a'){
       dl.displayFromFirst();
      } else {
        if (cd == 'b'){
        dl.displayFromLast();
       } else {
         System.out.println("輸入有誤"); break;
        }
       }
      break;
     case 5:
      default:
       System.exit(0);
    }//end switch
   }//end while
  }//end main
 }//end DoubleLink