单链表vs双链表–初篇

单链表对于某一结点前面的区域是未知的。即无法逆向检索，有时候不太方便

双链表则可以逆向检索，但是存储密度相比较稍微低一点。

双链表

初始化（带头结点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef struct DNode {
	Elemtype data;
	struct DNode* prior, * next;
}DNode,*DLinklist;
//初始化双链表
bool InitDLinklist(DLinklist& L) {
	L = (DNode*)malloc(sizeof(DNode));//分配一个头结点
	if (L == NULL)//内存不足 分配失败
		return false;
	L->prior = NULL;//头结点的prior永远指向NULL
	L->next = NULL;//头结点之后暂时还没有结点
	return true;
}
void testDLinklist() {
	DLinklist L;
	InitDLinklist(L);
}
//判断双链表是否为空 带头结点
bool Empty（DLinklist L){
    if(L->next==NULL)
        return true;
    else
        return false;
}

插入

修改指针时注意顺序

1
2
3
4
5
6
7
8
9
10
11
//后插
bool InsertNextDNode(DNode* p, DNode* s) {
	if (p==NULL||s==NULL)//非法参数
		return false;
	s->next = p->next;
	if (p->next != NULL)//如果p结点有后继节点
		p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
//删除p结点的后继结点
bool DeleteNextDNode(DNode* p) {
	if (p == NULL)
		return false;
	DNode* q = p->next;//找到p的后继节点給q
	if (q == NULL)//p没有后继节点
		return false;
	p->next = q ->next;
	if (q->next != NULL)//判断q是不是最后一个结点
		q->next->prior = p;
	free(q);//释放q
	return true;
}

此时若要销毁这个双链表，只需找到头结点，然后循环删除后继节点即可。

1
2
3
4
5
6
7
void DestroyList(DLinklist& L) {
	//循环释放各个数据节点
	while (L->next != NULL)
		DeleteNextDNode(L);
	free(L);//释放L
	L = NULL;//使头指针指向NULL
}

遍历

后向遍历

1
2
3
4
while(p!==NULL){
	//对结点p做相应处理，例如打印p
    p=p->next;
}

前向遍历

1
2
3
4
while(p!==NULL){
	//对结点p做相应处理，例如打印p
    p=p->prior;
}

跳过头结点的前向便利

1
2
3
4
while(p->prior!=NULL){
    //对结点p做相应处理，例如打印p
    p=p->prior;
}

双链表不可以随机存取，按位查找，按值查找都只能用遍历的方式实现。时间复杂度为O(n)