双向循环链表

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

// 1. 创建带头节点的双向链表
Node* create_list() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->prev = head;
    head->next = head;
    return head;
}

// 2. 在链表尾部插入节点
void append(Node* head, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;

    Node* last = head->prev;
    last->next = new_node;
    new_node->prev = last;
    new_node->next = head;
    head->prev = new_node;
}

// 3. 在链表头部插入节点
void prepend(Node* head, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;

    new_node->next = head->next;
    new_node->prev = head;
    head->next->prev = new_node;
    head->next = new_node;
}

// 4. 删除指定值的节点
void delete_node(Node* head, int data) {
    Node* current = head->next;
    while (current != 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);
}

// 5. 查找元素位置（从0开始）
int find_position(Node* head, int target) {
    Node* current = head->next;
    int position = 0;

    while (current != head) {
        if (current->data == target) {
            return position;
        }
        current = current->next;
        position++;
    }
    return -1;
}

// 6. 获取链表长度
int get_length(Node* head) {
    int count = 0;
    Node* current = head->next;
    while (current != head) {
        count++;
        current = current->next;
    }
    return count;
}

// 7. 打印链表
void print_list(Node* head) {
    Node* current = head->next;
    printf("链表内容: ");
    while (current != head) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 8. 清空链表
void clear_list(Node* head) {
    Node* current = head->next;
    while (current != head) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    head->next = head;
    head->prev = head;
}

// 9. 销毁链表
void destroy_list(Node* head) {
    clear_list(head);
    free(head);
}

int main() {
    // 测试代码
    Node* head = create_list();

    append(head, 10);
    append(head, 20);
    append(head, 30);
    prepend(head, 5);

    print_list(head);

    printf("元素20的位置: %d\n", find_position(head, 20));
    printf("链表长度: %d\n", get_length(head));

    delete_node(head, 20);
    print_list(head);

    clear_list(head);
    destroy_list(head);
    return 0;
}

本文作者: zhangJinLong
本文链接: https://zhang426fly.github.io/2025/08/25/data_structure/d_list/
版权声明: 本博客所有文章除特别声明外，均采用BY-NC-SA许可协议。转载请注明出处！