Java双向链表按照顺序添加节点的方法实例

package linkedlist;

public class DoubleLinkedListDemo {

     public static void main(String[] args) {

         // 测试

         System.out.println( "双向链表的测试" );

         // 创建节点

         Node node1 = new Node( 1 , "道明寺" );

         Node node2 = new Node( 2 , "花泽类" );

         Node node3 = new Node( 3 , "西门总二郎" );

         Node node4 = new Node( 4 , "美作玲" );

         // 创建一个双向链表

         DoubleLinkedList doubleLinkedList = new DoubleLinkedList();

         // 添加节点

         doubleLinkedList.addByOrder(node1);

         doubleLinkedList.addByOrder(node4);

         doubleLinkedList.addByOrder(node3);

         doubleLinkedList.addByOrder(node2);

         // 显示排序后的双向链表

         doubleLinkedList.list();

     }

}

// 创建一个双向链表的类

class DoubleLinkedList {

     // 先初始化头节点，头节点不动

     private Node head = new Node( 0 , "" );

     // 返回头节点

     public Node getHead() {

         return head;

     }

     // 添加节点时，根据编号将节点插入到指定位置

     // 如果有这个编号，则添加失败，并给出提示

     public void addByOrder(Node node) {

         // 头节点不能动，通过一个辅助指针（变量）帮助找到需要添加的位置

         Node temp = head;

         boolean flag = false ;   // flag标志添加的编号是否存在，默认为false

         while ( true ) {

             if (temp.next == null ) {

                 break ;

             }

             if (temp.next.no > node.no) {

                 break ;

             }

             if (temp.next.no == node.no) {

                 flag = true ;

                 break ;

             }

             temp = temp.next;   // 遍历链表

         }

         if (flag) {

             System.out.printf( "输入的编号%d已经存在,不能加入\n" , node.no);

         }

         else {

             // 为防止出现空指针的情况，需要对temp节点位置进行判断

             // 若双向链表尚未到达尾端，则需要将node节点与其相邻的后面的节点进行连接

             if (temp.next != null ) {

                 node.next = temp.next;

                 temp.next.pre = node;

             }

             // 无论双向链表是否到达尾端，都需要将node节点与其相邻的前面的节点进行连接

             temp.next = node;

             node.pre = temp;

         }

     }

     // 遍历双向链表的方法

     // 显示链表【遍历】

     public void list() {

         // 判断链表是否为空

         if (head.next == null ) {

             System.out.println( "链表为空" );

             return ;

         }

         // 因为头节点不能动，需要一个辅助变量来遍历

         Node temp = head.next;

         while ( true ) {

             // 判断是否到链表最后

             if (temp == null )

                 break ;

             // 输出节点的信息

             System.out.println(temp);

             // 将temp后移

             temp = temp.next;

         }

     }

}

// 创建一个双向链表的类

// 定义Node，每个Node对象就是一个节点

class Node {

     public int no;

     public String name;

     public Node next;   // 指向下一个节点，默认为null

     public Node pre;    // 指向前一个节点，默认为null

     // 构造器

     public Node( int no, String name) {

         this .no = no;

         this .name = name;

     }

     // 为了显示方便，重新toString

     @Override

     public String toString() {

         return "Node [no=" + no + ", name=" + name + "]" ;

     }

}