正文
java与数据结构(3)---java实现循环链表
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
循环链表：将单链表中尾结点的指针由空指针改为指向头结点，就使整个单链表形成一个环，这种首尾相接的单链表称为单链表循环表，即循环链表。
循环链表与单链表最重要的区别是：尾结点的指针，不再是p->next = null;而是：p->next=head。
接口
1 //接口类
2 interface Listable<T> {
3
4 public void clear();
5
6 public boolean isEmpty();
7
8 public int Length();
9
10 public T getElement(int index);
11
12 public boolean add(T element);
13
14 public boolean addHead(T element);
15
16 public boolean addByIndex(int index, T element);
17
18 public boolean add(Listable<T> list);
19
20 public T remove(int index);
21
22 public boolean removeAll();
23
24 public T remove(T element);
25
26 public T setElement(int index,T element);
27
28 }
节点类
1 //结点类
2 class Node<T> {
3 private T data;
4 private Node next;
5
6 Node(T data, Node next) {
7 this.data = data;
8 this.next = next;
9 }
10
11 Node(T data) {
12 this(data,null);
13 }
14
15 Node() {
16 this(null,null);
17 }
18
19 public T getData() {
20 return this.data;
21 }
22
23 public Node getNext() {
24 return this.next;
25 }
26
27 public void setData(T data) {
28 this.data = data;
29 }
30
31 public void setNext(Node next) {
32 this.next = next;
33 }
34
35 public String toString() {
36 return getData().toString();
37 }
38
39 }
接口实现类
1 class CircularLinkedList<T> implements Listable<T> {
2 public Node<T> head,tail;
3
4 // 建空表，头为结点和尾结点都指向自己
5 CircularLinkedList() {
6 this(null);
7 }
8
9 // 建表，如果参数为空，建空表；若参数不为空，建一张有头有尾的结点，尾结点的指针指向头结点
10 CircularLinkedList(T data) {
11 if(data == null) {
12 head = new Node<T>(data,null);//创建头结点，数据为data,指针为空
13 tail = head;//尾结点和头结点相同
14 tail.setNext(head);//尾结点指针域指向头结点，使首尾形成环
15 }else {
16 head = new Node<T>();
17 tail = new Node<T>(data,head);
18 head.setNext(tail);//等价于head.next = tail;
19 }
20 }
21
22 // 清空链表，头=尾，this = null;
23 public void clear() {
24 removeAll();
25 head.setNext(tail);
26 tail.setNext(head);
27 head = tail;
28 }
29
30 // 如果头=尾，返回true;否则，返回false
31 public boolean isEmpty() {
32 return tail == head;
33 }
34
35 // 获取链表当前元素个数，即表长
36 public int Length() {
37 int len = 0;
38 Node<T> temp = head;
39 while(temp.getNext() != head) {
40 len++;
41 temp = temp.getNext();
42 }
43 return len;
44 }
45
46 // 取index处的数据元素
47 public T getElement(int index) {
48 if(index < 0) return null;
49 Node<T> temp = head;
50 int j = 0;
51 while(j <= index && temp.getNext() != head) {
52 j++;
53 temp = temp.getNext();
54 }
55 return temp.getData();
56 }
57
58 // 将参数链表添加到当前链表的后面
59 public boolean add(Listable<T> list) {
60 CircularLinkedList<T> slist = (CircularLinkedList<T>)list;
61 tail.setNext(slist.head.getNext());
62 slist.tail.setNext(head);
63 slist.head.setNext(null);
64 slist.head = null;
65 return true;
66 }
67
68 // 尾添
69 public boolean add(T element) {
70 if(element == null) return false;
71 Node<T> temp = new Node<T>(element,head);
72 tail.setNext(temp);
73 tail = temp;
74 return true;
75 }
76
77 // 首添
78 public boolean addHead(T element) {
79 if(element == null) return false;
80 Node<T> temp = new Node<T>(element,head.getNext());
81 head.setNext(temp);
82 return true;
83 }
84
85 // 任意位置添加
86 public boolean addByIndex(int index, T element) {
87 if(element == null) return false;
88 if(index <= 0)
89 addHead(element);
90 if(index >= Length())
91 add(element);
92 if(index > 0 && index < Length()) {
93 int j = 0;
94 Node<T> temp = head;
95 Node<T> tempNext = temp.getNext();
96 while(j < index && tempNext != head) {
97 j++;
98 temp = tempNext;
99 tempNext = tempNext.getNext();
100 }
101 Node<T> node = new Node<T>(element,tempNext);
102 temp.setNext(node);
103 }
104 return true;
105 }
106
107 // 删除循环表中所有的数据元素
108 public boolean removeAll() {
109 if(isEmpty()) return false;
110 Node<T> tempNext = head.getNext();
111 while(tempNext != head) {
112 tempNext = tempNext.getNext();
113 head.setNext(tempNext);
114 }
115 return true;
116 }
117
118 // 删除指定位置上的元素
119 public T remove(int index) {
120 if(isEmpty()) return null;
121 T element = null;
122 if(index <= 0)
123 return removeHead();
124 if(index > Length())
125 index = Length()-1;
126 if(index > 0) {
127 int j = 0;
128 Node<T> temp = head;
129 Node<T> tempNext = head.getNext();
130 while(j < index && tempNext != head) {
131 temp = tempNext;
132 tempNext = tempNext.getNext();
133 j++;
134 }
135 element = tempNext.getData();
136 temp.setNext(tempNext.getNext());
137 }
138 return element;
139 }
140
141 // 删除表中的第一条element的数据
142 public T remove(T element) {
143 if(isEmpty()) return null;
144 if(element == null) return null;
145 Node<T> temp = head.getNext();
146 while(temp != head) {
147 if(!(element.equals(temp.getData()))) {
148 temp = temp.getNext();
149 }else{
150 return element;
151 }
152 }
153 return null;
154 }
155
156 // 删除表头数据
157 private T removeHead() {
158 if(isEmpty()) return null;
159 Node<T> firstNode = head.getNext();
160 T element = firstNode.getData();
161 head.setNext(head.getNext().getNext());
162 return element;
163 }
164
165 // 修改指定位置上的数据元素，并将原数据返回给T
166 public T setElement(int index,T element) {
167 if(isEmpty()) return null;
168 if(element == null) return null;
169 T tempEle = null;
170 if(index < 0) {
171 return null;
172 }
173 if(index >= Length()-1) {
174 index = Length() - 1;
175 tempEle = tail.getData();
176 tail.setData(element);
177 return tempEle;
178 }else if(index > 0 && index < Length()-1) {
179 Node<T> temp = head;
180 int j = 0;
181 while(j < index && temp.getNext() != head) {
182 j++;
183 temp = temp.getNext();
184 }
185 tempEle = temp.getData();
186 temp.setData(element);
187 }
188 return tempEle;
189 }
190
191 // 重写父类toString()方法
192 public String toString() {
193 if(isEmpty())
194 return "[ ]";
195 StringBuffer sb = new StringBuffer();
196 sb.append("[ ");
197 int L = Length();
198 for(int i = 0; i < L; i++) {
199 sb.append(getElement(i)+" ");
200 }
201 sb.append("]");
202 return sb.toString();
203 }
204 }
测试类
1 package list;
2
3 /*
4 *@author Nora-Xie
5 *@time 2013-10-04 PM1708
6 *java实现循环链表
7 */
8
9 public class TestCircularLinkedList {
10 public static void main(String[] args) {
11 Listable<String> list = new CircularLinkedList<String>("a");
12 list.add("b");
13 list.add("c");
14 list.add("d");
15 list.add("f");
16 System.out.println(list);
17 list.setElement(4,"e");
18 list.add("f");
19 System.out.println(list);
20 System.out.println(list);
21 list.addByIndex(1,"B");
22 System.out.println(list.Length()+"list="+list);
23 list.addHead("A");
24 System.out.println(list.Length()+"list="+list);
25 list.remove(0);
26 System.out.println(list.Length()+"list="+list);
27 list.remove(9);
28 System.out.println(list.Length()+"list="+list);
29 Listable<String> list1 = new CircularLinkedList<String>( );
30 list1.add("1");
31 list1.add("2");
32 list1.add("3");
33 list1.add("4");
34 list1.add("5");
35 list1.add("6");
36 list1.add("7");
37 list1.add("8");
38 list.add(list1);
39 System.out.println(list);
40 list.clear();
41 System.out.println(list.isEmpty());
42 System.out.println(list.Length()+"list="+list);
43 }
44 }
