2.3.2_3 单链表的建立

news/2025/1/15 15:04:57/

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。
此外，《程序员必备技能》专栏和《程序员必备工具》专栏（该专栏暂未开设）日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！
谢谢大家！

引言

假如有很多个数据元素，怎么把他们存到一个单链表里面

初始化一个单链表
每次取一个数据元素，插入到表尾/表头

本节讨论带头结点的情况

尾插法建立单链表

具体代码实现：

typedef struct LNode{ElemType data;struct LNode *next;
}LNode, *LinkList;//初始化一个单链表
bool InitList(LinkList &L){L = (LNode *) malloc (sizeof(LNode));  //分配一个头结点if(L == NULL)       //内存不足，分配失败return false;L->next = NULL;     //头结点之后暂时没有结点return true;
}void test(){LinkList L;InitList(L);//......
}

举例：
初始化单链表
设置变量length记录链表长度

while 循环{ 每次取一个元素e;ListInsert(L, length+1, e)插到尾部； length++;
}

这种操作的时间复杂度为： $O(n^2)$ ，还是很高的

其实完全可以采用更好的方法：
设置一个表尾指针r
每次要插入元素的时候只需要对r进行后插操作就好了[[2.3.2_1 单链表的插入和删除#指定结点的后插操作]]

课本中的代码：

LinkList List_TailInsert(LinkList &L){  正向建立单链表int x;  //设ElemType为整型L = (LNode *) malloc (sizeof(LNode));  //建立头结点LNode *s, *r = L;  //r为表尾指针scanf("%d", &x);  //输入结点的值while(x != 9999){  //输入9999表示结束s = (LNode *) malloc (sizeof(LNode));s->data = x;r->next = s;r = s;        //r指向新的表尾结点scanf("%d", &x);}r->next = NULL;   //尾结点指针置空return L;
}

时间复杂度： $O (n)$

头插法

课本中的代码：

LinkList List_HeadInsert(LinkList &L){  //逆向建立单链表LNode *s;int x;L = (LNode *) malloc (sizeof(LNode)); //创建头结点L->next = NULL; //初始化为空链表scanf("%d", &x); //输出结点的值while(x != 9999){ //输入9999表示结束s = (LNode *) malloc (sizeof(LNode)); //创建新结点s->data = x;s->next = L->next;L->next = s; //将新结点插入表中，L为头指针scanf("%d", &x);}return L;
}