前面已经说过线性表类型的结构在进行插入和删除操作时要移动大量元素,导致时间复杂度高。
链表中,每一数据元素需要存储数据信息之外,还要存储它的后继元素的内存地址。
头指针与头结点
头指针 | 头结点 |
---|---|
头指针是指向链表第一个结点的指针;头指针具有标识作用;无论链表是否为空,头指针均不为空 | 头结点是为了链表操作方便而设立的,放在第一个元素之前; |
头指针是头结点的指针域部分
单链表的存储结构
1 | type struct Node |
链表的结点由存放数据元素的数据域和存放后继结点的指针域组成
单链表的创建
创建单链表的过程就是一个动态生成链表的过程。从“空表”的初始状态开始,依次建立各个结点,并逐个插入链表中。
头插法建立单链表:
- 声明一个结点p和计数器变脸i
- 初始化空链表L
- 让L的的头结点的指针指向NULL,即建立一个带头结点的单链表
- Loop:
- 生成新结点赋值给p
- 结点p的数据域赋值
- 将p插入到头结点与前一个结点之间
1 | void create_linklist(LinkList *L,int n) |
尾插法创建单链表:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void creata_list_tail(LinkList *L ,int n)
{
LinkList p,r;
int i;
*L = (LinkList)malloc(sizeof(Node));
r = *L; /* r直线尾部的结点 */
for(i=0;i<n;i++)
{
p = (LinkList)malloc(sizeof(Node));
p->data = rand()%100 + 1;
r->next = p; /* 将当前链表的终端结点的指针域指向新的结点 */
r = p; /* 现在链表的尾节点的指针域应该是p的指针域 */
}
r->next = NULL; /* 链表创建完毕,尾结点指向NULL */
}
单链表的插入
通俗来讲,要向单链表中插入一个元素,那么
- 新增结点的指针域指向后续结点
- 新增结点上一个结点的指针域指向新增结点
就可以完成单链表的结点插入。
假设现在要向单链表L的第i个元素前插入新的数据元素e:
1 | Status list_insert(LinkList *L,int I,ElemType e) |
若上述代码①和②互换位置,会导致剩余链表的地址丢失,链表数据丢失。
单链表的删除
与单链表的插入原理相同,需要完成以下几步:
- 查找单链表中需要删除的元素,若没有则抛错
- 将被删除结点的前一个结点的指针域指向被删除结点的后一个结点 p->next = p->next->next
- 将删除结点的数据返回 *e = p->data
单链表结构与顺序存储结构的优缺点
- 时间性能
- 单链表查找慢O(n);线性表快o(1)
- 单链表插入和删除快o(1);线性表慢O(n)
- 空间性能
- 单链表不需要分配存储空间大小,元素个数不受限制
- 顺序存储结构需要预分配内存,而且存在硬件上限的限制
循环链表:将单链表中终端节点的指针域改为指向头结点,使得整个单链表形成一个环,这种首尾相接的单链表称为循环链表
本文链接: http://www.xiaopeng.pro/articles/2362a8ea.html
版权声明: 本原创文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!