【数据结构】双向链表实现-蒲公英云

双向链表(Double Linked List)

由两个指针域构成，分别指向前驱、后驱。如下图。
在这里插入图片描述

判断链表是否到头、到尾：list.next != null、list.prior != null
假设上图中间节点为q，则有: q = q->next->prior = q.prior.next

线性链表、单链表: https://blog.csdn.net/weixin_43217942/article/details/104856259

#include <stdio.h>
#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
typedef int status;
typedef int ElemType;
typedef struct Node { 
    ElemType data;//数据
    struct Node *prior;//前驱
    struct Node *next;//后驱
} Node, *DLinkList;
/* * 初始化List * 初始化时前后驱都需要设为 NULL * 指针创建出来不初始化,会随机到其他地址,之后时候指针会修改其他地方的数据 */
void initList(DLinkList &L) { 
    L = new Node;
    L->next = NULL;
    L->prior = NULL;
}
/* * 初始化L并创建n个元素 */
void createList(DLinkList &L, int n) { 
    //init L
    L = new Node;
    L->prior = NULL;
    L->next = NULL;
    DLinkList q, add_elem;
    q = L;
    for (int i = 0; i < n; i++) { 
        add_elem = new Node;
        add_elem->prior = NULL;
        add_elem->next = NULL;
        scanf("%d", &add_elem->data);
        q->next = add_elem;
        add_elem->prior = q;
        q = q->next;
    }
}
/* * 在尾部添加元素 * 首先找到尾元素,然后添加即可 */
status addLast(DLinkList &L, ElemType e) { 
    DLinkList q = L;
    while (q && q->next != NULL) { 
        q = q->next;
    }
    Node *add_elem = new Node;
    add_elem->prior = NULL;
    add_elem->next = NULL;
    add_elem->data = e;
    q->next = add_elem;
    add_elem->prior = q;
    return OK;
}
/* * 在第i处添加元素e * 首先找到第i个元素 * while执行完后q指向第i个元素 * 此处注意: q指向最后余割元素需特殊处理 */
status addElem(DLinkList &L, int i, ElemType e) { 
    DLinkList q;
    q = L;
    int j = 0;
    while (q && j < i) { 
        q = q->next;
        j++;
    }
    Node *add_elem = new Node;
    add_elem->prior = NULL;
    add_elem->next = NULL;
    add_elem->data = e;
    // i<0 i>n
    if (!q || j > i) return ERROR;
    //处理i=0 或 i=n
    if (q->next == NULL) { 
        q->next = add_elem;
        add_elem->prior = q;
        return OK;
    }
    add_elem->next = q;
    q->prior = add_elem;
    add_elem->prior = q->prior;
    q->prior->next = add_elem;
    return OK;
}
//在头部添加元素
status addFirst(DLinkList &L, ElemType e) { 
    Node *add_elem = new Node;
    add_elem->data = e;
    add_elem->next = L->next;
    L->next->prior = add_elem;
    add_elem->prior = L;
    L->next = add_elem;
    return OK;
}
/* * 将第i个元素的值设置为e * 首先找到第i个元素 * while执行完后q指向第i个元素 * 注意: 当i=0, 设置的是头元节点的data */
status setElem(DLinkList &L, int i, ElemType e) { 
    DLinkList q;
    q = L;
    int j = 0;
    while (q && j < i) { 
        q = q->next;
        j++;
    }
    //i<0 i>n
    if (!q || j > i) return ERROR;
    q->data = e;
    return OK;
}
//获取第i个elem
ElemType getElem(DLinkList L, int i) { 
    DLinkList q;
    q = L;
    int j = 0;
    while (q && j < i) { 
        q = q->next;
        j++;
    }
    //i<0 i>n
    if (!q || j > i) return ERROR;
    return q->data;
}
//删除第i个元素
status delElem(DLinkList &L, int i) { 
    if (L->next == NULL) return ERROR;
    DLinkList q = L;
    int j = 0;
    while (q && j < i) { 
        q = q->next;
        j++;
    }
    //i<1 i>n
    if (!q || j > i) return ERROR;
    Node *del_node;
    del_node = q;
    //尾元素
    if (q->next == NULL) { 
        q->prior->next = NULL;
        delete del_node;
        return OK;
    }
    //非尾元素 删除q.next
    q->next->prior = q->prior;
    q->prior->next = q->next;
    delete del_node;
    return OK;
}
//删除首元素
status delFirst(DLinkList &L) { 
    //空表
    if (L->next == NULL) return ERROR;
    //删除L.next
    Node *del_node = L->next;
    L->next->next->prior = L;
    L->next = L->next->next;
    delete del_node;
    return OK;
}
//删除尾原宿
status delLast(DLinkList &L) { 
    DLinkList q = L;
    while (q->next != NULL) { 
        q = q->next;
    }
    Node *del_node = q;
    q->prior->next = NULL;
    delete del_node;
    return OK;
}
//链表大小
//此处的参数L是DLinkList指针的拷贝,相当于DLinkList L = L2;
int size(DLinkList L) { 
    if (L->next == NULL) return 0;
    int n = 0;
    while (L->next != NULL) { 
        L = L->next;
        n++;
    }
    return n;
}
status isEmpty(DLinkList L) { 
    if (L->next == NULL)return TRUE;
    return FALSE;
}
void printList(DLinkList L) { 
    printf("---正序遍历---\n");
    while (L->next != NULL) { 
        printf("%d\n", L->next->data);
        L = L->next;
    }
    //测试prior指针是否正确
// printf("---倒序遍历---\n");
// while(L->prior!=NULL){ 
// printf("%d\n", L->data);
// L = L->prior;
// }
}
int main() { 
    DLinkList L;
    initList(L);
    addLast(L, 1);
    addLast(L, 2);
    addLast(L, 3);
// delLast(L);
// delFirst(L);
// delElem(L, 1);
// addFirst(L,0);
// addElem(L,4,4);
// setElem(L,3,33);
// printf("%d\n",getElem(L,3));
// printf("%d\n",size(L));
// printf("%d\n",isEmpty(L));
    printList(L);
// DLinkList L2;
//输入三个元素
// createList(L2, 3);
//
// printList(L2);
    return 0;
}