双向循环链表实战
package XHLB;
public class SXXHLB {
// 定义双向链表节点
static class DoubleListNode { //Node(节点)
private int val;
private DoubleListNode prev;
private DoubleListNode next;
public DoubleListNode(int val) {
this.val = val;
this.next = null;
this.prev = null;
}
}
// 封装函数
static class SXLB {
private DoubleListNode head;
private DoubleListNode tail;
// 构造函数，初始化空链表
public SXLB() {
this.head = null;
this.tail = null;
}
// 判断链表是否为空
public boolean isEmpty() {
return this.head == null;
}
//在第i个位置添加元素X
public void append(int i, int val) {
DoubleListNode newNode = new DoubleListNode(val);
// 如果链表为空，头节点尾节点都是我，并且将前指针域和后指针域都指向我
if (this.head == null) {
this.head = newNode;
this.tail = newNode;
newNode.next = newNode;
newNode.prev = newNode;
return;
}
// 如果 i == 0，表示在头部插入
//第一步:先处理循环链表(2)
//第二步:再处理原来的头节点
//第三步:更新头节点
if (i == 0) {
newNode.next = this.head;
newNode.prev = this.tail;
this.head.prev = newNode;
this.tail.next = newNode;
this.head = newNode;
return;
}
// 遍历链表，找到第 i-1 个节点
DoubleListNode current = this.head;
int count = 0;
while (count < i - 1 && current.next != this.head) {
current = current.next;
count++;
}
// 如果 i 超出链表长度，插入到链表尾部
if (count < i - 1) {
newNode.prev = this.tail;
newNode.next = this.head;
this.tail.next = newNode;
this.head.prev = newNode;
this.tail = newNode;
return;
}
// 在第 i-1 个节点和第 i 个节点之间插入新节点
//第一步:先将元素插入(2)
//第二步:处理附近元素
newNode.prev = current;
newNode.next = current.next;
current.next.prev = newNode;
current.next = newNode;
// 如果插入位置是尾部，更新 tail
if (newNode.next == this.head) {
this.tail = newNode;
}
}
// 从前往后遍历（双向循环链表）
public void qianprint() {
if (this.head == null) {
return; // 空链表
}
DoubleListNode current = this.head;
do {
System.out.print(current.val + "\t");
current = current.next;
} while (current != this.head); // 循环直到回到头节点
System.out.println();
}
// 从后往前遍历（双向循环链表）
public void hoprint() {
if (this.tail == null) {
return; // 空链表
}
DoubleListNode current = this.tail;
do {
System.out.print(current.val + "\t");
current = current.prev;
} while (current != this.tail); // 循环直到回到尾节点
System.out.println();
}
// 删除节点（双向循环链表）
public void delete(int i) {
if (this.head == null) {
return; // 空链表
}
DoubleListNode current = this.head;
int count = 0;
// 遍历链表，找到第 i 个节点
while (count < i && current.next != this.head) {
current = current.next;
count++;
}
// 如果 i 超出链表长度，直接返回
if (count < i) {
return;
}
// 如果链表只有一个节点
if (current == this.head && current == this.tail) {
this.head = null;
this.tail = null;
return;
}
// 如果删除的是头节点
if (current == this.head) {
this.head = current.next;
this.head.prev = this.tail;
this.tail.next = this.head;
}
// 如果删除的是尾节点
else if (current == this.tail) {
this.tail = current.prev;
this.tail.next = this.head;
this.head.prev = this.tail;
}
// 如果删除的是中间节点
else {
current.prev.next = current.next;
current.next.prev = current.prev;
}
}
// 取第 i 个位置上的元素（双向循环链表）
public int getElement(int index) {
if (this.head == null) {
throw new IndexOutOfBoundsException("Index out of range");
}
DoubleListNode current = this.head;
int count = 0;
do {
if (count == index) {
return current.val;
}
count++;
current = current.next;
} while (current != this.head); // 循环直到回到头节点
throw new IndexOutOfBoundsException("Index out of range");
}
// 返回元素 x 第一次出现在双向循环链表中的位置号
public int firstappear(int x) {
if (this.head == null) {
return -1; // 空链表
}
DoubleListNode current = this.head;
int index = 0;
do {
if (current.val == x) {
return index;
}
index++;
current = current.next;
} while (current != this.head); // 循环直到回到头节点
return -1; // 没有找到
}
// 求双向循环链表的长度，即元素个数
public int getLength() {
if (this.head == null) {
return 0; // 空链表
}
DoubleListNode current = this.head;
int count = 0;
do {
count++;
current = current.next;
} while (current != this.head); // 循环直到回到头节点
return count;
}
}
// 测试集
public static void main(String[] args) {
SXLB TEXT = new SXLB();
//测试空表
System.out.println("***测试第一个任务:建立一个空表");
System.out.println("链表是否为空: " + TEXT.isEmpty());
TEXT.append(0,0);
System.out.println("链表是否为空: " + TEXT.isEmpty());
System.out.println("***测试第一个任务完成");
System.out.println();
//测试在第i个位置插入X元素
System.out.println("###测试第二个任务和第七个任务:在第i个位置插入元素X 输出所有值");
TEXT.append(1,1);
TEXT.append(2,12);
TEXT.append(3,123);
TEXT.append(4,1234);
TEXT.append(5,12345);
TEXT.append(6,123456);
System.out.println("****顺序输出（双向循环链表）*****");
TEXT.qianprint();
System.out.println("###测试第二个任务和第七个任务成功");
System.out.println();
// 测试删除节点
System.out.println("$$$测试第三个任务:删除第i个位置的元素");
System.out.println("$$$测试第三个任务:删除第3个位置的元素");
// 测试删除节点
TEXT.delete(3);
TEXT.qianprint();
System.out.println("$$$测试第三个任务成功:删除第3个位置的元素");
System.out.println();
//测试取元素
System.out.println("@@@测试第四个任务:取第i个位置的元素");
System.out.println("@@@测试第四个任务:取第3个位置的元素");
System.out.println(TEXT.getElement(3));
System.out.println("@@@测试第四个任务成功"); //！！！需要print
System.out.println();
//返回第一次出现位置号
System.out.println("&&&测试第五个任务:返回元素第一次出现的位置");
System.out.println(TEXT.firstappear(1234)); //！！！需要print
System.out.println("&&&测试第五个任务成功");
System.out.println();
//测试求链表长度
System.out.println("===测试第六个任务:返回元素第一次出现的位置");
TEXT.qianprint();
System.out.println(TEXT.getLength());
System.out.println("===测试第六个任务成功");
System.out.println();
// 测试从后往前输出
System.out.println("---测试第八个任务:返回元素第一次出现的位置");
TEXT.hoprint();
System.out.println("---测试第八个任务成功");
System.out.println();
}
}
