双链表

图示：

代码：

  1 import lombok.Data;
  2 
  3 public class DoubleLinkedListTest {
  4     public static void main(String[] args) {
  5         DoubleNode node1 = new DoubleNode(1, "吕布");
  6         DoubleNode node2 = new DoubleNode(2, "典韦");
  7         DoubleNode node3 = new DoubleNode(3, "赵云");
  8         DoubleNode node4 = new DoubleNode(4, "关羽");
  9         DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
 10 //        doubleLinkedList.tailInsert(node1);
 11 //        doubleLinkedList.tailInsert(node4);
 12 //        doubleLinkedList.tailInsert(node2);
 13 //        doubleLinkedList.tailInsert(node3);
 14         doubleLinkedList.orderInsert(node1);
 15         doubleLinkedList.orderInsert(node4);
 16         doubleLinkedList.orderInsert(node2);
 17         doubleLinkedList.orderInsert(node3);
 18         doubleLinkedList.ascList();
 19         System.out.println("~~~~~~");
 20 //        doubleLinkedList.descList();
 21         DoubleNode node5 = new DoubleNode(0, "张飞");
 22         doubleLinkedList.updateByNo(node5);
 23         doubleLinkedList.ascList();
 24 //        doubleLinkedList.delByNo(5);
 25 //        doubleLinkedList.ascList();
 26 
 27     }
 28 }
 29 
 30 @Data
 31 class DoubleNode {
 32     /**
 33      * 编号
 34      */
 35     private int no;
 36 
 37     /**
 38      * 名称
 39      */
 40     private String name;
 41 
 42     private DoubleNode prev;
 43     private DoubleNode next;
 44 
 45     public DoubleNode() {
 46 
 47     }
 48 
 49     public DoubleNode(int no, String name) {
 50         this.no = no;
 51         this.name = name;
 52     }
 53 
 54     @Override
 55     public String toString() {
 56         return "DoubleNode{" +
 57                 "no=" + no +
 58                 ", name='" + name + '\'' +
 59                 '}';
 60     }
 61 }
 62 
 63 class DoubleLinkedList {
 64     private DoubleNode headNode;
 65 
 66     public DoubleLinkedList() {
 67         headNode = new DoubleNode();
 68     }
 69 
 70     /**
 71      * 尾部添加节点
 72      * @param newNode
 73      * @return
 74      */
 75     public boolean tailInsert(DoubleNode newNode) {
 76         DoubleNode temp = headNode;
 77         while (temp.getNext() != null) {
 78             temp = temp.getNext();
 79         }
 80         temp.setNext(newNode);
 81         newNode.setPrev(temp);
 82         return true;
 83     }
 84 
 85     /**
 86      * 按编号顺序插入
 87      * @param newNode
 88      * @return
 89      */
 90     public boolean orderInsert(DoubleNode newNode) {
 91         DoubleNode temp = headNode;
 92         while (temp.getNext() != null) {
 93             if (temp.getNext().getNo() == newNode.getNo()) {
 94                 System.out.println("已存在编号相同的节点，无法插入");
 95                 return false;
 96             }
 97             if (temp.getNext().getNo() > newNode.getNo()) {
 98                 newNode.setNext(temp.getNext());
 99                 newNode.setPrev(temp);
100                 temp.getNext().setPrev(newNode);
101                 temp.setNext(newNode);
102                 return true;
103             }
104             temp = temp.getNext();
105         }
106         //遍历到最后没有找到比newNode的编号大的，插在最后面
107         temp.setNext(newNode);
108         newNode.setPrev(temp);
109         return true;
110     }
111 
112     /**
113      * 正序遍历
114      */
115     public void ascList() {
116         DoubleNode temp = headNode;
117         while (temp.getNext() != null) {
118             System.out.println(temp.getNext());
119             temp = temp.getNext();
120         }
121     }
122 
123     /**
124      * 倒序遍历
125      */
126     public void descList() {
127         DoubleNode temp = headNode;
128         while (temp.getNext() != null) {
129             temp = temp.getNext();
130         }
131 
132         while (true) {
133             System.out.println(temp);
134             if (temp.getPrev() == headNode) {
135                 break;
136             }
137             temp = temp.getPrev();
138         }
139     }
140 
141     /**
142      * 根据编号修改节点
143      * @param newNode
144      * @return
145      */
146     public boolean updateByNo(DoubleNode newNode) {
147         DoubleNode temp = headNode.getNext();
148         while (temp != null) {
149             if (temp.getNo() == newNode.getNo()) {
150                 temp.setName(newNode.getName());
151                 return true;
152             }
153             temp = temp.getNext();
154         }
155         System.out.println("未找到需修改的节点");
156         return false;
157     }
158 
159     /**
160      * 根据编号删除节点
161      * @param no
162      * @return
163      */
164     public boolean delByNo(int no) {
165         DoubleNode temp = headNode.getNext();
166         while (temp != null) {
167             if (temp.getNo() == no) {
168                 temp.getPrev().setNext(temp.getNext());
169                 if (temp.getNext() != null) {
170                     temp.getNext().setPrev(temp.getPrev());
171                 }
172                 return true;
173             }
174             temp = temp.getNext();
175         }
176         System.out.println("未找到需删除的节点");
177         return false;
178     }
179 }