双向链表

结构定义

//结构定义
typedef struct Node { //节点定义 
    int val;
    struct Node *next; // 后驱指针 -> 
    struct Node *per;  //前驱指针 <-
} Node;

typedef struct DList { //双向链表定义 
    int length; //链表长度 
    Node head; //链表头地址 
} DList; 

结构操作|函数接口

Node *getNewNode();
void clear_Node(Node *n);
DList *init_DList();
int insert(DList *, int , int);
int erase(DList *, int);
void clear_DList(DList *);
void next_output(DList *);
void per_output(DList *);

代码演示

//双向链表 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//结构定义
typedef struct Node { //节点定义 
    int val;
    struct Node *next; // 后驱指针 -> 
    struct Node *per;  //前驱指针 <-
} Node;

typedef struct DList { //双向链表定义 
    int length; //链表长度 
    Node head; //链表头地址 
} DList; 

//结构操作

Node *getNewNode(int val) { //节点初始化 
    Node *n = (Node *)malloc(sizeof(Node));
    n->val = val;
    n->next = NULL;
    n->per = NULL;
    return n;
}

void clear_Node(Node *n) { //节点销毁 
    if (n == NULL) return ;
    free(n);
    return ;
}

DList *init_DList() { //链表初始化 
    DList *l = (DList *)malloc(sizeof(DList));
    l->length = 0;
    l->head.next = NULL;
    return l;
}

void clear_DList(DList *l) {
    if (l == NULL) return ;
    Node *p = l->head.next;
    while (p) {
        Node *q = p->next;
        clear_Node(p);
        p = q;
    }
    free(l);
    return ;
}

int insert(DList *l, int ind, int val) { //节点插入 
    if (l == NULL) return 0;
    if (ind < 0 || ind > l->length) return 0;
    Node *p = &(l->head), *n = getNewNode(val);
    while (ind--) p = p->next;
    n->next = p->next;
    p->next = n;
    n->per = p;
    if (n->next) n->next->per = n;
    l->length += 1;
    return 1;
}

int erase(DList *l, int ind) { //节点删除 
    if (l == NULL) return 0;
    if (ind < 0 || ind >= l->length) return 0;
    Node *p = &(l->head), *q;
    while (ind--) p = p->next;
    q = p->next;
    p->next = q->next;
    if(q->next) q->next->per = p;
    free(q);
    l->length -= 1;
    return 1;
}

//void next_output(DList *l) {
//    if (l == NULL) return ;
//    Node *p = l->head.next;
//    printf("next元素个数（%d）: [", l->length);
//    for (int i = 0; i < l->length; i++) {
//        i && printf("->");
//        printf("%d", p->data);
//        p = p->next;
//    }
//    printf("NULL ]\n");
//}

void next_output(DList *l) {
    if (l == NULL) return ;
    printf("next(%d) : ", l->length);
    for (Node *p = l->head.next; p; p = p->next) {
        printf("%d->", p->val);
    }
    printf("NULL\n");
    return ;
}

void per_output(DList *l) {
    if (l == NULL) return ;
    Node *p = &(l->head);
    printf("per元素个数（%d）: ", l->length);
    int ind = l->length;
    while (ind--) p = p->next;
    for (; p != &(l->head); p = p->per) {
        printf("%d->", p->val);
    }
    printf("head\n");
    return ;
} 

int main() {
    srand(time(0));
    #define n 200
    DList *l = init_DList();
    for (int i = 0; i < n; i++) {
        int op = rand() % 4;
        int ind = rand() % (l->length + 3) - 1;
        int val = rand() % 100;
        switch (op) {
            case 0 :
            case 1 :
            case 2 : {
                printf("插入元素：%d, 插入位置：%d, %s\n", val, ind, insert(l, ind, val) ? "成功" : "失败"); 
            } break;
            case 3 : {
                printf("删除位置：%d, %s\n", ind, erase(l ,ind) ? "成功" : "失败"); 
            } break;
        }
        next_output(l), printf("\n");
        per_output(l), printf("\n");
    }
    #undef n
    clear_DList(l);
    return 0;
}