1. 双链表的定义

双链表也是链表的一种。双链表的每个数据节点中都有两个指针，分别指向前驱节点和后继结点。

结构体如下：

typedef struct DNode{            //定义双链表结点类型 
    ElemType data;               //数据域    
    struct DNode *prior, *next;  //前驱和后继指针
}DNode, *DLinklist;
1
2
3
4

大写的’D’ 就是double的意思
DLinklist 等价于 DNode*
DLinklist 侧重于双链表的意思
DNode* 侧重于指针的意思

---

2. 双链表的初始化 (带头结点) ：InitDLinkList(Dlinklist &L)

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);       
    ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

3. 判断双链表是否为空：Empty(DLinklist L)

bool Empty(DLinklist L){   
    if(L->next == NULL)   
        return true;      
    else             
        return false;
}
1
2
3
4
5
6

---

4. 双链表的后插：InsertNextDNode(DNode *p, DNode *s)

1、2步骤可互换 3、4步骤可互换
但1、2步 必须在 3、4步 前面

 

typedef struct DNode{     
    ElemType data;       
    struct DNode *prior, *next;
}DNode, *DLinklist;

// 将结点s插入到结点p之后
bool InsertNextDNode(DNode *p, DNode *s){ 
    if(p==NULL || s==NULL)  
        return false;      
           
    s->next = p->next;      
    // 判断结点p之后是否有后继结点  
    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
12
13
14
15
16
17
18

双链表的前插操作、按位序插入操作都可以转换成后插操作

---

5. 双链表的删除下一个结点 ：DeletNextDNode(DNode *p)

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

---

6. 销毁一个双链表：DestoryList(DLinklist &L)

bool DestoryList(DLinklist &L){ 
    // 循环释放各个数据结点   
    while(L->next != NULL) 
        DeletNextDNode(L);   
        
    //销毁表时，才能删除头结点   
     free(L);        
     // 头指针置空  
     L=NULL;     
}
1
2
3
4
5
6
7
8
9
10

---

7. 双链表的遍历

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。