链表
基本概念
数据结构的三要素
费曼理解
链表的存储就好像打游戏下副本时的传送门，我们首先看到传送阵，然后进入传送门才能进入下一个房间，而这房间就是数据所在地址，传送门则是指针，指向下个数据所在房间。
内部实现：
单链表
1
2
3
4
5
| typedef struct LNode
{
Elempment data;
struct LNode *next;
}LNode,*linklist
|
- 头结点：代表链表上头指针指向的第一个结点，不带有任何数据。
1
2
3
4
5
6
7
8
9
10
| ### 内存布局
```text
链表头指针 LinkList L
↓
+----------------+----------------+ +----------------+----------------+ +----------------+----------------+
| data | next | --> | data | next | --> | data | next |
| (头节点) | 0x2000 | | 10 | 0x3000 | | 20 | NULL |
+----------------+----------------+ +----------------+----------------+ +----------------+----------------+
地址: 0x1000 地址: 0x2000 地址:0x3000
|
复杂度分析：
初始化一个不带头节点的空链表以及声明单链表
1
2
3
4
5
6
7
8
9
10
| bool InitList(Linklist &L)
{
L=NULL
return true;
}
void BuidList()
{
Linklist L;
Initlist(L);
}
|
复杂度分析
- 时间复杂度：O(1)
- 空间复杂度：O(1)
初始化 带头结点的链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| bool InitList(Linklist &L)
{
L=(LNode*)malloc(sizeof(LNode));
if (L==NULL){
return false;
}
L -> next ==NULL;
return true;
}
void BuidList()
{
Linklist L;
Initlist(L);
}
|
复杂度分析
- 时间复杂度：O(1)
- 空间复杂度：O(1)
按位序插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| bool ListInsert(Linklist &L,int i,Elempment e)
{
if（i<1)
return false;
LNode *p;
int j=0;
p=L;
while(p!=NULL&& j<i-1){
p=p->next;
j++;
}
if(p==NULL){
return false;
}
LNode *s =(LNode *)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
|
复杂度分析
- 时间复杂度：
- 最好情况：在头节点后插入元素-O(1)
- 最坏情况：在链表尾插入元素或i>L.length-O(N)
- 平均情况：在第n/2个节点插入-O(N)
- 空间复杂度：O(1)
指定节点的后插操作
1
2
3
4
5
6
7
8
9
| bool InsertNext(LNode *p,Elempment e){
if(p==NUll)
return false;
LNode *s =(LNode *)malloc(sizeof(LNode));
s=e;
s->next=p-next;
p->next=s;
return true;
}
|
复杂度分析
- 时间复杂度：O(1)
- 空间复杂度：O(1)
指定节点的前插操作
1
2
3
4
5
6
7
8
9
10
| bool Insertpre(LNode *p,Elempment e){
if(p==NULL)
return false;
LNode *s=(LNode *)malloc(sizeof(LNdoe));
s->next=p->next;
p->next=s;
s->data=p->data;
p=->data=e;
return true;
}
|
复杂度分析
- 时间复杂度：O(1)
- 空间复杂度：O(1)
按位序删除节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| bool ListDelete(LNode &l,int i,ElenType &e)
{
if(i<1) return false;
LNode *p;
int j=0;
while(p!=NULL&&j<i-1){
p=p->next;
j++;
}
if(p==NULL) return false;
if(p->next == NULL)
LNode *q=p->next;
e=q->data;
p->next=q->next;
free(q);
return true;
}
|
复杂度分析
- 时间复杂度：
- 最好情况：在头节点后删除元素-O(1)
- 最坏情况：在链表尾删除元素或i>L.length-O(N)
- 平均情况：在第n/2个节点删除-O(N)
- 空间复杂度：O(1)
指定结点的删除
1
2
3
4
5
6
7
8
| bool DeleteNode(LNode *p){
if(p==NULL) return false;
LNode *q =p->next;
p->data=p->next->data;
p->next=q->next;
free(q);
return true;
}
|
复杂度分析
- 时间复杂度：O(1)
- 空间复杂度：O(1)
按位查找
1
2
3
4
5
6
7
8
9
10
11
12
| LNode* GetElem(Linklist L,int i)
{
LNode *p=l;
int j=0;
p=L;
while(p!=null&&j<i)
{
p=p->next;
j++;
}
return p;
}
|
复杂度分析
- 时间复杂度：
- 最好情况：在头节点后插入元素-O(1)
- 最坏情况：在链表尾插入元素或i>L.length-O(N)
- 平均情况：在第n/2个节点插入-O(N)
- 空间复杂度：O(1)
按值查找
1
2
3
4
5
6
7
8
9
10
| LNode* LocalElem(Linklist L,ElemType e)
{
LNode *p;
p=L;
while(p!=null&&p->data!=e)
{
p=p->next;
}
return p;
}
|
复杂度分析
- 时间复杂度：
- 最好情况：在头节点后插入元素-O(1)
- 最坏情况：在链表尾插入元素或i>L.length-O(N)
- 平均情况：在第n/2个节点插入-O(N)
- 空间复杂度：O(1)
单链表的长度
1
2
3
4
5
6
7
8
9
10
11
| int Length(Linklist L)
{
int len=0;
LNode *p=L;
while(p->next!=NULL)
{
p=p->next;
len++;
}
return len;
}
|
复杂度分析
- 时间复杂度：O(N)
- 空间复杂度：O(1)
头插法建立单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| Linklist List_Headsert(Linklist &L)
{
LNode *s;
int x;
L=(Linklist)malloc(sizeof(LNode));
L->next=NULL;
scanf("%d",&x);
while(x!=9999)
{
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
s->next=L->next;
L->next=s;
scanf("%d",&x);
}
return L;
}
|
复杂度分析
- 时间复杂度：O(N)
- 空间复杂度：O(N)
尾插法建立单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| Linklist list_taiInsert(Linklist &L)
{
int x;
L=(Linklist)malloc(sizeof(LNode));
LNode *s,*r=L;
scanf("%d",&x);
while(x!=9999)
{
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
r-next=s;
r=s;
scanf("%d",&x);
}
r-next=NULL;
return L;
}
|
复杂度分析
- 时间复杂度：O(N)
- 空间复杂度：O(N)
应用场景：
