双向链表

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

双线链表的结点.png

双向链表.png

1.双链表的结构

/* 双向链表的结构 */
typedef struct List{
    int data;           //  数据域
    struct List *next;      //  向后的指针
    struct List *front;     //  向前的指针
};

2.双向链表的创建

代码实现如下

Status createLinkList(LinkList *L){
    
    //*L 指向头结点
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    
    (*L)->prior = NULL;
    (*L)->next = NULL;
    (*L)->data = -1;
    
    //新增数据
    LinkList p = *L;
    for(int i=0; i < 10;i++){
        
        //1.创建1个临时的结点
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->prior = NULL;
        temp->next = NULL;
        temp->data = i;
        
        //2.为新增的结点建立双向链表关系
        //① temp 是p的后继
        p->next = temp;
        //② temp 的前驱是p
        temp->prior = p;
        //③ p 要记录最后的结点的位置,方便下一次插入
        p = p->next;
        
    }
    
    return OK;
}

结果输出

创建双向链表成功.png

3.双向链表的插入

首先我们来画图看看双向链表的插入过程：

双向链表的插入流程.png

第一步：首先找到插入位置，节点 T 将插入到P结点后面
第二步：将节点P-next 的前驱指向节点T，即 P->next->prior = T;
第三步：将节点 T 的后继指向节点P->next 即 T->next = P->next;
第四步：将节点 P 的后继指向节点 T 即 P->next = T;
第五步：将节点T 的前驱指向节点 P 即 T->prior = P;

代码实现如下

Status InsertLinkList(LinkList *L,int place,int num){
    
    //1.插入的位置不合法 为0或者复述
    if (place < 1) return ERROR;
    
    //2.新建结点
    LinkList temp = (LinkList)malloc(sizeof(Node));
    temp->next = NULL;
    temp->prior = NULL;
    temp->data = num;
    
    //3.将p指向头结点
    LinkList p = *L;
    
    //4.找到插入位置place的结点
    for (int i = 1; i< place; i++) {
        p = p->next;
    }
    
    //5.如果插入的位置超过链表本身的长度
    if (p == NULL)  return ERROR ;
    
    //6.判断插入的位置是否为链表的尾部(p的后驱指针式NULL)
    if (p->next == NULL) {
        p->next = temp;
        temp->prior = p;
    }else{
        // 如果不在链表的尾部
        //1.将p->next结点的前驱指向插入结点（temp）
        p->next->prior = temp;
        
        //2.将tem的next只想 p的next的指向
        temp->next = p->next;
        
        // 3.p->next指向temp
        p->next = temp;
        
        // 4.temp的前驱指向p
        temp->prior = p;
     }
    return OK;
}

结果输出

双向链表的插入结果.png

这里需要注意处理当插入的位置在末位时候的情况,尾结点p的后继指向新插入的结点(p->next = temp)，新插入的结点的前驱指向尾结点(temp->prior = p);

4.双线链表的删除

双向链表的结点删除.png

第一步：首先找到删除结点Del
第二步：将节点Del->prior->next 的后继指向节点Del->next，即 Del->prior->next = Del->next;
第三步：将节点 Del->next 的前驱指向节点p 即 Del->next->prior = Del->prior;
第四步：释放结点Del

代码实现如下

Status ListDelete(LinkList *L,int place){
    int k = 1;
    
    LinkList p = (*L);
    
    //1.判断双向链表是否为空
    if (*L == NULL) return ERROR;
    
    //2.将指针p移动到删除元素的前一个位置
    while (k< place && p != NULL) {
        p = p->next;
        k++;
    }
    
    //3.如果k>place 或者p == NULL 则返回ERROR
    if (k > place || p == NULL) return ERROR;
    
    //4.创建临时指针delTemp 指向要删除的结点
    LinkList delTemp = p->next;
    
    //5.p-next 等于要删除的结点的下一个结点
    p->next = delTemp->next;
    
    //6.如果删除结点的下一个结点不为空 则将简要删除的下一个结点的前驱指针赋值p
    if (delTemp->next != NULL) {
        delTemp->next->prior = p;
    }
    
    return OK;
}

结果输出

删除双向链表结点成功.png

5.查找某个元素的位置

代码实现如下

int serachData(LinkList L,int value){
    if (L == NULL) return -1;
    LinkList p = L->next;
    int i = 1;
    while (p) {
        if (p->data == value) {
            return i;
        }
        i++;
        p = p->next;
    }
    
    return -1;
}

结果输出

查询双向链表的位置.png

6.循环双向链表的操作

循环双向链表可以结合双向链表和单向循环链表的处理逻辑来进行操作，这里不再做逻辑和代码实现。