王道数据结构精简笔记——双链表_王道双链表

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;		// 前驱和后继指针
}DNode, *DLinklist;
1
2
3
4

一、双链表的初始化（带头节点）

bool InitDLinkList(DLinklist &L){
    L = (DNode *) malloc(sizeof(DNode));		// 分配一个头节点
    if(L == NULL)
        return false;
    L -> prior = NULL;
    L -> next = NULL;
    return true;
}
1
2
3
4
5
6
7
8

二、双链表的插入

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

三、双链表的删除

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

四、双链表的遍历

// 后向遍历
while(p != NULL)
    p = p -> next;

// 前向遍历
while(p != NULL)
    p = p -> prior;

// 前向遍历（跳过头节点）
while(p -> prior != NULL)
    p = p -> prior;
1
2
3
4
5
6
7
8
9
10
11

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