双向循环链表以及十字链表等

public void addLast(int data) {        ListNode added = new ListNode(data);        added.prev = head.prev;        added.next = head;        head.prev.next = added;        head.prev = added;    }

5. 删除首元结点

既然要在双向链表中删除首元结点，就需要先找到首元结点的直接后继，断开首元结点直接后继的前驱指针与首元结点的链接，除此之外，还需要断开哨兵结点后继指针与首元结点的链接。

public void removeLast() {        if (head.prev == head)            throw new IllegalArgumentException("空链表不允许删除");        ListNode lastNode = head.prev;        ListNode prev = head.prev.prev;        lastNode.prev = null;        lastNode.next = null;        prev.next = head;        head.prev = prev;    }

7. 查找指定结点

此方法是一个私有化的工具方法。

定义双向循环链表

双向循环链表（Bidirectional Circular Linked List）结合了双向链表与循环链表二者的特点，故我们可以从两个方面理解。双向循环链表以及十字链表等。此类有三个属性——、

对应到代码，如下。

• 双向：双向循环链表中的每个结点都有两个指针域，我们称为前驱指针域 与后继指针域 ，前驱指针域用于存储此结点的直接前驱在内存中的地址，后继指针域用于存储此结点的直接后继在内存中的地址，换句话说，就是  指向直接前驱， 指向直接后继；
• 循环：需要提前指出的是，为了避免对链表头部进行额外操作，本文实现的双向循环链表是带哨兵结点的。

  

  实现双向循环链表

  我们定义一个名为  的类来实现带哨兵结点的双向循环链表及其基本操作。

所以双向循环链表的结点结构示意图可以如下表示，此示意图并没有体现循环，我们将在初始化时展示循环的特点。

private static class ListNode {        ListNode prev;        int data;        ListNode next;        public ListNode(int data) {            this.data = data;        }        public ListNode(ListNode prev, int data, ListNode next) {            this.prev = prev;            this.data = data;            this.next = next;        }    }

2. 初始化操作

由于实现的是带哨兵结点的双向循环链表，所以我们先定义一个头指针  指向哨兵结点，由于此时链表为空，即链表中只有哨兵结点而没有真正存储元素的结点，于是让哨兵结点的后继指针及前驱指针都指向自身。

此时，已经将结点成功插入到了尾部，对应到代码，如下。当前结点的直接前驱及直接后继。

同样的，我们发现新的尾结点和原先的尾结点的后继指针都指向了哨兵结点，同时原先尾结点的前驱指针还指向新的尾结点，为了断干净关系，我们需要将这两个指针置空。

public void removeByValue(int data) {        ListNode removed = findByValue(data);        if (removed == null)            throw new RuntimeException(String.format("在链表中没有找到与数据[%d]相同的结点数据域%n",data));        ListNode previousNode = removed.prev;        ListNode nextNode = removed.next;        removed.prev = null;        removed.next = null;        previousNode.next = nextNode;        nextNode.prev = previousNode;    }

9. 遍历链表

我们上面提到，与单链表不同的是，遍历的循环终止条件不同，这里直接给出对应的实现代码：

public void traverse() {        ListNode indexNode = head.next;        while (indexNode != head) {            System.out.print(indexNode.data + " ");            indexNode = indexNode.next;        }        System.out.println();    }

final. 完整实现代码 & 单元测试

Java实现

import java.util.Iterator;/**<h3>双向循环链表</h3> * @Author Arrebol * @Date 2025/1/18 15:50 * @Project datastructure_algorithm * @Description： */public class BidirectionalCircularLinkedListSentinel implements Iterable<Integer>{    private static class ListNode {        ListNode prev;        int data;        ListNode next;        public ListNode(int data) {            this.data = data;        }        public ListNode(ListNode prev, int data, ListNode next) {            this.prev = prev;            this.data = data;            this.next = next;        }    }    private final int SENTINEL_VALUE = 666;    private ListNode head = new ListNode(null, SENTINEL_VALUE, null);    public BidirectionalCircularLinkedListSentinel() {        head.prev = head;        head.next = head;    }    public void addFirst(int data) {        ListNode added = new ListNode(data);        added.prev = head;        added.next = head.next;        head.next.prev = added;        head.next = added;    }    public void addLast(int data) {        ListNode added = new ListNode(data);        added.prev = head.prev;        added.next = head;        head.prev.next = added;        head.prev = added;    }    public void removeFirst() {        if (head.next == head)            throw new IllegalArgumentException("空链表不允许删除");        ListNode secondNode = head.next.next;        head.next.next = null;        head.next.prev = null;        secondNode.prev = head;        head.next = secondNode;    }    public void removeLast() {        if (head.prev == head)            throw new IllegalArgumentException("空链表不允许删除");        ListNode lastNode = head.prev;        ListNode prev = head.prev.prev;        lastNode.prev = null;        lastNode.next = null;        prev.next = head;        head.prev = prev;    }    public void removeByValue(int data) {        ListNode removed = findByValue(data);        if (removed == null)            throw new RuntimeException(String.format("在链表中没有找到与数据[%d]相同的结点数据域%n",data));        ListNode previousNode = removed.prev;        ListNode nextNode = removed.next;        removed.prev = null;        removed.next = null;        previousNode.next = nextNode;        nextNode.prev = previousNode;    }    private ListNode findByValue(int data) {        ListNode indexNode = head.next;        while (indexNode != head) {            if (indexNode.data == data)                return indexNode;            indexNode = indexNode.next;        }        return null;    }    public void traverse() {        ListNode indexNode = head.next;        while (indexNode != head) {            System.out.print(indexNode.data + " ");            indexNode = indexNode.next;        }        System.out.println();    }    @Override    public Iterator<Integer> iterator() {        return new Iterator<>() {            ListNode indexNode = head.next;            @Override            public boolean hasNext() {                return indexNode != head;            }            @Override            public Integer next() {                int data =indexNode.data;                indexNode = indexNode.next;                return data;            }        };    }}

import com.uchain.mkj.data_structure.linkedlist.BidirectionalCircularLinkedListSentinel;import org.junit.jupiter.api.BeforeEach;import org.junit.jupiter.api.Test;import java.util.List;import static org.junit.jupiter.api.Assertions.*;class BidirectionalCircularLinkedListSentinelTest {    private BidirectionalCircularLinkedListSentinel list;    @BeforeEach    void setUp() {        list = new BidirectionalCircularLinkedListSentinel();    }    @Test    void testAddFirst() {        list.addFirst(1);        list.addFirst(2);        list.addFirst(3);        assertIterableEquals(List.of(3, 2, 1), list);    }    @Test    void testAddLast() {        list.addLast(100);        list.addLast(99);        list.addLast(98);        assertIterableEquals(List.of(100, 99, 98), list);    }    @Test    void testRemoveFirst() {        list.addFirst(1);        list.addFirst(2);        list.addFirst(3);        list.removeFirst();        assertIterableEquals(List.of(2, 1), list);    }    @Test    void testRemoveFirstOnEmptyList() {        assertThrows(IllegalArgumentException.class, () -> list.removeFirst());    }    @Test    void testRemoveLast() {        list.addLast(100);        list.addLast(99);        list.addLast(98);        list.removeLast();        assertIterableEquals(List.of(100, 99), list);    }    @Test    void testRemoveLastOnEmptyList() {        assertThrows(IllegalArgumentException.class, () -> list.removeLast());    }    @Test    void testRemoveByValue() {        list.addLast(100);        list.addLast(99);        list.addLast(98);        list.removeByValue(99);        assertIterableEquals(List.of(100, 98), list);    }    @Test    void testRemoveByValueNotFound() {        list.addLast(100);        list.addLast(99);        list.addLast(98);        assertThrows(RuntimeException.class, () -> list.removeByValue(101));    }    @Test    void testTraverse() {        list.addFirst(1);        list.addFirst(2);        list.addFirst(3);        list.addLast(100);        list.addLast(99);        list.addLast(98);        list.traverse();    }    @Test    void testIterator() {        list.addFirst(1);        list.addFirst(2);        list.addFirst(3);        var iterator = list.iterator();        assertTrue(iterator.hasNext());        assertEquals(3, iterator.next());        assertEquals(2, iterator.next());        assertEquals(1, iterator.next());        assertFalse(iterator.hasNext());    }    @Test    void testEmptyList() {        assertThrows(IllegalArgumentException.class, () -> list.removeFirst());        assertThrows(IllegalArgumentException.class, () -> list.removeLast());        assertThrows(RuntimeException.class, () -> list.removeByValue(1));    }}

C语言实现

#include <stdio.h>#include <stdlib.h>typedef struct ListNode {    struct ListNode* prev;    int data;    struct ListNode* next;} ListNode;typedef struct {    ListNode* head;} BidirectionalCircularLinkedList;ListNode* createNode(int data) {    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));    newNode->data = data;    newNode->prev = NULL;    newNode->next = NULL;    return newNode;}void initList(BidirectionalCircularLinkedList* list) {    list->head = createNode(666);    list->head->prev = list->head;    list->head->next = list->head;}void addFirst(BidirectionalCircularLinkedList* list, int data) {    ListNode* added = createNode(data);    added->prev = list->head;    added->next = list->head->next;    list->head->next->prev = added;    list->head->next = added;}void addLast(BidirectionalCircularLinkedList* list, int data) {    ListNode* added = createNode(data);    added->prev = list->head->prev;    added->next = list->head;    list->head->prev->next = added;    list->head->prev = added;}void removeFirst(BidirectionalCircularLinkedList* list) {    if (list->head->next == list->head) {        printf("空链表不允许删除\n");        return;    }    ListNode* first = list->head->next;    list->head->next = first->next;    first->next->prev = list->head;    free(first);}void removeLast(BidirectionalCircularLinkedList* list) {    if (list->head->prev == list->head) {        printf("空链表不允许删除\n");        return;    }    ListNode* last = list->head->prev;    list->head->prev = last->prev;    last->prev->next = list->head;    free(last);}void removeByValue(BidirectionalCircularLinkedList* list, int data) {    ListNode* current = list->head->next;    while (current != list->head) {        if (current->data == data) {            current->prev->next = current->next;            current->next->prev = current->prev;            free(current);            return;        }        current = current->next;    }    printf("在链表中没有找到与数据[%d]相同的结点数据域\n", data);}void traverse(BidirectionalCircularLinkedList* list) {    ListNode* current = list->head->next;    while (current != list->head) {        printf("%d ", current->data);        current = current->next;    }    printf("\n");}void freeList(BidirectionalCircularLinkedList* list) {    ListNode* current = list->head->next;    while (current != list->head) {        ListNode* temp = current;        current = current->next;        free(temp);    }    free(list->head);}int main() {    BidirectionalCircularLinkedList list;    initList(&list);    addFirst(&list, 1);    addFirst(&list, 2);    addFirst(&list, 3);    addLast(&list, 100);    addLast(&list, 99);    addLast(&list, 98);    printf("添加节点后的链表: ");    traverse(&list); // 输出: 3 2 1 100 99 98    removeFirst(&list);    printf("删除头部节点后的链表: ");    traverse(&list); // 输出: 2 1 100 99 98    removeLast(&list);    printf("删除尾部节点后的链表: ");    traverse(&list); // 输出: 2 1 100 99    removeByValue(&list, 100);    printf("删除值为100的节点后的链表: ");    traverse(&list); // 输出: 2 1 99    removeByValue(&list, 101); // 输出: 在链表中没有找到与数据[101]相同的结点数据域    freeList(&list);    return 0;}

总结

双向循环链表已经是链表中结构比较复杂的一种了，建议将所有基本操作模拟之后再对应代码。这与单链表中的处理方案是不同的，在单链表中，由于指针链总是沿着一个方向，所以只需要断开哨兵结点与首元结点的链接即可，但是在双向链表背景下，通过首元结点直接后继的前驱指针依然可以访问到首元结点。只不过当链表中存在重复元素，遍历方向的不同就会产生不同的结果，如果使用前一种方法，就会返回链表中第一个存储指定元素的结点，而使用后一种方法就会返回链表中最后一个存储指定元素的结点。

public void removeFirst() {        if (head.next == head)            throw new IllegalArgumentException("空链表不允许删除");        ListNode secondNode = head.next.next;        head.next.next = null;        head.next.prev = null;        secondNode.prev = head;        head.next = secondNode;    }

6. 删除尾结点

与删除首元结点对应，需要先找到尾结点的直接前驱，让尾结点直接前驱的后继指针指向哨兵结点，同时需要让哨兵结点的前驱指针指向尾结点的直接前驱。而十字链表主要用于图数据结构，我们本文先对双向循环链表做一简要分析与实现。

对应到代码，如下。

我们需要将待插入结点的前驱指针域  指向哨兵结点，将待插入结点的后继指针域  指向首元结点，也就是哨兵结点的直接后继，以上对待插入结点的操作处理完成，如下。

private ListNode findByValue(int data) {        ListNode indexNode = head.next;        while (indexNode != head) {            if (indexNode.data == data)                return indexNode;            indexNode = indexNode.next;        }        return null;    }

8. 删除指定结点

我们上面实现的查找指定结点工具方法就派上用场了，可以调用上面实现的  方法，届时只需要按照规则修改结点指针域即可。

public void addFirst(int data) {        ListNode added = new ListNode(data);        added.prev = head;        added.next = head.next;        head.next.prev = added;        head.next = added;    }

private final int SENTINEL_VALUE = 666;    private ListNode head = new ListNode(null, SENTINEL_VALUE, null);    public BidirectionalCircularLinkedListSentinel() {        head.prev = head;        head.next = head;    }