单链表的读取

单链表第i个数据的算法思路:

1.声明一个指针p指向链表第一个结点,初始化j从1开始;

2.当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1;

3.若到链表末尾p为空,则说明第i个结点不存在;

4.否则查找成功,返回结点p的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */
/* 操作结果:用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L, int i, ElemType *e)
{
int j;
LinkList p; /* 声明一指针p */
p = L->next; /* 让p指向链表L的第个结点 */
j = 1; /* j为计数器 */
/* p不为空且计数器j还没有等于i时,循环继续 */
while (p && j < i)
{
p = p->next; /* 让p指向下一个结点 */
++j;
}
if (!p || j > i)
return ERROR; /* 第i个结点不存在 */
*e = p->data; /* 取第i个结点的数据 */
return OK;
}

从头开始找,直到第i个结点为止。由于这个算法的时间复杂度取决于i的位置,当i=1时,则不需遍历,第一个就取出数据了,而当i=n时则遍历n-1次才可以。因此最坏情况的时间复杂度是O(n)。

单链表的插入与删除

单链表的插入

1
s->next = p->next; p->next = s;

单链表第i个数据插入结点的算法思路:

1.声明一指针p指向链表头结点,初始化j从1开始;

2.当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1;

3.若到链表末尾p为空,则说明第i个结点不存在;

4.否则查找成功,在系统中生成一个空结点s;

5.将数据元素e赋值给s->data;

6.单链表的插入标准语句s->next=p->next;p->next=s;

7.返回成功。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* 初始条件:顺序线性表L已存在,1≤i≤
ListLength(L), */
/* 操作结果:在L中第i个结点位置之前插入新的数
据元素e,L的长度加1 */
Status ListInsert(LinkList *L, int i, ElemType e)
{
int j;
LinkList p, s;
p = *L;
j = 1;
/* 寻找第i-1个结点 */
while (p && j < i)
{
p = p->next;
++j;
}
/* 第i个结点不存在 */
if (!p || j > i)
return ERROR;
/* 生成新结点(C标准函数) */
s = (LinkList)malloc(sizeof(Node));
s->data = e;
/* 将p的后继结点赋值给s的后继 */
s->next = p->next;
/* 将s赋值给p的后继 */
p->next = s;
return OK;
}

单链表的删除

1
q=p->next; p->next=q->next;

单链表第i个数据删除结点的算法思路:

1.声明一指针p指向链表头结点,初始化j从1开始;

2.当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1;

3.若到链表末尾p为空,则说明第i个结点不存在;

4.否则查找成功,将欲删除的结点p->next赋值给q;

5.单链表的删除标准语句p->next=q->next;

6.将q结点中的数据赋值给e,作为返回;

7.释放q结点;

8.返回成功。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* 初始条件:顺序线性表L已存在,1≤i≤
ListLength(L) */
/* 操作结果:删除L的第i个结点,并用e返回其
值,L的长度减1 */
Status ListDelete(LinkList *L, int i, ElemType *e)
{
int j;
LinkList p, q;
p = *L;
j = 1;
/* 遍历寻找第i-1个结点 */
while (p->next && j < i)
{
p = p->next;
++j;
}
/* 第i个结点不存在 */
if (!(p->next) || j > i)
return ERROR;
q = p->next;
/* 将q的后继赋值给p的后继 */
p->next = q->next;
/* 将q结点中的数据给e */
*e = q->data;
/* 让系统回收此结点,释放内存 */
free(q);
return OK;
}

总结

单链表插入和删除算法,都是由两部分组成:第一部分就是遍历查找第i个结点;第二部分就是插入和删除结点。
它们的时间复杂度都是O(n)。

如果在我们不知道第i个结点的指针位置,单链表数据结构在插入和删除操作上,与线性表的顺序存储结构是没有太大优势的。但如果,我们希望从第i个位置,插入10个结点,对于顺序存储结构意味着,每一次插入都需要移动n-i个结点,每次都是O(n)。而单链表,我们只需要在第一次时,找到第i个位置的指针,此时为O(n),接下来只是简单地通过赋值移动指针而已,时间复杂度都是O(1)。显然,对于插入或删除数据越频繁的操作,单链表的效率优势就越是明显。

欢迎扫描下方二维码,持续关注:

image
image

互联网工程师(id:phpstcn),我们一起学习,一起进步