首页 > 代码库 > java实现双链表（差点没写吐系列...）
java实现双链表（差点没写吐系列...）
刚才把单链表写完了，现在又把双链表写了，双链表和单链表的区别就是每个节点有prior和next两个指针，不同于单链表的一个next指针，而且，正是因为有这两个指针，所以双链表可以前后两个方向去移动指针，
同时，我所实现的双链表和单链表不同之处在于，主要体现在其不用每次都把指针从头结点开始遍历，而是根据实际情况从选择最优的线路去遍历，移动到想要的位置。差点写吐了....话不多说，上代码
1 package com.voole.linkedlist; 2 3 public class Test { 4 public static void main(String[] args) { 5 // LinkedList linkedList = new LinkedList(); 6 // linkedList.insert(new Node(null, null)); 7 // linkedList.insert(new Node(null, null)); 8 // linkedList.insert(new Node(null, null)); 9 // linkedList.insert(new Node(null, null)); 10 // linkedList.insert(new Node(null, null)); 11 // linkedList.insert(new Node(null, null),2); 12 // Node node = new Node(null, null); 13 // linkedList.update(node,2); 14 // System.out.println(linkedList.select(2)); 15 // System.out.println(node); 16 DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); 17 doubleLinkedList.insert(new Node(null, null, null)); 18 doubleLinkedList.insert(new Node(null, null, null)); 19 doubleLinkedList.insert(new Node(null, null, null)); 20 doubleLinkedList.insert(new Node(null, null, null)); 21 doubleLinkedList.insert(new Node(null, null, null),3); 22 doubleLinkedList.select(2); 23 } 24 } 25 26 27 28 package com.voole.linkedlist; 29 30 31 /** 32 * 双链表(该链表的效率比单链表高，主要体现在其不用每次都把指针从头结点开始遍历，而是根据实际情况从选择最优的线路去遍历，移动到想要的位置) 33 * @author TMAC-J 34 * 35 */ 36 public class DoubleLinkedList { 37 /** 38 * 头结点 39 */ 40 private Node head = null; 41 /** 42 * 链表长度 43 */ 44 private int size = 0; 45 /** 46 * 定义指针 47 */ 48 private int point = 0; 49 /** 50 * 当前指针指向的节点 51 */ 52 private Node currentNode = null; 53 /** 54 * 构造方法 55 */ 56 public DoubleLinkedList(){ 57 head = new Node(null, null, null); 58 } 59 /** 60 * 增(从末尾增加) 61 */ 62 public void insert(Node node){ 63 if(size == 0){ 64 head.next = node; 65 currentNode = node; 66 node.prior = head; 67 } 68 else{ 69 while(point<size){ 70 currentNode = currentNode.next; 71 point++; 72 } 73 currentNode.next = node; 74 node.prior = currentNode; 75 currentNode = node; 76 } 77 point++; 78 size++; 79 LinkedListLog.getInstance().insert(); 80 } 81 /** 82 * 增(从任意位置添加) 83 */ 84 public void insert(Node node,int position){ 85 checkPosition(position); 86 //如果指针离插入位置更近 87 if(Math.abs(position-point)<=position){ 88 if((position-point)>0){ 89 while(point<position-1){ 90 currentNode = currentNode.next; 91 point++; 92 } 93 node.next = currentNode.next; 94 currentNode.next = node; 95 node.prior = currentNode; 96 currentNode = node; 97 } 98 else if((position-point)<=0){ 99 while(point>position){ 100 currentNode = currentNode.prior; 101 point--; 102 } 103 node.prior = currentNode.prior; 104 currentNode.prior = node; 105 node.next = currentNode; 106 currentNode = node; 107 } 108 } 109 //如果头结点离插入位置更近 110 else{ 111 point = 0; 112 while(point<position-1){ 113 if(point == 0){ 114 currentNode = head.next; 115 } 116 else{ 117 currentNode = currentNode.next; 118 } 119 point++; 120 } 121 if(currentNode!=null){ 122 node.next = currentNode.next; 123 currentNode.next = node; 124 node.prior = currentNode; 125 currentNode = node; 126 } 127 else{ 128 head.next = node; 129 node.prior = head; 130 } 131 } 132 size++; 133 LinkedListLog.getInstance().insert(); 134 } 135 /** 136 * 删(从末尾删除) 137 */ 138 public void delete(){ 139 if(size == 0){ 140 LinkedListLog.getInstance().error(); 141 return; 142 } 143 while(point<size){ 144 currentNode = currentNode.next; 145 point++; 146 } 147 currentNode = currentNode.prior; 148 currentNode.next = null; 149 point--; 150 size--; 151 LinkedListLog.getInstance().delete(); 152 } 153 /** 154 * 删(任意位置删除) 155 */ 156 public void delete(int position){ 157 checkPosition(position); 158 if(size == 0){ 159 LinkedListLog.getInstance().error(); 160 return; 161 } 162 //如果指针离插入位置更近 163 if(Math.abs(position-point)<=position){ 164 if((position-point)>0){ 165 while(point<position-1){ 166 currentNode = currentNode.next; 167 point++; 168 } 169 try{ 170 currentNode.next = currentNode.next.next; 171 currentNode.next.next.prior = currentNode; 172 }catch(Exception e){ 173 /** 174 * 这里为了防止currentNode.next.next为空设定， 175 * 若以后发现currentNode.next.next为空的情况存在，这里在做一些措施 176 * 目前逻辑有点复杂，不想看了....等抛出再处理 177 */ 178 System.out.println("有参数为空！"); 179 } 180 } 181 else if((position-point)<=0){ 182 while(point>position){ 183 currentNode = currentNode.prior; 184 point--; 185 } 186 try{ 187 currentNode.next.prior = currentNode.prior.next; 188 currentNode.prior.next = currentNode.next.prior; 189 currentNode = currentNode.next; 190 }catch(Exception e){ 191 /** 192 * 理由同上 193 */ 194 System.out.println("有参数为空！"); 195 } 196 } 197 } 198 //如果头结点离插入位置更近 199 else{ 200 point = 0; 201 while(point<position-1){ 202 if(point == 0){ 203 currentNode = head.next; 204 } 205 else{ 206 currentNode = currentNode.next; 207 } 208 point++; 209 } 210 try{ 211 currentNode.next = currentNode.next.next; 212 currentNode.next.next.prior = currentNode; 213 }catch(Exception e){ 214 /** 215 * 理由如上 216 */ 217 System.out.println("参数为空！"); 218 } 219 } 220 size--; 221 LinkedListLog.getInstance().delete(); 222 } 223 /** 224 * 改 225 */ 226 public void update(Node node,int position){ 227 checkPosition(position); 228 if(size == 0){ 229 LinkedListLog.getInstance().error(); 230 return; 231 } 232 //如果指针离插入位置更近 233 if(Math.abs(position-point)<=position){ 234 if((position-point)>0){ 235 while(point<position-1){ 236 currentNode = currentNode.next; 237 point++; 238 } 239 node.next = currentNode.next.next; 240 node.prior = currentNode; 241 currentNode.next.next.prior = node; 242 currentNode.next = node; 243 } 244 else if((position-point)<=0){ 245 while(point>position){ 246 currentNode = currentNode.prior; 247 point--; 248 } 249 node.next = currentNode.next; 250 node.prior = currentNode.prior; 251 currentNode.next.prior = node; 252 currentNode.prior.next = node; 253 currentNode = node; 254 } 255 } 256 //如果头结点离插入位置更近 257 else{ 258 point = 0; 259 while(point<position-1){ 260 if(point == 0){ 261 currentNode = head.next; 262 } 263 else{ 264 currentNode = currentNode.next; 265 } 266 point++; 267 } 268 node.next = currentNode.next.next; 269 node.prior = currentNode; 270 currentNode.next.next.prior = node; 271 currentNode.next = node; 272 } 273 LinkedListLog.getInstance().update(); 274 } 275 /** 276 * 查 277 */ 278 public Node select(int position){ 279 checkPosition(position); 280 if(size == 0){ 281 LinkedListLog.getInstance().error(); 282 return null; 283 } 284 //如果指针离插入位置更近 285 if(Math.abs(position-point)<=position){ 286 if((position-point)>0){ 287 while(point<position-1){ 288 currentNode = currentNode.next; 289 point++; 290 } 291 LinkedListLog.getInstance().select(); 292 return currentNode.next; 293 } 294 else if((position-point)<=0){ 295 while(point>position){ 296 currentNode = currentNode.prior; 297 point--; 298 } 299 LinkedListLog.getInstance().select(); 300 return currentNode; 301 } 302 } 303 //如果头结点离插入位置更近 304 else{ 305 point = 0; 306 while(point<position-1){ 307 if(point == 0){ 308 currentNode = head.next; 309 } 310 else{ 311 currentNode = currentNode.next; 312 } 313 point++; 314 } 315 LinkedListLog.getInstance().select(); 316 return currentNode.next; 317 } 318 LinkedListLog.getInstance().error(); 319 return null; 320 } 321 /** 322 * 检查位置是否正确 323 */ 324 public void checkPosition(int position){ 325 if(position>size+1||position<=0){ 326 LinkedListLog.getInstance().error(); 327 return; 328 } 329 } 330 } 331 332 333 package com.voole.linkedlist; 334 /** 335 * @description 链表节点 336 * @author TMAC-J 337 * 338 */ 339 public class Node { 340 /** 341 * 定义下一个指针 342 */ 343 public Node next = null; 344 /** 345 * 定义上一个指针 346 */ 347 public Node prior = null; 348 /** 349 * 定义数据域 350 */ 351 public Data data = http://www.mamicode.com/null; 352 /** 353 * @description 构造方法 354 */ 355 public Node(Node prior,Node next,Data data){ 356 this.prior = prior; 357 this.next = next; 358 this.data =http://www.mamicode.com/ data; 359 } 360 } 361 362 363 package com.voole.linkedlist; 364 365 import java.io.Serializable; 366 367 public class Data implements Serializable{ 368 369 private static final long serialVersionUID = 1L; 370 371 } 372 373 374 375 package com.voole.linkedlist; 376 /** 377 * 单例日志类（饿汉） 378 * @author TMAC-J 379 * 380 */ 381 public class LinkedListLog { 382 private static final LinkedListLog instance = new LinkedListLog(); 383 384 private LinkedListLog(){} 385 386 public static LinkedListLog getInstance(){ 387 return instance; 388 } 389 390 public void insert(){ 391 System.out.println("插入成功！"); 392 } 393 394 public void delete(){ 395 System.out.println("删除成功！"); 396 } 397 398 public void update(){ 399 System.out.println("修改成功！"); 400 } 401 402 public void select(){ 403 System.out.println("查询成功！"); 404 } 405 406 public void error(){ 407 System.out.println("错误！"); 408 } 409 }
可能还会有一些小bug，以后碰到的时候再改吧，先写到这了。
java实现双链表（差点没写吐系列...）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。