数据结构Java实现：循环链表和双向链表 _数据结构

文章插图

上篇教程给大家分享了单链表的概念，以及如何用 JAVA 实现一个单链表的结构。单链表是最基础的一种链表结构，在实际开发中的使用有一些局限性，比如只能单向往后查找节点，如果需要找到某元素的前驱节点，单链表是无法实现的，今天来给大家分享另外两个复杂一些的链表结构：循环链表和双向链表。
循环链表
循环链表本质上就是一种单链表，两者的不同之处在于链表中最后一个节点的指针指向哪里，在单链表中，末尾节点的指针指向空，如下图所示。

文章插图

第一个元素 a 的指针指向 1008，即第二个元素 b 的首地址，b 的指针指向第三个元素 c 的内存地址 1020，没有第四个元素，所以 c 的指针指向空。
而在循环链表中，末尾节点的指针指向首节点，形成一个闭环，所以它叫循环链表，应该很好理解，如下图所示。

文章插图

接下来用 Java 实现一个循环链表的结构，只需要在原有单链表的基础上稍作修改即可，如下所示。
package com.southwind.link;public class Node { //数据 public Object data; //下一个节点 public Node next; public Node(Object data){ this.data = https://www.isolves.com/it/cxkf/yy/JAVA/2019-07-08/data; }}package com.southwind.link;public class LoopLinkedList { public int size; public Node head; /** * 添加元素 * @param obj * @return */ public Node add(Object obj){ Node newNode = new Node(obj); if(size == 0){ head = newNode; head.next = head; }else{ Node target = head; while(target.next!=head){ target = target.next; } target.next = newNode; newNode.next = head; } size++; return newNode; } /** * 在指定位置插入元素 * @return */ public Node insert(int index,Object obj){ if(index >= size){ return null; } Node newNode = new Node(obj); if(index == 0){ newNode.next = head; head = newNode; }else{ Node target = head; Node previous = head; int pos = 0; while(pos != index){ previous = target; target = target.next; pos++; } previous.next = newNode; newNode.next = target; } size++; return newNode; } /** * 删除链表头部元素 * @return */ public Node removeHead(){ if(size > 0){ Node node = head; Node target = head; while(target.next!=head){ target = target.next; } head = head.next; target.next = head; size--; return node; }else{ return null; } } /** * 删除指定位置元素 * @return */ public Node remove(int index){ if(index >= size){ return null; } Node result = head; if(index == 0){ head = head.next; }else{ Node target = head; Node previous = head; int pos = 0; while(pos != index){ previous = target; target = target.next; pos++; } previous.next = target.next; result = target; } size--; return result; } /** * 删除指定元素 * @return */ public Node removeNode(Object obj){ Node target = head; Node previoust = head; if(obj.equals(target.data)){ head = head.next; size--; }else{ while(target.next!=null){ if(obj.equals(target.next.data)){ previoust = target; target = target.next; size--; break; }else{ target = target.next; previoust = previoust.next; } } previoust.next = target.next; } return target; } /** * 返回指定元素 * @return */ public Node findNode(Object obj){ Node target = head; while(target.next!=null){ if(obj.equals(target.data)){ return target; }else{ target = target.next; } } return null; } /** * 输出链表元素 */ public void show(){ if(size > 0){ Node node = head; int length = size; System.out.print("["); while(length > 0){ if(length == 1){ System.out.print(node.data); }else{ System.out.print(node.data+","); } node = node.next; length--; } System.out.println("]"); }else{ System.out.println("[]"); } }}双向链表
双向链表是相对单链表来讲的，区别在于单链表中只有一个指针指向下一个节点，是单向连接的，只能从当前节点访问它的后继节点。而双向链表顾名思义是双向连接的，既可以从当前节点访问到后继节点，也可以访问到前驱节点，所以在双向链表中有两个指针，一个叫做后继指针，指向下一个节点，另一个叫做前驱指针，指向它的上一个节点，双向链表的结构如下图所示。