双链表（线性表的链式存储）---C语言版_双链表在最后处加入节点的时间复杂度

双链表（线性表的链式存储）—C语言版

单链表结点中只有一个指向其后继结点的指针，使得单链表只能从头结点依次顺序地向后遍历。
要访问某个结点的前驱结点，只能从头开始遍历。
也就是说：访问后继结点的时间复杂度为O(1),访问前驱结点的时间复杂度为O(n)

为了克服单链表的上述缺点，引入了双链表。
双链表中有两个指针prior和next，分别指向其前驱结点和后继结点

一、双链表的定义

定义
仍旧使用该例子，我们要如何存储该表呢？

步骤一：声明数据元素类型

首先我们使用结构体声明数据元素（对应表中的一行数据）的类型

typedef struct{
   
    int id;//对应表中的id
    char name[100];//对应表中的姓名
    char description[200];//对应表中的描述
}ElemType;//此处的ElemType是个类型名
1
2
3
4
5
6

步骤二：声明结点
双链表中结点定义如下：

typedef struct DNode{
   
    ElemType data;//数据域
    struct DNode *prior;//前驱指针
    struct DNode *next;//后继指针
}DNode,*DLinkList;
1
2
3
4
5
6

双链表逻辑示意图：

二、双链表上具体操作的实现和时间复杂度

使用含头结点的双链表

1、初始化表。构造一个空表。

/*初始化*/
int InitList_DLink(DLinkList *L){
   
    *L=(DLinkList)malloc(sizeof(DNode));//创建头结点，并让头指针指向头结点
    if (!(*L)) return FALSE;//分配失败
    (*L)->prior=NULL;//头结点的prior永远指向NULL
    (*L)->next=NULL;//初始化为空
    return TRUE;//初始化成功
}
1
2
3
4
5
6
7
8
9

空表：

时间复杂度：

时间复杂度为O(1)

2、根据数组创建双链表（头插法和尾插法）

1.头插法

/*头插法创建双链表*/
int create_HeadInsert(DLinkList *L,ElemType a[],int n){
   
 // InitList_DLink(L);
    DNode *s;//用来指示新创建的结点
    int i;
    for(i=n-1;i>=0;i--){
   //由于D头插法是倒序插入，所以这里我们从数组最后开始遍历
        s=(DLinkList)malloc(sizeof(DNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        s->next=(*L)->next;//让该结点的后继指向第一个结点
        if((*L)->next!=NULL) (*L)->next->prior=s;//第一个结点的前驱指向该结点
        s->prior=(*L);//让该结点的前驱指向头结点   
        (*L)->next=s;//让头结点指向该D结点（该结点成为第一个结点）
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

如图所示：

2.尾插法

/*尾插法创建双链表*/
int create_TailInsert(DLinkList *L,ElemType a[],int n){
   
 // InitList_DLink(L);
    DNode *s,*r=(*L); //s用来指示新创建的结点，r用来移动以连接链表
    int i;
    for(i=0;i<n;i++){
   //遍历数组
        s=(DLinkList)malloc(sizeof(DNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        r->next=s;//r始终指向链表的尾端，这里将新结点连接到r的后面
        s->prior=r;//该结点的前驱指向r指向的结点
        r=s;//r移动到链表尾端o
    
1
2
3
4
5
6
7
8
9
10
11
12
13