一、單向循環(huán)鏈表：

1、概念：

單向循環(huán)鏈表是單鏈表的另一種形式，其結(jié)構(gòu)特點是鏈表中最后一個結(jié)點的指針不再是結(jié)束標記，而是指向整個鏈表的第一個結(jié)點，從而使單鏈表形成一個環(huán)。

和單鏈表相比，循環(huán)單鏈表的長處是從鏈尾到鏈頭比較方便。當要處理的數(shù)據(jù)元素序列具有環(huán)型結(jié)構(gòu)特點時，適合于采用循環(huán)單鏈表。

和單鏈表相同，循環(huán)單鏈表也有帶頭結(jié)點結(jié)構(gòu)和不帶頭結(jié)點結(jié)構(gòu)兩種，帶頭結(jié)點的循環(huán)單鏈表實現(xiàn)插入和刪除操作時，算法實現(xiàn)較為方便。

帶頭結(jié)點的循環(huán)單鏈表的操作實現(xiàn)方法和帶頭結(jié)點的單鏈表的操作實現(xiàn)方法類同，差別僅在于：

（1）在構(gòu)造函數(shù)中，要加一條head.next = head 語句，把初始時的帶頭結(jié)點的循環(huán)單鏈表設(shè)計成上圖中（a）所示的狀態(tài)。

（2）在index(i)成員函數(shù)中，把循環(huán)結(jié)束判斷條件current != null改為current != head。

2、單鏈表的代碼實現(xiàn)：

1、結(jié)點類Node的實現(xiàn)代碼

public class Node { public Object data;//保存當前結(jié)點的數(shù)據(jù) public Node next;//指向下一個結(jié)點 public Node(Object data){ this.data = data; } }

2、循環(huán)鏈表類CircleList的實現(xiàn)代碼

public class CircleList { private Node head; public CircleList(){ head = new Node(0); head.next = null; } //在指定位置插入結(jié)點 public boolean insert(Object data,int pos){ boolean ret = (head != null) && (data != null) && (pos >= 0); if(ret){ Node node = new Node(data); if(head.next == null){ //插入的結(jié)點前，循環(huán)鏈表中沒有結(jié)點。 head.next = node; node.next = node; }else{ if(pos >= (Integer)head.data){ pos = (Integer)head.data; } Node currentNode = head.next; //若currentNode.next == head.next，就說明currentNode是最后一個結(jié)點 for(int i = 0;(i < pos) && (currentNode.next != head.next);i++){ currentNode = currentNode.next; } node.next = currentNode.next; currentNode.next = node; //插入位置的下標為0時 if(pos == 0){ head.next = node; } } head.data = (Integer)head.data + 1; } return ret; } //獲取鏈表中下標為pos的結(jié)點 public Object get(int pos){ Object ret = null; if(head != null && pos >= 0 && pos < (Integer)head.data){ Node node = head;//頭結(jié)點 //找到要刪除的結(jié)點 for(int i = 0;i<=pos;i++){ node = node.next; } if(node != null){ ret = node.data; } } return ret; } //刪除鏈表中下標為pos的結(jié)點 public Object delete(int pos){ Object ret = null; if(head != null && pos >= 0 && pos < (Integer)head.data){ Node node = head;//頭結(jié)點 Node currentNode = null;//要刪除的結(jié)點 //找到要刪除結(jié)點的前一個結(jié)點 for(int i = 0;i<pos;i++){ node = node.next; } currentNode = node.next; //獲取要刪除結(jié)點的數(shù)據(jù) if(currentNode != null){ ret = currentNode.data; } //要刪除的結(jié)點是循環(huán)鏈表中的第一個結(jié)點 if(head.next == currentNode){ head.next = currentNode.next; } //刪除結(jié)點 node.next = currentNode.next; head.data = (Integer)head.data - 1; } return ret; } //清空鏈表 public void clear(){ if(head != null){ head.data = 0; head.next = null; } } //注銷鏈表 public void destroy(){ if(head != null){ head = null; } } //獲取鏈表中結(jié)點的個數(shù) public int length(){ int ret = -1; if(head != null){ ret = (Integer)head.data; } return ret; } //打印循環(huán)鏈表中的數(shù)據(jù) public void display(){ if(head != null){ Node node = head; for(int i = 0;i < (Integer)head.data;i++){ node = node.next; System.out.print(node.data+" "); } } } }

3、測試類Test的代碼

public class Test { public static void main(String[] args) { CircleList list = new CircleList(); list.insert("結(jié)點1", 0); list.insert("結(jié)點2", 1); list.insert("結(jié)點3", 2); list.insert("結(jié)點4", 3); list.insert("結(jié)點5", 4); list.insert("結(jié)點6", 5); System.out.println("鏈表中的元素為："); list.display(); System.out.println("\n鏈表中結(jié)點的個數(shù)："+list.length()); System.out.println("\n獲取鏈表中下標為2的結(jié)點："+list.get(2)); System.out.println("刪除鏈表中下標為0的結(jié)點："+list.delete(0)); System.out.println("鏈表中的元素為："); list.display(); System.out.println("\n鏈表中結(jié)點的個數(shù)："+list.length()); list.clear(); list.destroy(); } }

4、程序運行結(jié)果

鏈表中的元素為：
結(jié)點1 結(jié)點2 結(jié)點3 結(jié)點4 結(jié)點5 結(jié)點6
鏈表中結(jié)點的個數(shù)：6
獲取鏈表中下標為2的結(jié)點：結(jié)點3
刪除鏈表中下標為0的結(jié)點：結(jié)點1
鏈表中的元素為：
結(jié)點2 結(jié)點3 結(jié)點4 結(jié)點5 結(jié)點6
鏈表中結(jié)點的個數(shù)：5

二、雙向循環(huán)鏈表：

雙向鏈表：

雙向鏈表是每個結(jié)點除后繼指針外還有一個前驅(qū)指針。和單鏈表類同，雙向鏈表也有帶頭結(jié)點結(jié)構(gòu)和不帶頭結(jié)點結(jié)構(gòu)兩種，帶頭結(jié)點的雙向鏈表更為常用；另外，雙向鏈表也可以有循環(huán)和非循環(huán)兩種結(jié)構(gòu)，循環(huán)結(jié)構(gòu)的雙向鏈表更為常用。

雙向循環(huán)鏈表：

在雙向鏈表中，每個結(jié)點包括三個域，分別是element域、next域和prior域，其中element域為數(shù)據(jù)元素域，next域為指向后繼結(jié)點的對象引用，prior域為指向前驅(qū)結(jié)點的對象引用。下圖為雙向鏈表結(jié)點的圖示結(jié)構(gòu)：

如下圖是帶頭結(jié)點的雙向循環(huán)鏈表的圖示結(jié)構(gòu)。雙向循環(huán)鏈表的next和prior各自構(gòu)成自己的單向循環(huán)鏈表：

在雙向鏈表中，有如下關(guān)系：設(shè)對象引用p表示雙向鏈表中的第i個結(jié)點，則p.next表示第i+1個結(jié)點，p.next.prior仍表示第i個結(jié)點，即p.next.prior == p；同樣地，p.prior表示第i-1個結(jié)點，p.prior.next仍表示第i個結(jié)點，即p.prior.next == p。下圖是雙向鏈表上述關(guān)系的圖示：

雙向循環(huán)鏈表的插入過程：

下圖中的指針p表示要插入結(jié)點的位置，s表示要插入的結(jié)點，①、②、③、④表示實現(xiàn)插入過程的步驟：

循環(huán)雙向鏈表的刪除過程：

下圖中的指針p表示要插入結(jié)點的位置，①、②表示實現(xiàn)刪除過程的步驟：

2、雙向循環(huán)鏈表的代碼實現(xiàn)

public class DbLinkedList<T> { //定義內(nèi)部類，用作鏈表的節(jié)點 private class Node<T> { Node<T> pre; //指向前一個節(jié)點 Node<T> next; //指向后一個節(jié)點 T value; //當前節(jié)點的值 public Node(T value, Node<T> next, Node<T> pre) { this.value = value; this.next = next; this.pre = pre; } public String toString() { return this.value + ""; } } private Node<T> header; //定義頭節(jié)點 private int size; //定義鏈表的長度 public DbLinkedList() { header = new Node<T>(null, null, null);//空的頭節(jié)點，用來區(qū)分雙向循環(huán)鏈表的首尾 header.pre = header.next = header; //雙向循環(huán)鏈表，首尾相連 size = 0; } public DbLinkedList(Collection<? extends T> collection) { this(); addAll(this.size, collection); } public boolean add(T value)//在鏈表的尾巴上面加一個節(jié)點, 相當于在header節(jié)點前面加一個節(jié)點 { return add(header, value); } public boolean add(int index, T value)//指定index處加入節(jié)點 { return add(entry(index), value); } public boolean remove(Object obj)//刪除指定value的節(jié)點 { Node<T> node; //1. 從header.next往后遍歷，再到header時結(jié)束 for(node = header.next; node!=header; node=node.next) { if(node.value == obj || (obj!=null && obj.equals(node.value))) { remove(node); return true; } } //2.java.util.LinkedList實現(xiàn)，先區(qū)分null再遍歷，個人感覺效率差不多呀，希望有人賜教 /* if(obj==null) { for(node = header.next; node!=header; node=node.next) { if(node.value == null) { remove(node); return true; } } } else { for(node = header.next; node!=header; node=node.next) { if(node.value == obj || obj.equals(node.value)) { remove(node); return true; } } } */ return false; } public T remove(int index)//刪除指定index節(jié)點 { return remove(entry(index)); } public boolean addAll(Collection<? extends T> collection) { return addAll(this.size, collection); } //在指定index位置添加collection里的所有元素 public boolean addAll(int index, Collection<? extends T> collection) { if(collection==null || collection.size()==0) { return false; } //獲取指定位置節(jié)點，如果index==size，則在末尾添加節(jié)點，即header節(jié)點之前 //當index==size時，調(diào)用entry方法會拋異常，所以三則表達式很有必要 Node<T> node = index == this.size ? this.header : entry(index); Object[] objArray = collection.toArray(); int len = objArray.length; Node<T> preNode = node.pre; for(int i=0; i<len; i++) { //新建一個節(jié)點，新節(jié)點的next指向node，新節(jié)點的pre指向node的pre //完成指向過程node.pre←newNode→node //當?shù)诙蔚鷷r，preNode=newNode1(i=1創(chuàng)建的newNode), newNode1←newNode2(i=2創(chuàng)建的newNode)→node Node<T> newNode = new Node<T>((T) objArray[i], node, preNode); //維持雙向鏈表的指向，將node的pre節(jié)點的next指向新節(jié)點,完成指向過程node.pre→newNode //當?shù)诙蔚鷷r，newNode1→newNode2 preNode.next = newNode; //將preNode指向newNode，當?shù)诙蔚鷷r，preNode往后移動一位 preNode = newNode; } //迭代完成后，node的前一個節(jié)點指向preNode（即最后一次創(chuàng)建的newNode），preNode←node //如果len=2,完成的鏈就變成這樣preNode→←newNode1→←newNode2→←node node.pre = preNode; //長度加len this.size += len; return true; } private T remove(Node<T> node) { //node的前一個節(jié)點next指向node的下一個節(jié)點 //node的下一個節(jié)點pre指向node的前一個節(jié)點 //A→node←B改成A→←B node.pre.next = node.next; node.next.pre = node.pre; //node的前后指向null //A←node→B改成null←node→null node.pre = node.next = null; T value = node.value; node.value = null; this.size--; return value; } public T get(int index) { return entry(index).value; } private Node<T> entry(int index) //迭代至index處的節(jié)點 { rangeIndex(index); //判斷index是否越界 Node<T> node = this.header; //判斷index是否小于size的一半，如果小于就從header往后開始迭代，否則就從header往前開始迭代，提高效率 //例如有一個鏈表header→A→B→C→D→header if(index < (this.size>>1)) { //因為header是空的頭節(jié)點，所以i要小于等于index //例如index=1， 小于size的一半2 //i=0時，node=A //i=1時，node=B，然后跳出循環(huán) for(int i=0; i<=index; i++) { node = node.next; } } else { //例如index=2，不小size的一半 //i=3, node等于header的前一個， node=D //i=2, node=C，然后跳出循環(huán) for(int i=this.size-1; i>=index; i--) { node = node.pre; } } return node; } private void rangeIndex(int index) { if(index < 0 || index >= this.size) { throw new IndexOutOfBoundsException("index錯誤"); } } private boolean add(Node<T> node, T value) { //新建一個節(jié)點，新節(jié)點的next指向node，新節(jié)點的pre指向node的pre //完成指向過程node.pre←newNode→node Node<T> newNode = new Node<T>(value, node, node.pre); //維持雙向鏈表的指向，將node的pre節(jié)點的next指向新節(jié)點,完成指向過程node.pre→newNode node.pre.next = newNode; //node節(jié)點的前一個節(jié)點指向新節(jié)點，完成指向過程newNode←node node.pre = newNode; //上面兩行代碼不能顛倒，否則node的前一個節(jié)點會被覆蓋成新節(jié)點，會丟失node原來的前一個節(jié)點的next指向 //上述代碼完成了在node節(jié)點和node前一個節(jié)點之間加入一個新節(jié)點，并維護了雙向關(guān)系 this.size++; return true; } public void clear() { Node<T> node = header.next; //將每一個節(jié)點的雙向指向都清空，這樣每個節(jié)點都沒有被引用，可以方便垃圾回收器回收內(nèi)存 while(node != header) { //將node的下一個節(jié)點臨時保存起來 Node<T> tempNode = node.next; //將node的下一個節(jié)點和上一個節(jié)點置空 node.next = node.pre = null; //將node的值也置空 node.value = null; //將node移動到下一個節(jié)點 node = tempNode; } //清空header的雙向指向null this.header.next = this.header.pre = this.header; this.size = 0; } public boolean isEmpty() { return this.size == 0; } public int size() { return this.size; } }

三、仿真鏈表：

在鏈式存儲結(jié)構(gòu)中，我們實現(xiàn)數(shù)據(jù)元素之間的次序關(guān)系依靠指針。我們也可以用數(shù)組來構(gòu)造仿真鏈表。方法是在數(shù)組中增加一個（或兩個）int類型的變量域，這些變量用來表示后一個（或前一個）數(shù)據(jù)元素在數(shù)組中的下標。我們把這些int類型變量構(gòu)造的指針稱為仿真指針。這樣，就可以用仿真指針構(gòu)造仿真的單鏈表（或仿真的雙向鏈表）。

參考資料

• https://blog.csdn.net/tu451953337/article/details/36673671
• https://blog.csdn.net/basycia/article/details/51839431
• https://blog.csdn.net/dianzigaoshou/article/details/74546451

總結(jié)

以上是生活随笔為你收集整理的数据结构-单向循环链表、双向循环链表、仿真链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。