黑马程序员技术交流社区

标题: java双向链表 [打印本页]

---

作者: 罗忠文    时间: 2012-11-28 11:13
标题: java双向链表
1. package ChapterFive;   
2.   
3. class DoubleLink<E> {   
4.   
5.     public Link<E> first;   
6.   
7.     public Link<E> last;   
8.   
9.     int size;   
10.   
11.     @SuppressWarnings("hiding")   
12.     class Link<E> {   
13.         public E data;   
14.   
15.         public Link<E> next;// 链表的下一项   
16.   
17.         public Link<E> previous;// 链表的前一项   
18.   
19.         public Link(E value) {   
20.             this.data = value;   
21.         }   
22.     }   
23.   
24.     public DoubleLink() {   
25.         first = null;   
26.         last = null;   
27.         size = 0;   
28.     }   
29.   
30.     // 在链表的首部插入一项   
31.     public void insertFirst(E value) {   
32.         Link<E> newLink = new Link<E>(value);   
33.         if (isEmpty())// 如果链表为空则first == last   
34.             last = newLink;   
35.         else  
36.             first.previous = newLink;// 确定原first与newLink的前后关系   
37.         newLink.next = first;   
38.         first = newLink;// 设置新的first值   
39.         size++;   
40.     }   
41.   
42.     // 在链表的尾部插入一项   
43.     public void insertLast(E value) {   
44.         Link<E> newLink = new Link<E>(value);   
45.         if (isEmpty())// 如果链表为空则last == first   
46.             first = newLink;   
47.         else {   
48.             last.next = newLink;// 确定原last与newLink的前后关系   
49.             newLink.previous = last;   
50.         }   
51.         last = newLink;// 设置新的last值   
52.         size++;   
53.     }   
54.   
55.     // 删除双向链表的表头   
56.     public Link<E> deleteFirst() {   
57.         Link<E> temp = first;   
58.         if (first.next == null)// 链表中只有一项数据   
59.             last = null;   
60.         else  
61.             first.next.previous = null;// 销毁原链表的头部   
62.         first = first.next;   
63.         size--;   
64.         return temp;   
65.     }   
66.   
67.     // 删除链表的最后一项   
68.     public Link<E> deleteLast() {   
69.         Link<E> temp = last;   
70.         if (first.next == null)// 链表中只有一项数据   
71.             first = null;   
72.         else  
73.             last.previous.next = null;// 销毁原链表的尾部   
74.         last = last.previous;   
75.         size--;   
76.         return temp;   
77.     }   
78.   
79.     // 判断链表是否为空   
80.     public boolean isEmpty() {   
81.         return size == 0;   
82.     }   
83.   
84.     // 输出链表中的所有数据项   
85.     public void display() {   
86.         Link<E> curr = first;   
87.         while (curr != null) {   
88.             System.out.print(curr.data + " ");   
89.             curr = curr.next;   
90.         }   
91.         System.out.println();   
92.     }   
93. }   
94.   
95. public class DoubleLinkApp {   
96.     public static void main(String[] args) {   
97.         DoubleLink<Integer> dl = new DoubleLink<Integer>();   
98.         for (int i = 0; i < 5; i++) {   
99.             dl.insertFirst((int) (Math.random() * 100));   
100.         }   
101.         for (int i = 0; i < 5; i++) {   
102.             dl.insertLast((int) (Math.random() * 100));   
103.         }   
104.         dl.display();   
105.         while (!dl.isEmpty()) {   
106.             dl.deleteFirst();   
107.             dl.deleteLast();   
108.             dl.display();   
109.         }   
110.         System.out.println("Ok");   
111.     }   
112. }

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2