你是怎么把生活弄的一團(tuán)糟的 . . .
正常發(fā)揮罷了
接一下有什么打算 . . .
熬 !
生活充滿希望
用這段話形容自己的近況，簡(jiǎn)直了?。?！好吧，接下來(lái)搞定循環(huán)鏈表?。?！
概述
本文主要針對(duì)數(shù)據(jù)結(jié)構(gòu)中的循環(huán)鏈表結(jié)構(gòu)(包括單向和雙向)進(jìn)行詳細(xì)的講解并用java實(shí)現(xiàn)了鏈表結(jié)構(gòu)上的增刪改查操作。關(guān)于單鏈表結(jié)構(gòu)可參看作者的上一篇文章：數(shù)據(jù)結(jié)構(gòu)(一)---線性表(Java實(shí)現(xiàn))
單向循環(huán)鏈表
基本概念
如果把單鏈表的最后一個(gè)節(jié)點(diǎn)的指針指向鏈表頭部，而不是指向NULL，那么就構(gòu)成了一個(gè)單向循環(huán)鏈表。
帶頭節(jié)點(diǎn)的循環(huán)單鏈表結(jié)構(gòu)示意圖
代碼實(shí)現(xiàn)(Java)
package com.datastruct.learn.list;
/**
* 循環(huán)單鏈表：表的最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)表形成一個(gè)環(huán)
*
* @author zengsk
* @date 2019/1/19
**/
public class CycleLinkedList {
class CycleNode {
Object data;
CycleNode next = null;
CycleNode() {
this.data = null;
}
CycleNode(Object data) {
this.data = data;
}
}
private CycleNode head, pos;
private int size;
//初始化時(shí),生成一個(gè)包含頭節(jié)點(diǎn)的空鏈表
CycleLinkedList() {
head = new CycleNode();
head.next = head;
pos = head;
this.size = 0;
}
/**
* 返回鏈表的大小
* @return
*/
public int len() {
return this.size;
}
/**
* 判斷鏈表是否為空
* @return
*/
public boolean isEmpty() {
return this.size == 0;
}
/**
* 添加元素，在末尾節(jié)點(diǎn)處添加
* @param data
*/
public void add(Object data) {
CycleNode _node = new CycleNode(data);
if (head.next == head) {
head.next = _node;
_node.next = head;
} else {
pos = head;
while (pos.next != head) {
pos = pos.next;
}
pos.next = _node;
_node.next = head;
}
size++;
}
/**
* 插入元素， 在指定索引位置處插入
* @param index
* @param data
*/
public void insert(int index, Object data) {
CycleNode _node = new CycleNode(data);
if (index < 0 || index > size - 1)
throw new RuntimeException("索引錯(cuò)誤" + index);
int i = 0;
pos = head;
while (pos.next != head && i < index) {
pos = pos.next;
i++;
}
_node.next = pos.next;
pos.next = _node;
size++;
}
/**
* 移除元素
* @param index
* @return
*/
public Object remove(int index) {
Object value = null;
if (index < 0 || index > size - 1)
throw new RuntimeException("索引錯(cuò)誤" + index);
int i = 0;
pos = head;
while (pos.next != head && i < index) {
pos = pos.next;
i++;
}
value = pos.next.data;
pos.next = pos.next.next;
size--;
return value;
}
/**
* 替換元素
* @param index
* @param newObj
* @return
*/
public Object replace(int index, Object newObj) {
Object value = null;
if (index < 0 || index > size - 1)
throw new RuntimeException("索引錯(cuò)誤" + index);
int i = 0;
pos = head;
while (pos.next != head && i < index) {
pos = pos.next;
i++;
}
value = pos.next.data;
pos.next.data = newObj;
return value;
}
/**
* 獲取元素
* @param index
* @return
*/
public Object get(int index) {
if (index < 0 || index > size - 1)
throw new RuntimeException("索引錯(cuò)誤" + index);
int i = 0;
pos = head;
while (pos.next != head && i < index) {
pos = pos.next;
i++;
}
return pos.next.data;
}
/**
* 查詢?cè)厮饕? * @param data
* @return
*/
public int indexOf(Object data) {
int i = 0;
pos = head;
while (pos.next != head) {
pos = pos.next;
if (pos.data.equals(data))
return i;
i++;
}
return -1;
}
/**
* 判斷是否包含指定元素
* @param data
* @return
*/
public boolean contains(Object data) {
int i = 0;
pos = head;
while (pos.next != head) {
pos = pos.next;
if (pos.data.equals(data))
return true;
}
return false;
}
/**
* 打印鏈表中的元素
*/
public void show() {
for (int i = 0; i < size; i++) {
System.out.print(this.get(i) + "-->");
}
}
}
雙向循環(huán)鏈表
基本概念
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始，都可以很方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表。
- 在雙向鏈表中，每個(gè)結(jié)點(diǎn)包括三個(gè)域，分別是data域、next域和prior域，其中data域?yàn)閿?shù)據(jù)元素域，next域?yàn)橹赶蚝罄^結(jié)點(diǎn)的對(duì)象引用，prior域?yàn)橹赶蚯膀?qū)結(jié)點(diǎn)的對(duì)象引用。
帶頭節(jié)點(diǎn)的雙向循環(huán)鏈表示意圖
代碼實(shí)現(xiàn)(Java)
package com.datastruct.learn.list;
/**
* 設(shè)計(jì)實(shí)現(xiàn)一個(gè)雙向鏈表結(jié)構(gòu)
*
* @author zengsk
* @date 2019/1/19
**/
public class DualLinkedList {
class DualNode {
private Object data;
private DualNode prior = null;
private DualNode next = null;
DualNode() {
this.data = null;
}
DualNode(Object data) {
this.data = data;
}
}
private DualNode head, rear; //頭尾指針
private int size;
/**
* 初始化一個(gè)空鏈表
*/
DualLinkedList() {
head = new DualNode();
head.next = head;
head.prior = head;
this.rear = head.prior;
this.size = 0;
}
/**
* 獲取鏈表長(zhǎng)度
*
* @return
*/
public int len() {
return this.size;
}
/**
* 判斷鏈表是否為空
*
* @return
*/
public boolean isEmpty() {
if (head.prior == head)
return true;
return false;
}
/**
* 添加結(jié)點(diǎn)到表尾
*
* @param data
*/
public void add(Object data) {
DualNode _node = new DualNode(data);
if (isEmpty()) { //鏈表為空情況
_node.prior = head;
_node.next = head;
head.next = _node;
head.prior = _node;
this.rear = _node;
} else {
_node.prior = this.rear;
_node.next = head;
this.rear.next = _node;
this.head.prior = _node;
this.rear = _node;
}
size++;
}
/**
* 在指定索引位置插入元素
*
* @param index
* @param data
*/
public void insert(int index, Object data) {
DualNode _node = new DualNode(data);
try {
if (index < 0 || index > size - 1)
throw new RuntimeException("索引錯(cuò)誤" + index);
if (head.prior == head) {
add(data);
} else {
int i = 0;
DualNode pos = head;
while (pos.next != rear && i < index) {
pos = pos.next;
i++;
}
_node.next = pos.next;
_node.prior = pos;
pos.next.prior = _node;
pos.next = _node;
size++;
}
} catch (RuntimeException e) {
e.printStackTrace();
}
}
/**
* 移除指定索引位置的元素
*
* @param index
* @return
*/
public Object remove(int index) {
Object data = null;
if (index < 0 || index > size - 1)
throw new RuntimeException("索引錯(cuò)誤" + index);
if (head.prior == head)
throw new RuntimeException("鏈表為空!!");
DualNode pos = head;
int i = 0;
while (pos.next != rear && i < index) {
pos = pos.next;
i++;
}
data = pos.next.data;
pos.next.next.prior = pos;
pos.next = pos.next.next;
size--;
return data;
}
/**
* 獲取指定索引位置的元素
*
* @param index
* @return
*/
public Object get(int index) {
if (index < 0 || index > size - 1)
throw new RuntimeException("索引錯(cuò)誤！！" + index);
if (head.prior == head) {
throw new RuntimeException("鏈表為空");
}
DualNode pos = head;
int i = 0;
while (pos.next != rear && i < index) {
pos = pos.next;
i++;
}
Object obj = pos.next.data;
return obj;
}
/**
* @param data
* @return
*/
public boolean contains(Object data) {
DualNode pos = head;
while (pos.next != rear) {
pos = pos.next;
if (pos.data.equals(data)) {
return true;
}
}
return false;
}
/**
* 獲取指定元素所在的索引
*
* @param data
* @return
*/
public int indexOf(Object data) {
DualNode pos = head;
int i = 0;
while (pos.next != rear) {
pos = pos.next;
if (pos.data.equals(data)) {
return i;
}
i++;
}
return -1;
}
/**
* 打印鏈表的所有元素
*/
public void show() {
for (int i = 0; i < size; i++) {
System.out.print(this.get(i) + "-->");
}
}
}
