双向链表的创建、插入和删除、宏定义函数_双向链表如何删除

摘要：本文介绍双向链表的实现：创建、插入、删除，以及宏定义版本

所谓双链表即每个节点有两个指针：prev指向前一个节点，next指向后一个节点

struct node {
    int data;
    struct node *prev;
    struct node *next;
};

1
2
3
4
5
6

首先需要创建节点：

struct node* create_node(int data) {
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    if(newnode == NULL) {
        printf("内存分配失败")；
        exit(1);
    }
        
    newnode->prev = NULL;
    newnode->next = NULL;
    newnode->data = data;
    
    return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

对节点进行插入操作：

1.头插法

void insert(struct node **head, int data) {
    struct node *newnode = create_node(data);
    if (*head == NULL){
        *head = newnode;
        return;
    }
    newnode->next = *head;
    (*head)->prev = newnode;
    *head = newnode;
}
1
2
3
4
5
6
7
8
9
10

2.尾插法：

void insert(struct node **head, int data) {
    struct node *newnode = create_node(data);
    struct node *current = *head;
    if (current->next != NULL) {
        current = current->next;
    }
    current->next = newnode;
    newnode->prev = current;
}
1
2
3
4
5
6
7
8
9

删除一个节点：分为表头、表中、表尾

void delete(struct node**head, int data) {
    int status = 0;
    struct node *current = *head;
    while (current != NULL) {//从头节点遍历到最后一个节点
        if (current->data == data) {
            status = 1;//找到了
            break;
        }
        current = current->next;
    }
    if (!status) printf("未找到该数据所在节点\n");
    else {//节点在表尾
        if(current->next == NULL) {
            if (current->prev != NULL) // 先判断
            	current->prev->next = NULL;
            free(current);
        }
        else if(current->prev == NULL) {//*******节点在表头!需要修改*head！**********
            *head = current->next;
            if(current->next != NULL)
               current->next->prev = NULL;//考虑删除该节点为唯一的节点的情况
            free(current);
        }
        else{//节点在表中
            current->prev->next = current->next;
            current->next->prev = current->prev;
            free(current);
        }
        (current) = NULL; /* 将current置为NULL 避免悬空指针（悬空指针指向一个已经被释放的空间的地址，没有访问权限）*/
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

宏定义头插法： list是链表头指针，item是要插入的指针

#define LIST_INSERT(item, list) do {\
    if ((item) != NULL) {\
        (item)->prev = NULL;\
        if ((list) != NULL) {\
            (item)->next = (list);\
            (list)->prev = (item);\
        } else {\
            (item)->next = NULL;\
        }\
        (list) = (item);\ // 更新头指针
    }\
} while(0)
1
2
3
4
5
6
7
8
9
10
11
12

宏定义尾插法：

#define LIST_APPEND(item, list) do {\
    if ((item) != NULL) {\
        if ((list) == NULL) {\
            (list) = (item);\
            (item)->prev = NULL;\
        } else {\
            ListNode *temp = (list);\
            while (temp->next != NULL) {\
                temp = temp->next;\
            }\
            temp->next = (item);\
            (item)->prev = temp;\
        }\
        (item)->next = NULL;\ 
    }\
} while(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

宏定义删除节点： 提供要删除的指针，进行删除

#define LIST_REMOVE(item, list) do {\
    if ((item) != NULL) {\
        if ((item)->prev != NULL) (item)->prev->next = (item)->next;\
        if ((item)->next != NULL) (item)->next->prev = (item)->prev;\
        if ((list) == (item)) (list) = (item)->next;\
        (item)->prev = (item)->next = NULL;\
    }\
} while(0)
1
2
3
4
5
6
7
8
9

宏定义查找删除节点：根据节点的data数据，先查找后删除：

#define DELETE_NODE(head, data) do {\
    int status = 0;\
    struct node *current = *(head);\
    while (current != NULL) {\
        if (current->data == data) {\
            status = 1;\
            break;\
        }\
        current = current->next;\
    }\
    if (!status) {\
        printf("未找到该数据所在节点\n");\
    } else {\
        struct node *temp = current;\
        if (current->next == NULL) {\
            if (current->prev != NULL)\
                current->prev->next = NULL;\
            free(temp);\
        } else if (current->prev == NULL) {\
            *(head) = current->next;\
            current->next->prev = NULL;\
            free(temp);\
        } else {\
            current->prev->next = current->next;\
            current->next->prev = current->prev;\
            free(temp);\
        }\
        (current) = NULL; /* 将current置为NULL 避免悬空指针*/\
    }\
} while(0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31