java与数据结构(4)---java实现双向循环链表
生活随笔
收集整理的這篇文章主要介紹了
java与数据结构(4)---java实现双向循环链表
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
線性表之鏈式存儲結構雙向循環鏈表
雙向循環鏈表：每個結點包含了數據、直接前驅地址指針和直接后驅地址指針，頭結點的直接前驅指向尾結點，尾結點的直接后驅指向頭結點，頭尾相連構成一個可正可反的圓環。可以形象的理解成一群孩子手拉手牽成一個圓圈，從頭一個孩子開始可以從左往右報數，也可以從右往左開始報數。
優點：雙向循環鏈表可以迅速的獲取當前數據的前驅數據，解決了單向循環鏈表從頭開始遍歷的麻煩。
接口類
1 package list; 2 3 public interface Listable<T> { 4 5 public void clear(); 6 7 public boolean isEmpty(); 8 9 public int Length(); 10 11 public T getElement(int index); 12 13 public boolean add(T element); 14 15 public boolean addHead(T element); 16 17 public boolean addByIndex(int index, T element); 18 19 public boolean add(Listable<T> list); 20 21 public T remove(int index); 22 23 public boolean removeAll(); 24 25 public T remove(T element); 26 27 public T setElement(int index,T element); 28 29 } View Code結點類
1 //結點類 2 class Node<T> { 3 private Node<T> left,right; 4 private T data; 5 6 Node(T data) { 7 this(data,null,null); 8 } 9 10 Node() { 11 this(null,null,null); 12 } 13 14 Node(T data,Node<T> left,Node<T> right) { 15 this.data = data; 16 this.left = left; 17 this.right = right; 18 } 19 20 public T getData() { 21 return this.data; 22 } 23 24 public Node<T> getLeft() { 25 return this.left; 26 } 27 28 public Node<T> getRight() { 29 return this.right; 30 } 31 32 public void setData(T data) { 33 this.data = data; 34 } 35 36 public void setRight(Node<T> right) { 37 this.right = right; 38 } 39 40 public void setLeft(Node<T> left) { 41 this.left = left; 42 } 43 44 public String toString() { 45 return getData().toString(); 46 } 47 } View Code接口實現類
1 //接口實現類 2 class DoubleLinkedList<T> implements Listable<T> { 3 public Node<T> head; 4 5 //建空表,帶頭結點 6 DoubleLinkedList() { 7 this(null); 8 } 9 10 //建表，帶頭結點，表中有一條數據元素 11 DoubleLinkedList(T element) { 12 if(element == null) { 13 head = new Node<T>(element,null,null); 14 head.setRight(head); 15 head.setLeft(head); 16 }else { 17 Node<T> headRight = new Node<T>(element,null,null); 18 head = new Node<T>(null,headRight,headRight); 19 headRight.setLeft(head); 20 headRight.setRight(head); 21 } 22 } 23 24 //清空當前鏈表 25 public void clear() {} 26 27 //判空表 28 public boolean isEmpty() { 29 return head.getRight() == head; 30 } 31 32 //表長 33 public int Length() { 34 int len = 0; 35 Node<T> temp = head; 36 while(temp.getRight() != head) { 37 len++; 38 temp = temp.getRight(); 39 } 40 return len; 41 } 42 43 //取下標index處的數據 44 public T getElement(int index) { 45 if(index <= 0) { 46 return head.getRight().getData(); 47 } 48 int len = Length(); 49 if(index >= len) { 50 return head.getLeft().getData(); 51 } 52 T element = null; 53 if(index > 0 && index < len) { 54 int k = 0; 55 Node<T> temp = head; 56 //此處只能用while不能用if，用錯好幾次 57 while(k <= index && temp.getRight() != head) { 58 k++; 59 temp = temp.getRight(); 60 } 61 element = temp.getData(); 62 } 63 return element; 64 } 65 66 //尾添 67 public boolean add(T element) { 68 if(element == null) return false; 69 Node<T> node = new Node<T>(element,head.getLeft(),head); 70 head.getLeft().setRight(node); 71 head.setLeft(node); 72 return true; 73 } 74 75 //首添 76 public boolean addHead(T element) { 77 if(element == null) return false; 78 Node<T> node = new Node<T>(element,head,head.getRight()); 79 head.getRight().setLeft(node); 80 head.setRight(node); 81 return false; 82 } 83 84 //表index處，添加新數據element 85 public boolean addByIndex(int index, T element) { 86 if(index <= 0) { 87 return addHead(element); 88 }else if(index >= Length()) { 89 return add(element); 90 }else { 91 int k = 0; 92 Node<T> temp = head; 93 //此處只能用while不能用if，用錯好幾次 94 while(k <= index && temp.getRight() != head) { 95 k++; 96 temp = temp.getRight(); 97 } 98 Node<T> node = new Node<T>(element,temp.getLeft(),temp); 99 temp.getLeft().setRight(node); 100 temp.setLeft(node); 101 } 102 return true; 103 } 104 105 //將參數中的鏈表添加到當前鏈表的尾部 106 public boolean add(Listable<T> slist) { 107 if(slist.isEmpty() || slist == null) return false; 108 if(slist instanceof DoubleLinkedList) { 109 DoubleLinkedList<T> list = (DoubleLinkedList<T>)slist; 110 //以下操作影響到了添加的slist表，所以需要將slist表重新備份一個 111 DoubleLinkedList<T> temp = new DoubleLinkedList<T>(); 112 for(int i = 0; i < list.Length(); i++) { 113 temp.add(list.getElement(i)); 114 } 115 Node<T> node = temp.head; 116 Node<T> nodeLeft = node.getLeft(); 117 Node<T> nodeRight = node.getRight(); 118 this.head.getLeft().setRight(node.getRight()); 119 nodeRight.setLeft(this.head.getLeft()); 120 nodeLeft.setRight(this.head); 121 this.head.setLeft(node.getLeft()); 122 return true; 123 }else { 124 return false; 125 } 126 } 127 128 //刪除下標Index處的數據 129 public T remove(int index) { 130 if(isEmpty()) return null; 131 if(index < 0) { 132 index = 0; 133 } 134 int len = Length(); 135 if(index >= len) { 136 //當index大于或等于表長是，默認移走表的最后一個元素，即下標為len-1的數據 137 index = len-1; 138 } 139 T element = null; 140 if(index >= 0 && index < len) { 141 Node<T> temp = head; 142 int k = 0; 143 while(k <= index && temp.getRight() != head) { 144 k++; 145 temp = temp.getRight(); 146 } 147 element = temp.getData(); 148 temp.getRight().setLeft(temp.getLeft()); 149 temp.getLeft().setRight(temp.getRight()); 150 temp.setRight(null); 151 temp.setLeft(null); 152 temp = null; 153 } 154 return element; 155 } 156 157 //刪除當前鏈表中所有的數據，只剩頭結點 158 public boolean removeAll() { 159 if(isEmpty()) return false; 160 Node<T> temp = head.getRight(); 161 while(temp != head) { 162 head.setRight(temp.getRight()); 163 temp.getRight().setLeft(head); 164 temp.setLeft(null); 165 temp.setRight(null); 166 temp = head.getRight(); 167 } 168 return true; 169 } 170 171 //刪除鏈表中從head開始的第一個element數據 172 public T remove(T element) { 173 if(isEmpty() || element == null) return null; 174 //從表中第一個元素開始比較 175 Node<T> temp = head.getRight(); 176 int k=0; 177 while(temp != head) { 178 if(element.equals(temp.getData())) { 179 remove(k); 180 return element; 181 }else { 182 temp = temp.getRight(); 183 k++; 184 } 185 } 186 if(k == (Length()-1)) { 187 System.out.println("該鏈表中沒有該數據"); 188 } 189 return element; 190 } 191 192 //修改下標index處的數據，并將原始數據返回 193 public T setElement(int index,T element) { 194 if(index < 0 || index >= Length()) return null; 195 Node<T> temp = head; 196 int k = 0; 197 while(k < index && temp.getRight() != head) { 198 k++; 199 temp = temp.getRight(); 200 } 201 T tempEle = temp.getData(); 202 temp.setData(element); 203 return tempEle; 204 } 205 206 //重寫父類toString方法，實際是給list做遍歷后將數據打印出來 207 public String toString() { 208 StringBuffer sb = new StringBuffer(); 209 /*通過for循環遍歷雙向循環鏈表 210 int length = Length(); 211 sb.append("[ "); 212 for(int i = 0; i < length; i++) { 213 sb.append(getElement(i)+" "); 214 } 215 sb.append("]"); 216 */ 217 //從表頭開始遍歷雙向循環鏈表 218 sb.append("[ "); 219 Node<T> node = head; 220 while(node.getRight() != head) { 221 sb.append(node.getRight().getData()+" "); 222 node = node.getRight(); 223 } 224 sb.append("]"); 225 return sb.toString(); 226 } 227 228 } View Code測試類
1 package list; 2 3 //************************************************ 4 //*雙向循環鏈表-java實現(畫圖分析會容易理解得多) 5 //************************************************ 6 7 public class TestDoubleLinkedList { 8 public static void main(String[] args) { 9 Listable<String> list = new DoubleLinkedList<String>("a"); 10 list.add("b"); 11 list.add("c"); 12 list.addByIndex(3,"e"); 13 list.addByIndex(3,"d"); 14 list.addByIndex(5,"f"); 15 System.out.println(list); 16 list.addHead("A"); 17 System.out.println(list.Length()); 18 System.out.println(list); 19 Listable<String> list1 = new DoubleLinkedList<String>("123456"); 20 list.add(list1); 21 System.out.println(list); 22 list.remove(100); 23 list.add("123456"); 24 System.out.println("list="+list); 25 System.out.println(list1); 26 list1.removeAll(); 27 System.out.println(list1+" list1 is Empty??"+list1.isEmpty()); 28 list.remove("123456"); 29 System.out.println("list="+list); 30 System.out.println("remove item="+list.remove("A")); 31 System.out.println("list="+list); 32 } 33 } View Code完整代碼
1 package list; 2 3 //************************************************ 4 //*雙向循環鏈表-java實現(畫圖分析會容易理解得多) 5 //************************************************ 6 7 public class TestDoubleLinkedList { 8 public static void main(String[] args) { 9 Listable<String> list = new DoubleLinkedList<String>("a"); 10 list.add("b"); 11 list.add("c"); 12 list.addByIndex(3,"e"); 13 list.addByIndex(3,"d"); 14 list.addByIndex(5,"f"); 15 System.out.println(list); 16 list.addHead("A"); 17 System.out.println(list.Length()); 18 System.out.println(list); 19 Listable<String> list1 = new DoubleLinkedList<String>("123456"); 20 list.add(list1); 21 System.out.println(list); 22 list.remove(100); 23 list.add("123456"); 24 System.out.println("list="+list); 25 System.out.println(list1); 26 list1.removeAll(); 27 System.out.println(list1+" list1 is Empty??"+list1.isEmpty()); 28 list.remove("123456"); 29 System.out.println("list="+list); 30 System.out.println("remove item="+list.remove("A")); 31 System.out.println("list="+list); 32 } 33 } 34 35 //結點類 36 class Node<T> { 37 private Node<T> left,right; 38 private T data; 39 40 Node(T data) { 41 this(data,null,null); 42 } 43 44 Node() { 45 this(null,null,null); 46 } 47 48 Node(T data,Node<T> left,Node<T> right) { 49 this.data = data; 50 this.left = left; 51 this.right = right; 52 } 53 54 public T getData() { 55 return this.data; 56 } 57 58 public Node<T> getLeft() { 59 return this.left; 60 } 61 62 public Node<T> getRight() { 63 return this.right; 64 } 65 66 public void setData(T data) { 67 this.data = data; 68 } 69 70 public void setRight(Node<T> right) { 71 this.right = right; 72 } 73 74 public void setLeft(Node<T> left) { 75 this.left = left; 76 } 77 78 public String toString() { 79 return getData().toString(); 80 } 81 } 82 83 //接口實現類 84 class DoubleLinkedList<T> implements Listable<T> { 85 public Node<T> head; 86 87 //建空表,帶頭結點 88 DoubleLinkedList() { 89 this(null); 90 } 91 92 //建表，帶頭結點，表中有一條數據元素 93 DoubleLinkedList(T element) { 94 if(element == null) { 95 head = new Node<T>(element,null,null); 96 head.setRight(head); 97 head.setLeft(head); 98 }else { 99 Node<T> headRight = new Node<T>(element,null,null); 100 head = new Node<T>(null,headRight,headRight); 101 headRight.setLeft(head); 102 headRight.setRight(head); 103 } 104 } 105 106 //清空當前鏈表 107 public void clear() {} 108 109 //判空表 110 public boolean isEmpty() { 111 return head.getRight() == head; 112 } 113 114 //表長 115 public int Length() { 116 int len = 0; 117 Node<T> temp = head; 118 while(temp.getRight() != head) { 119 len++; 120 temp = temp.getRight(); 121 } 122 return len; 123 } 124 125 //取下標index處的數據 126 public T getElement(int index) { 127 if(index <= 0) { 128 return head.getRight().getData(); 129 } 130 int len = Length(); 131 if(index >= len) { 132 return head.getLeft().getData(); 133 } 134 T element = null; 135 if(index > 0 && index < len) { 136 int k = 0; 137 Node<T> temp = head; 138 //此處只能用while不能用if，用錯好幾次 139 while(k <= index && temp.getRight() != head) { 140 k++; 141 temp = temp.getRight(); 142 } 143 element = temp.getData(); 144 } 145 return element; 146 } 147 148 //尾添 149 public boolean add(T element) { 150 if(element == null) return false; 151 Node<T> node = new Node<T>(element,head.getLeft(),head); 152 head.getLeft().setRight(node); 153 head.setLeft(node); 154 return true; 155 } 156 157 //首添 158 public boolean addHead(T element) { 159 if(element == null) return false; 160 Node<T> node = new Node<T>(element,head,head.getRight()); 161 head.getRight().setLeft(node); 162 head.setRight(node); 163 return false; 164 } 165 166 //表index處，添加新數據element 167 public boolean addByIndex(int index, T element) { 168 if(index <= 0) { 169 return addHead(element); 170 }else if(index >= Length()) { 171 return add(element); 172 }else { 173 int k = 0; 174 Node<T> temp = head; 175 //此處只能用while不能用if，用錯好幾次 176 while(k <= index && temp.getRight() != head) { 177 k++; 178 temp = temp.getRight(); 179 } 180 Node<T> node = new Node<T>(element,temp.getLeft(),temp); 181 temp.getLeft().setRight(node); 182 temp.setLeft(node); 183 } 184 return true; 185 } 186 187 //將參數中的鏈表添加到當前鏈表的尾部 188 public boolean add(Listable<T> slist) { 189 if(slist.isEmpty() || slist == null) return false; 190 if(slist instanceof DoubleLinkedList) { 191 DoubleLinkedList<T> list = (DoubleLinkedList<T>)slist; 192 //以下操作影響到了添加的slist表，所以需要將slist表重新備份一個 193 DoubleLinkedList<T> temp = new DoubleLinkedList<T>(); 194 for(int i = 0; i < list.Length(); i++) { 195 temp.add(list.getElement(i)); 196 } 197 Node<T> node = temp.head; 198 Node<T> nodeLeft = node.getLeft(); 199 Node<T> nodeRight = node.getRight(); 200 this.head.getLeft().setRight(node.getRight()); 201 nodeRight.setLeft(this.head.getLeft()); 202 nodeLeft.setRight(this.head); 203 this.head.setLeft(node.getLeft()); 204 return true; 205 }else { 206 return false; 207 } 208 } 209 210 //刪除下標Index處的數據 211 public T remove(int index) { 212 if(isEmpty()) return null; 213 if(index < 0) { 214 index = 0; 215 } 216 int len = Length(); 217 if(index >= len) { 218 //當index大于或等于表長是，默認移走表的最后一個元素，即下標為len-1的數據 219 index = len-1; 220 } 221 T element = null; 222 if(index >= 0 && index < len) { 223 Node<T> temp = head; 224 int k = 0; 225 while(k <= index && temp.getRight() != head) { 226 k++; 227 temp = temp.getRight(); 228 } 229 element = temp.getData(); 230 temp.getRight().setLeft(temp.getLeft()); 231 temp.getLeft().setRight(temp.getRight()); 232 temp.setRight(null); 233 temp.setLeft(null); 234 temp = null; 235 } 236 return element; 237 } 238 239 //刪除當前鏈表中所有的數據，只剩頭結點 240 public boolean removeAll() { 241 if(isEmpty()) return false; 242 Node<T> temp = head.getRight(); 243 while(temp != head) { 244 head.setRight(temp.getRight()); 245 temp.getRight().setLeft(head); 246 temp.setLeft(null); 247 temp.setRight(null); 248 temp = head.getRight(); 249 } 250 return true; 251 } 252 253 //刪除鏈表中從head開始的第一個element數據 254 public T remove(T element) { 255 if(isEmpty() || element == null) return null; 256 //從表中第一個元素開始比較 257 Node<T> temp = head.getRight(); 258 int k=0; 259 while(temp != head) { 260 if(element.equals(temp.getData())) { 261 remove(k); 262 return element; 263 }else { 264 temp = temp.getRight(); 265 k++; 266 } 267 } 268 if(k == (Length()-1)) { 269 System.out.println("該鏈表中沒有該數據"); 270 } 271 return element; 272 } 273 274 //修改下標index處的數據，并將原始數據返回 275 public T setElement(int index,T element) { 276 if(index < 0 || index >= Length()) return null; 277 Node<T> temp = head; 278 int k = 0; 279 while(k < index && temp.getRight() != head) { 280 k++; 281 temp = temp.getRight(); 282 } 283 T tempEle = temp.getData(); 284 temp.setData(element); 285 return tempEle; 286 } 287 288 //重寫父類toString方法，實際是給list做遍歷后將數據打印出來 289 public String toString() { 290 StringBuffer sb = new StringBuffer(); 291 /*通過for循環遍歷雙向循環鏈表 292 int length = Length(); 293 sb.append("[ "); 294 for(int i = 0; i < length; i++) { 295 sb.append(getElement(i)+" "); 296 } 297 sb.append("]"); 298 */ 299 //從表頭開始遍歷雙向循環鏈表 300 sb.append("[ "); 301 Node<T> node = head; 302 while(node.getRight() != head) { 303 sb.append(node.getRight().getData()+" "); 304 node = node.getRight(); 305 } 306 sb.append("]"); 307 return sb.toString(); 308 } 309 310 } View Code后期會添加兩個鏈表求交集等操作。
轉載于:https://www.cnblogs.com/nora-xie/p/3352909.html
總結
以上是生活随笔為你收集整理的java与数据结构(4)---java实现双向循环链表的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： My First Blog on cnb
- 下一篇： 细说PHP中strlen和mb_strl