1.双向链表

双向链表的节点分为3个部分：前驱指针域、数据域和后继指针域，可以用下图表示：

双向链表节点@2x.png

• 前驱指针域：用于存储该节点上一个节点的存储地址；
• 数据域：用于存储该节点的数据
• 后继指针域：用于存储该节点下一个节点存储地址；

双向链表的代码实现

1.1代码准备

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

typedef int Status;
typedef int ElemType;

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *prior;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

1.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++){
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->prior = NULL;
        temp->next = NULL;
        temp->data = I;

        p->next = temp;
        temp->prior = p;
        p = p->next;
        
    }
    
    return OK;
}

1.3双向链表的遍历

void display(LinkList L){
    
    LinkList temp = L->next;
    
    if(temp == NULL){
        printf("打印的双向链表为空!\n");
        return;
    }
    
    while (temp) {
        printf("%d  ",temp->data);
        temp = temp->next;
    }
    printf("\n");
    
}

1.4双向链表的插入

Status LinkListInsert(LinkList *L, int place, int num) {
    if (place < 1) return ERROR;
    LinkList temp = (LinkList)malloc(sizeof(Node));
    temp->prior = NULL;
    temp->next = NULL;
    temp->data = num;
    
    LinkList p = *L;
    for (int i = 1; i < place && p != NULL; i++) {
        p = p->next;
    }
    
    if (p == NULL) return ERROR;
    
    if (p->next == NULL) {
        p->next = temp;
        temp->prior = p;
    } else {
        temp->next = p->next;
        p->next->prior = temp;
        p->next = temp;
        temp->prior = p;
    }
    
    return OK;
}

1.5双向链表的删除

1.5.1 删除指定位置节点

Status ListDelete(LinkList *L, int i, ElemType *e){
    
    int k = 1;
    LinkList p = (*L);
    
    if (*L == NULL) {
        return ERROR;
    }
   
    while (k < i && p != NULL) {
        p = p->next;
        k++;
    }
    
    if (k>i || p == NULL) {
        return  ERROR;
    }
    
    LinkList delTemp = p->next;
    *e = delTemp->data;

    p->next = delTemp->next;

    if (delTemp->next != NULL) {
        delTemp->next->prior = p;
    }
    
    //7.删除delTemp结点
    free(delTemp);
    
    return OK;
    
}

1.5.2 删除指定内容节点

Status LinkListDeletVAL(LinkList *L, int data){
    LinkList p = *L;
    while (p) {
        if (p->data == data) {
            p->prior->next = p->next;
            if(p->next != NULL){
                p->next->prior = p->prior;
            }
            free(p);
            break;
        }
        p = p->next;
    }    
    return OK;    
}

1.6双向链表中查找元素

int selectElem(LinkList L,ElemType elem){\
    LinkList p = L->next;
    int i = 1;
    while (p) {
        if (p->data == elem) {
            return I;
        }
        I++;
        p = p->next;
    }
    return  -1;
}

1.7双向链表中更新节点

Status replaceLinkList(LinkList *L,int index,ElemType newElem){
    LinkList p = (*L)->next;
    for (int i = 1; i < index; i++) {
        p = p->next;
    }
    p->data = newElem;
    return OK;
}

2.双向循环列表

双向循环列表的特点是，列表头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点。

双向循环链表@2x.png

2.1双向循环链表的创建

Status creatLinkList(LinkList *L){
    
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) {
        return ERROR;
    }   
    (*L)->next = (*L);
    (*L)->prior = (*L);
    LinkList p = *L;
    for(int i=0; i < 10;i++){
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->data = i;
        p->next = temp;
        temp->prior = p;
        temp->next = (*L);
        p->prior = temp;
        p = p->next;  
    }
    return OK; 
}

2.2双向循环链表的遍历

Status Display(LinkList L){
    
    if (L == NULL) {
        printf("打印的双向循环链表为空!\n\n");
        return ERROR;
    }
    printf("双向循环链表内容:  ");
    
    LinkList p = L->next;
    while (p != L) {

        printf("%d  ",p->data);
        p = p->next;
    }
    printf("\n\n");
    return OK;
}

2.3双向循环链表的插入

Status LinkListInsert(LinkList *L, int index, ElemType e){
    LinkList p = (*L);
    int i = 1;
    if(*L == NULL) return ERROR;
    while (i < index && p->next != *L) {
        p = p->next;
        i++;
    }
    if (i > index)  return ERROR;
    LinkList temp = (LinkList)malloc(sizeof(Node));
    if (temp == NULL) return ERROR;
    temp->data = e;
    temp->prior = p;
    temp->next = p->next;
    p->next = temp;
    if (*L != temp->next) {
        temp->next->prior = temp;
    }else{
        (*L)->prior = temp;        
    }    
    return OK;
}

2.4双向循环链表的删除

Status LinkListDelete(LinkList *L,int index,ElemType *e){
    
    int i = 1;
    LinkList temp = (*L)->next;    
    if (*L == NULL) {
        return  ERROR;
    }
    if(temp->next == *L){
        free(*L);
        (*L) = NULL;
        return OK;
    }
    while (i < index) {
        temp = temp->next;
        i++;
    }
    *e = temp->data;
    temp->prior->next = temp->next;
    temp->next->prior = temp->prior;
    free(temp);
    return OK; 
}