上篇教程給大家分享了單鏈表的概念，以及如何用 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 = 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("[]");
}
}
}
雙向鏈表
雙向鏈表是相對單鏈表來講的，區別在于單鏈表中只有一個指針指向下一個節點，是單向連接的，只能從當前節點訪問它的后繼節點。而雙向鏈表顧名思義是雙向連接的，既可以從當前節點訪問到后繼節點，也可以訪問到前驅節點，所以在雙向鏈表中有兩個指針，一個叫做后繼指針，指向下一個節點，另一個叫做前驅指針，指向它的上一個節點，雙向鏈表的結構如下圖所示。
雙向鏈表相比于單鏈表會占用更多的內存空間，因為多了一個指針來存儲前驅節點的內存地址。雖然如此，但是在某些操作上，相比于單鏈表，雙向鏈表可以極大地提升效率。
比如要刪除鏈表中的某個節點，那么我們就需要獲取到目標節點的前驅節點，然后將前驅節點的指針指向目標節點的下一個節點，如下圖所示。
如上所示，刪除節點必須先找到其前驅節點，在單鏈表中是不會記錄元素的前驅節點的，所以必須從頭開始遍歷鏈表，直到找到目標節點的前驅節點，時間復雜度為 O(n)。
如果是雙向鏈表的結構，每一個節點都會記錄其前驅節點，可直接獲取，所以此時的時間復雜度為 O(1)。
搞清楚了雙向鏈表的概念，接下來我們用 Java 來實現雙向鏈表的結構。
package com.southwind.link;
public class DoubleNode {
//數據
public Object data;
//下一個節點
public DoubleNode next;
//上一個節點
public DoubleNode previous;
public DoubleNode(Object data){
this.data = data;
}
}
package com.southwind.link;
public class DoubleLinkedList {
public int size;
public DoubleNode head;
/**
* 添加元素
* @param obj
* @return
*/
public DoubleNode add(Object obj){
DoubleNode newNode = new DoubleNode(obj);
if(size == 0){
head = newNode;
}else{
DoubleNode target = head;
while(target.next!=null){
target = target.next;
}
target.next = newNode;
newNode.previous = target;
}
size++;
return newNode;
}
/**
* 在指定位置插入元素
* @return
*/
public DoubleNode insert(int index,Object obj){
if(index >= size){
return null;
}
DoubleNode newNode = new DoubleNode(obj);
if(index == 0){
newNode.next = head;
head.previous = newNode;
head = newNode;
}else{
DoubleNode target = head;
int pos = 0;
while(pos != index){
target = target.next;
pos++;
}
newNode.previous = target.previous;
newNode.previous.next = newNode;
newNode.next = target;
}
size++;
return newNode;
}
/**
* 刪除鏈表頭部元素
* @return
*/
public DoubleNode removeHead(){
if(size > 0){
DoubleNode node = head;
head = head.next;
size--;
return node;
}else{
return null;
}
}
/**
* 刪除指定位置元素
* @return
*/
public DoubleNode remove(int index){
if(index >= size){
return null;
}
DoubleNode result = head;
if(index == 0){
DoubleNode node = head;
head = head.next;
}else{
DoubleNode target = head;
int pos = 0;
while(pos != index){
target = target.next;
pos++;
}
target.previous.next = target.next;
}
size--;
return result;
}
/**
* 刪除指定元素
* @return
*/
public DoubleNode removeNode(Object obj){
DoubleNode target = head;
if(obj.equals(target.data)){
DoubleNode node = head;
head = head.next;
size--;
}else{
while(target.next!=null){
if(obj.equals(target.data)){
target.previous.next = target.next;
size--;
break;
}
target = target.next;
}
}
return target;
}
/**
* 返回指定元素
* @return
*/
public DoubleNode findNode(Object obj){
DoubleNode target = head;
while(target.next!=null){
if(obj.equals(target.data)){
return target;
}else{
target = target.next;
}
}
if(target.next==null && obj.equals(target.data)){
return target;
}
return null;
}
/**
* 輸出鏈表元素
*/
public void show(){
if(size > 0){
DoubleNode 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("[]");
}
}
}
