链表


介绍

数组和链表都属于线性结构,数组在内存上给出了连续的空间,链表在内存上的存储方式可以是不连续的。
在实际生产操作中,数组的使用是需要预先声明长度的,这就会导致面对庞大的数据量可能会出现内存溢出的情况,如果给定数据集的分布是发散,稀疏的,还会导致内存空间的浪费,而且数组结构不适合动态数据的存储(比如添加,删除元素等),但是在查询效率上要比链表高。
对于动态数据的存储方式而言,使用链表结构能动态的添加,删除和改变表的大小,只需要操作指针即可,但是如果要进行数据查找的话,要将链表所有数据遍历一遍,这样会使查询效率低下,所以还是要具体问题具体分析,

复杂度

查找 插入 删除
数组 O(1) O(N) O(N)
链表 O(N) O(1) O(1)

链表结构定义

1
2
3
4
5
6
7
typedef struct LNode* PtrToLNode;
typedef int ElementType;
struct LNode{
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode List;

C语言实现链表

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

List makeEmpty();//初始化链表
int Length(List PtrL);//求表长
List findKth(int K, List PtrL);//按序号查找
List find(ElementType X, List PtrL);//按值查找
List Insert(ElementType X, int i, List PtrL);//插入元素
List Delete(int i, List PtrL);//删除元素

List makeEmpty()
{
List L;
L = (List)malloc(sizeof(struct LNode));
if(L == NULL){
printf("内存分配失败\n");
exit();
}
L->Next = NULL;
return L;
}

//头插法创建链表
List createH()
{
List L = makeEmpty();

ElementType x;

while(scanf("%d",&x) != EOF)
{
LNode *p;
p = (List)malloc(sizeof(struct LNode)); //申请新的结点
p->data = x; //结点数据域赋值
p->next = L->next;
L->next = p;
}
return L;

}
//尾插法创建链表
List createT()
{
List L = makeEmpty();

t = L; //t指向最终结点
ElementType x;

while(scanf("%d",&x) != EOF)
{
LNode *p;
p = (List)malloc(sizeof(struct LNode)); //申请新的结点
p->data = x; //结点数据域赋值
t->next = p;
t->next = NULL;
}
return L;
}
//求表长
int Length(List PtrL){
List p = PtrL;//p指向表的第一个结点
int j = 0;
while(p){
p = p->Next;
j++;
}
return j;

}

//按序号查找
List FindKth(int K, List PtrL)
{
List p = PtrL;
int i = 1;
while (p != NULL && i<K){
p = PtrL->Next;
i++;
}
if (i == K){
return p;//返回指针
}else{
return NULL;
}
}

//按值查找
List find(ElementType X, List PtrL)
{
List p = PtrL;
while(p!=NULL && p->Data != X){
p = p->Next;
}
}

List Insert(ElementType X, int i, List PtrL)
{
List p,s;
//新结点插在表头,没有第0个所以要先判断
if(i==1){
s = (List)malloc(sizeof(struct LNode));
s->Data = X;
s->Next = PtrL;
return s;
}
p = Find(i-1, PtrL);
if (p==NULL){
printf("参数i错误");
return NULL;
}else{
s = (List)malloc(sizeof(struct LNode));
s->Data = X;
s->Next = p->Next;
p->Next = s;
return PtrL;
}
}

List Delete(int i, List PtrL)
{
List p,s;
if(i == 1){
s = PtrL;
if(PtrL!=NULL){
PtrL = PtrL->Next;
}else{
return NULL;
}
free(s);//释放结点
return PtrL;
}
p = FindKth(i-1, PtrL);
if(p === NULL){
printf("第%d个结点不存在", i-1);
return NULL;
}else if(p->Next == NULL){
printf("第%d个结点不存在", i);
return NULL;
}else{
s = p->Next;
p->Next = s->Next;
free(s);
return NULL;
}
}

int main() {
List H = createH();
List T = createT();
return 0;
}