你是怎么把生活弄的一团糟的 . . .
正常发挥罢了
接一下有什么打算 . . .
熬 !
生活充满希望
用这段话形容自己的近况，简直了！！！好吧，接下来搞定循环链表！！！
概述
本文主要针对数据结构中的循环链表结构(包括单向和双向)进行详细的讲解并用java实现了链表结构上的增删改查操作。关于单链表结构可参看作者的上一篇文章：数据结构(一)---线性表(Java实现)
单向循环链表
基本概念
如果把单链表的最后一个节点的指针指向链表头部，而不是指向NULL，那么就构成了一个单向循环链表。
带头节点的循环单链表结构示意图
代码实现(Java)
package com.datastruct.learn.list;
/**
* 循环单链表：表的最后一个结点的指针域指向头结点，整个表形成一个环
*
* @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;
//初始化时,生成一个包含头节点的空链表
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;
}
/**
* 添加元素，在末尾节点处添加
* @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("索引错误" + 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("索引错误" + 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("索引错误" + 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("索引错误" + index);
int i = 0;
pos = head;
while (pos.next != head && i < index) {
pos = pos.next;
i++;
}
return pos.next.data;
}
/**
* 查询元素索引
* @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) + "-->");
}
}
}
双向循环链表
基本概念
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
- 在双向链表中，每个结点包括三个域，分别是data域、next域和prior域，其中data域为数据元素域，next域为指向后继结点的对象引用，prior域为指向前驱结点的对象引用。
带头节点的双向循环链表示意图
代码实现(Java)
package com.datastruct.learn.list;
/**
* 设计实现一个双向链表结构
*
* @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;
/**
* 初始化一个空链表
*/
DualLinkedList() {
head = new DualNode();
head.next = head;
head.prior = head;
this.rear = head.prior;
this.size = 0;
}
/**
* 获取链表长度
*
* @return
*/
public int len() {
return this.size;
}
/**
* 判断链表是否为空
*
* @return
*/
public boolean isEmpty() {
if (head.prior == head)
return true;
return false;
}
/**
* 添加结点到表尾
*
* @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("索引错误" + 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("索引错误" + 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("索引错误！！" + 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) + "-->");
}
}
}
