双链表

双链表（doubly linked list）和单链表（singly linked list）是两种常见的链表数据结构，它们在内存中存储数据的方式以及对数据的访问方式上有所不同。以下是它们之间的对比：

1. 存储方式：

   • 单链表：每个节点包含一个数据元素和一个指向下一个节点的指针（通常称为“next”指针）。
   • 双链表：每个节点包含一个数据元素，一个指向下一个节点的指针和一个指向前一个节点的指针（通常称为“prev”指针）。

2. 访问方式：

   • 单链表：只能从头节点开始，沿着每个节点的“next”指针顺序地访问每个节点。
   • 双链表：可以从头节点或尾节点开始，沿着每个节点的“next”或“prev”指针来访问每个节点，这使得在某些情况下，双链表的遍历和操作更加灵活。

3. 插入和删除操作：

   • 单链表：在已知位置插入或删除节点时，需要通过修改指针来重新链接节点，因为单链表中只有“next”指针。
   • 双链表：由于双链表有“prev”指针，因此在已知位置插入或删除节点时，可以更轻松地更新相邻节点的链接。

4. 空间复杂度：

   • 单链表和双链表在空间上的复杂度都是O(n)，其中n是链表中的节点数。但是，双链表需要额外的空间来存储每个节点的“prev”指针。

5. 优势和劣势：

   • 单链表的优势在于实现简单，每个节点占用的空间较小，但在某些操作（如查找前一个节点）时效率较低。
   • 双链表的优势在于可以在O(1)时间内查找前一个节点，因此在某些情况下操作更加高效，但它需要额外的空间来存储“prev”指针。

总的来说，选择单链表还是双链表取决于具体的应用场景和需求。如果需要频繁地在中间位置插入或删除节点，或者需要反向遍历链表，则双链表可能更适合。而如果对空间有较高的要求，或者只需要单向遍历链表，则可以选择单链表。

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

typedef int ElemType;
typedef  struct  DNode{ //定义双链表结点类型
    ElemType data; //数据域
    struct DNode *prior,*next; //前驱和后继指针
}DNode,*DLinklist;

int main() {

    return 0;
}

双链表初始化(带头结点)

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

typedef int ElemType;
typedef  struct  DNode{ //定义双链表结点类型
    ElemType data; //数据域
    struct DNode *prior,*next; //前驱和后继指针
}DNode,*DLinklist;

//初始化双链表
bool  InitDLinkList(DLinklist &L){
    L=(DNode *) malloc(sizeof(DNode)); //分配一个头结点
    if(L==NULL) //内存不足，分配失败
    {
        return false;
    }
    L->prior=NULL; //头结点的prior指针永远指向NULL
    L->next=NULL; // 头结点之后暂时还没有节点
    return true;
}

//判断双链表是否为空
bool Empty(DLinklist L){
    if(L->next=NULL)
    {
        return true;
    } else
    {
        return false;
    }
}
int main() {
    //初始化双链表
    DLinklist L;
    InitDLinkList(L);
    return 0;
}

双链表的插入

下面给出的代码是用于在双链表中节点p的后面插入一个新节点s的操作。下面是对该函数的解释：

• s->next = p->next：将新节点s的next指针指向p节点的下一个节点，这样s就插入到了p节点的后面，与p的下一个节点相连。
• p->next->prior = s：将p节点原来的下一个节点的prior指针指向新节点s，这样新节点s就正确地与p节点的下一个节点相连。
• s->prior = p：将新节点s的prior指针指向节点p，这样新节点s就正确地与p节点相连。
• p->next = s：最后将p节点的next指针指向新节点s，这样就完成了在p节点后面插入新节点s的操作。

需要注意的是，这段代码假设了p节点的next指针不是NULL，否则可能会导致空指针异常。在实际使用中，可能需要进行额外的判断以确保程序的健壮性。

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

typedef int ElemType;
typedef  struct  DNode{ //定义双链表结点类型
    ElemType data; //数据域
    struct DNode *prior,*next; //前驱和后继指针
}DNode,*DLinklist;

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    s->next=p->next;
    p->next->prior=s;
    s->prior=p;
    p->next=s;
}

int main() {
    return 0;
}

但是该代码存在问题，如果p是最后一个结点，p->next=NULL，则最后结点并没有前驱指针，此时p->next->prior=s语句出现问题。

需要对代码进行修改，判断p、s的值是否合法，p结点是否还有后继结点。

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

typedef int ElemType;
typedef  struct  DNode{ //定义双链表结点类型
    ElemType data; //数据域
    struct DNode *prior,*next; //前驱和后继指针
}DNode,*DLinklist;

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    if(p==NULL || s==NULL) //非法参数
    {
        return false;
    }
    s->next=p->next;
    if(p->next!=NULL) //判断p结点是否有后继结点
    {
        p->next->prior=s;    
    }
    s->prior=p;
    p->next=s;
}

int main() {
    return 0;
}

双链表的删除

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

typedef int ElemType;
typedef  struct  DNode{ //定义双链表结点类型
    ElemType data; //数据域
    struct DNode *prior,*next; //前驱和后继指针
}DNode,*DLinklist;

//删除p结点的后继节点
bool DeleteNextDNode(DNode *p){
    if(p==NULL)
    {
        return false;
    }
    DNode *q=p->next;
    if(q==NULL)
    {
        return false;
    }
    p->next=q->next;
    if(q->next!=NULL)
    {
        q->next->prior=p;
    }
    free(q);
    return true;
}

int main() {
    DLinklist L = NULL; // 初始化头指针为NULL

    // 创建双链表，假设已经创建并赋值了

    // 循环释放各个数据结点
    while (L != NULL && L->next != NULL) {
        DeleteNextDNode(L);
    }

    // 释放头结点
    free(L);
    L = NULL; // 头指针指向NULL

    return 0;
}

双链表的遍历

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度为O(n)。

双链表的遍历可分为前向遍历、后向遍历和前向遍历(跳过头结点)，下面给出代码。

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

typedef int ElemType;
typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;
} DNode, *DLinklist;

// 前向遍历双链表
void ForwardTraversal(DLinklist L) {
    DNode *p = L->next; // 从第一个节点开始
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 后向遍历双链表
void BackwardTraversal(DLinklist L) {
    DNode *p = L;
    while (p->next != NULL) {
        p = p->next; // 移动到链表的最后一个节点
    }
    while (p != L) {
        printf("%d ", p->data);
        p = p->prior; // 逆序输出节点
    }
    printf("\n");
}

// 前向遍历双链表（跳过头结点）
void ForwardTraversalWithoutHead(DLinklist L) {
    DNode *p = L;
    while (p->next != NULL) {
        p = p->next; // 从头结点的下一个节点开始
        printf("%d ", p->data);
    }
    printf("\n");
}

// 示例函数
int main() {
    // 创建并初始化双链表
    DNode *L = (DNode *)malloc(sizeof(DNode));
    L->next = NULL;
    L->prior = NULL;

    // 假设双链表已经被创建并赋值
    // 此处省略赋值过程

    // 调用函数进行遍历
    printf("Forward traversal: ");
    ForwardTraversal(L);

    printf("Backward traversal: ");
    BackwardTraversal(L);

    printf("Forward traversal without head: ");
    ForwardTraversalWithoutHead(L);

    // 释放双链表的内存
    // 此处省略释放过程

    return 0;

}