双向循环链表实战
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个位置添加元素Xpublic 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;// 如果插入位置是尾部，更新 tailif (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("@@@测试第四个任务成功"); //！！！需要printSystem.out.println();//返回第一次出现位置号System.out.println("&&&测试第五个任务:返回元素第一次出现的位置");System.out.println(TEXT.firstappear(1234)); //！！！需要printSystem.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();}
}
