单链表是最简单确定链表,由一系列节点组成的序列,包括三部分:头指针、头节点、元节点。其中头节点根据实际需求可以不用。有头节点的优点是可保证链表非空,便于判断其他无效的指针即空指针。

单链表节点的定义

单链表的节点包括数据域和指针域。指针域中的指针指向下一个节点;数据域用于存放数据,存放的数据也可以是指针类型。

1
2
3
4
5
typedef int DataType;
typedef struct LinkListNode{
DataType data;
struct LinkListNode * next;
}LinkListNode, * NodePtr;

虽然这里我还定义了NodePtr这个指针类型,但是我不太喜欢使用。因为在后面的程序中没有看到*可能会忘记它是一个指针。把它写在这里是因为大多数经典教材都写了的。

单链表用熟练之后就可以把LinkListNode直接改为Node,当然前提是不会和后面的树或图产生歧义。

单链表的初始化

下面的单链表默认都带头节点。

法一:通过返回值进行传递

1
2
3
4
5
6
7
8
9
10
11
12
13
14
LinkListNode * InitLinkList(int n){
LinkListNode * head=(LinkListNode*)malloc(sizeof(LinkListNode));
if(head==NULL) exit(0);
head->next=NULL;
LinkListNode * temp=head;
for(int i=1;i<=n;i++){
temp->next=(LinkListNode*)malloc(sizeof(LinkListNode));
if(temp->next==NULL) exit(0);
temp=temp->next;
temp->next=NULL;
temp->data=i;
}
return head;
}

法二:通过指针进行传递

1
2
3
4
5
6
7
8
9
10
11
12
13
void InitLinkList(LinkListNode * head,int n){
head=(LinkListNode*)malloc(sizeof(LinkListNode));
if(head==NULL) exit(0);
head->next=NULL;
LinkListNode * temp=head;
for(int i=n;i>0;i--){
temp->next=(LinkListNode*)malloc(sizeof(LinkListNode));
if(temp->next==NULL) exit(0);
temp=temp->next;
temp->next=NULL;
scanf("%d",&(temp->data);
}
}

千万要注意,如果通过指针进行传递的话,调用的时候就应该用二重指针,即**。这点很容易犯错!不过*的个数多了我也不喜欢用了。

单链表的四大基本操作

1. 按址查找

单链表的查找,不论是按址查找,还是按值查找,都要从头指针开始,往后面一个一个地查找,所以时间复杂度均为O(n)。查找的方法就是设置一个工作指针往下移动直至查找成功。

1
2
3
4
5
6
7
8
9
DataType LinkListLocate_1(LinkListNode * head,int pos){
LinkListNode * temp=head->next;
for(int i=1;i<=pos;i++){
if(i==pos)
return (temp->data);
else if(temp->next==NULL) exit(0);
temp=temp->next;
}
}

因为返回值不确定,所以上面的程序没有直接返回值,有的编译器可能会警告,不是太好。

最好通过指针向主调函数传递查找到的data。

1
2
3
4
5
6
7
8
9
10
int LinkListLocate_1(LinkListNode * head,int pos,DataType * data){
LinkListNode * temp=head->next;
for(int i=1;i<=pos;i++){
if(i==pos)
*data=temp->data;
else if(temp->next==NULL) return -1;
temp=temp->next;
}
return 0;
}

上面两种函数调用的形式也不相同:

方法一:

1
DataType data=LinkListLocate_1(head,pos);

方法二:

1
2
ElemType data;
LinkListNode(head,pos,&data);

2. 按值查找

1
2
3
4
5
6
7
8
9
10
int LinkListLocate_2(LinkListNode * head,DataType data){
LinkListNode * temp=head->next;
int i=1;
while(temp->data!=data && temp->next!=NULL){
temp=temp->next;
i++;
}
if(temp->data==data) return i;
return -1;
}

3. 插入

向单链表中插入一个元素,只需要改变两次指针,时间复杂度为O(1)(不包括移动指针的步骤,不然仍然为O(n))。但是一定要注意指针改变的顺序,应该为:

1
2
3
//temp指向要插入位置的上一位
add->next=temp->next;
temp->next=add;

实现插入操作的函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int LinkListInsert(LinkListNode * head,int pos,DataType d){
LinkListNode * temp, * add;
add=(LinkListNode*)malloc(sizeof(LinkListNode));
if(add==NULL) return -1;
add->data=d;
temp=head->next;

for(int i=1;i<pos;i++){
temp=temp->next;
if(temp==NULL) return -1;
}
add->next=temp->next;
temp->next=add;
return 0;
}

4. 删除

删除也只需要改变两次指针,时间复杂度为O(1)(不包括移动指针)。

与插入操作不同的是,删除操作需要两个中间指针。指针改变的顺序为:

1
2
3
4
5
//此时p指向要删除位置的前一位
q=p->next;
p=q->next;
//一定要把q指向节点的空间释放掉
free(q);

实现删除操作的函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
int LinkListDelete(LinkListNode * head,int pos,DataType * data){
LinkListNode * p, * q;
p=head;
for(int i=1;i<pos;i++){
p=p->next;
if(p==NULL) return -1;
}
q=p->next;
p->next=q->next;
free(q);
return 0;
}

总结

单链表的存取方式为顺序存取,所以对元素的访问必须进行从头进行,不太方便。

单链表的优点是便于修改其中的元素,但是要修改的前提是要先进行访问……

要注意的一点是插入和删除的位置到底在哪里。比如说在pos=6处进行插入或删除,则插入的话应该把新添加的元素放在pos=6处,原来的pos>=6的元素都向后移动一位;删除的话应该删除pos=6的元素,原来的pos>6的元素都向前移动一位。

说实话,我认为用单链表不如用顺序表,特别是,如果顺序表使用动态数组的话可以弥补数组大小得事先确定的缺点。链表的更多使用的是后面的循环链表、双向链表。

下面使用一个程序包括前面单链表的所有操作:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <stdio.h>
#include <stdlib.h>

typedef int DataType;
typedef struct LinkListNode{
DataType data;
struct LinkListNode * next;
}LinkListNode, * NodePtr;

LinkListNode * InitLinkList(int n);
int LinkListLocate_1(LinkListNode * head,int pos,DataType * data);
int LinkListLocate_2(LinkListNode * head,DataType data);
int LinkListInsert(LinkListNode * head,int pos,DataType d);
int LinkListDelete(LinkListNode * head,int pos,DataType * data);
int DisplayLinkList(LinkListNode * head){
LinkListNode * temp=head->next;
while(temp!=NULL){
printf("%d",temp->data);
temp=temp->next;
}
printf("\n");
return 0;
}

int main(){
int n=10;
LinkListNode * head;
head=InitLinkList(n);
printf("原始的序列:");
DisplayLinkList(head);

int pos=6;
DataType data;
LinkListLocate_1(head,pos,&data);
printf("查找的位置的元素为%d\n",data);

pos=LinkListLocate_2(head,data);
printf("查找的元素的位置为%d\n",pos);

LinkListDelete(head,pos,&data);
printf("删除的元素为%d\n",data);
printf("删除后的序列:");
DisplayLinkList(head);

LinkListInsert(head,pos-1,data);
printf("插入后的序列:");
DisplayLinkList(head);

return 0;
}

LinkListNode * InitLinkList(int n){
LinkListNode * head=(LinkListNode*)malloc(sizeof(LinkListNode));
if(head==NULL) exit(0);
head->next=NULL;
LinkListNode * temp=head;
for(int i=1;i<=n;i++){
temp->next=(LinkListNode*)malloc(sizeof(LinkListNode));
if(temp->next==NULL) exit(0);
temp=temp->next;
temp->next=NULL;
temp->data=i;
}
return head;
}
int LinkListLocate_1(LinkListNode * head,int pos,DataType * data){
LinkListNode * temp=head->next;
for(int i=1;i<=pos;i++){
if(i==pos)
*data=temp->data;
else if(temp->next==NULL) return -1;
temp=temp->next;
}
return 0;
}
int LinkListLocate_2(LinkListNode * head,DataType data){
LinkListNode * temp=head->next;
int i=1;
while(temp->data!=data && temp->next!=NULL){
temp=temp->next;
i++;
}
if(temp->data==data) return i;
return -1;
}
int LinkListInsert(LinkListNode * head,int pos,DataType d){
LinkListNode * temp, * add;
add=(LinkListNode*)malloc(sizeof(LinkListNode));
if(add==NULL) return -1;
add->data=d;
temp=head->next;

for(int i=1;i<pos;i++){
temp=temp->next;
if(temp==NULL) return -1;
}
add->next=temp->next;
temp->next=add;
return 0;
}
int LinkListDelete(LinkListNode * head,int pos,DataType * data){
LinkListNode * p, * q;
p=head;
for(int i=1;i<pos;i++){
p=p->next;
if(p==NULL) return -1;
}
q=p->next;
p->next=q->next;
free(q);
return 0;
}

output:

1
2
3
4
5
6
原始的序列:12345678910
查找的位置的元素为6
查找的元素的位置为6
删除的元素为6
删除后的序列:1234578910
插入后的序列:12345678910