使用嵌套類DoubleNode實作雙向連結清單

每一個節點都含有指向前驅節點的引用pre

每一個節點都含有指向後繼節點的引用next

實作以下功能：

1.在表頭插入節點

2.在表尾插入節點

3.從表頭删除節點

4.從表尾删除節點

5.從指定節點之前插入新節點

6.從指定節點之後插入新節點

7.删除指定節點

8.輸對外連結表

代碼

/**
* @author 鯉伴MAY
* @param <Item> 泛型
*/
public class TwoDirLinkedList <Item> {
   private class DoubleNode {
       Item item;
       DoubleNode pre;
       DoubleNode next;
   }
   private DoubleNode first;//指向首節點
   private DoubleNode last;//指向尾結點
   private int N;

   //判斷連結清單是否為空
   public boolean isEmpty() {
       return this.first == null;
   }

   public int size() {
       return this.N;
   }

   public  void insertAtFirst(Item item) {
       DoubleNode newNode = new DoubleNode();
       newNode.item = item;
       //處理空連結清單
       if(isEmpty()) {
           this.first = newNode;
           this.last = newNode;
       }else {
           newNode.next = this.first;
           first.pre = newNode;
           first = newNode;
       }
       N++;
   }

   public void insertAtLast(Item item) {
       DoubleNode newNode = new DoubleNode();
       newNode.item = item;
       //處理空連結清單
       if(isEmpty()) {
           this.first = newNode;
           this.last = newNode;
       }else {
           last.next = newNode;
           newNode.pre = last;
           last = newNode;
       }
       N++;
   }

   public DoubleNode deleteAtFirst(){
       if(first == null) {
           System.out.println("連結清單已空");
           return null;
       }
       DoubleNode temp;
       temp = first;
       //處理隻有一個節點的情況
       if(size() == 1) {
           first = null;
           last = null;
       }else {
           this.first = this.first.next;
           this.first.pre = null;
       }
       N--;
       return temp;
   }

   public DoubleNode deleteAtLast() {
       if(last == null) {
           System.out.println("連結清單已空");
           return null;
       }
       DoubleNode temp;
       temp = this.last;
       if(size() == 1) {
           first = null;
           last = null;
       }else {
           this.last = this.last.pre;
           this.last.next = null;
       }
       N--;
       return temp;
   }

   /**
    *
    * @param item
    * @return 傳回指向查找節點的指針，如果沒有，則傳回空
    */
   private DoubleNode findNode(Item item) {
       DoubleNode temp = this.first;
       while(temp != null) {
           if(temp.item.equals(item)){
               return temp;
           }
           temp = temp.next;
       }
       return null;
   }

   public boolean insertAtBefore(Item oldItem,Item newItem) {
       DoubleNode temp = findNode(oldItem);
       //處理幾種特殊情況
       if(temp == null) {
           System.out.println("連結清單中沒有指定節點");
           return false;
       } else if(temp.item.equals(first.item)) {
           insertAtFirst(newItem);
           return true;
       }
       DoubleNode newNode = new DoubleNode();
       newNode.item = newItem;
       newNode.next = temp;
       temp.pre.next = newNode;
       newNode.pre = temp.pre;
       temp.pre = newNode;
       N++;
       return true;
   }

   public boolean insertAtBehind(Item oldItem,Item newItem) {
       DoubleNode temp = findNode(oldItem);
       //處理特殊情況
       if(temp == null) {
           System.out.println("連結清單中沒有此節點");
           return false;
       } else if(temp.item.equals(last.item)) {
           insertAtLast(newItem);
           return true;
       }
       DoubleNode newNode = new DoubleNode();
       newNode.item = newItem;
       newNode.next = temp.next;
       temp.next.pre = newNode;
       newNode.pre = temp;
       temp.next = newNode;
       N++;
       return true;
   }
   public boolean deleteAt(Item item){
       DoubleNode temp = findNode(item);
       //處理特殊情況
       if(temp == null) {
           System.out.println("連結清單中沒有此節點");
           return false;
       }else if(temp.item.equals(first.item)) {
           deleteAtFirst();
           return true;
       }else if(temp.item.equals(last.item)) {
           deleteAtLast();
           return true;
       }
       temp.next.pre = temp.pre;
       temp.pre.next = temp.next;
       temp.pre = null;
       temp.next = null;
       N--;
       return true;
   }

   public void printList() {
       DoubleNode temp = first;
       while(temp != null) {
           System.out.println(temp.item);
           temp = temp.next;
       }
   }
}

           

如果需要變為靜态方法，則需要改變方法的傳入參數，将連結清單的頭結點傳入