使用嵌套类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;
       }
   }
}

           

如果需要变为静态方法，则需要改变方法的传入参数，将链表的头结点传入