【数据结构-链表】链表的基本操作

编写插入函数和删除函数的思路：

• 先考虑一般情况；
• 再考虑在链表头部的操作；
• 最后考虑在链表尾部的操作。

1 单向链表

1.1 有头结点的单向链表

1.1.1 数据结构定义

typedef struct LinkNode{
    int data;
    LinkNode *next;
} *LinkNode, LinkList;
1
2
3
4

1.1.2 初始化建立链表

• 头插法：

LinkList InitList (LinkList &L){
    LinkNode *newNode, *head;
    int x;

    // 建立头结点
    head = (LinkList) malloc(sizeof(LinkList));
    head->next = NULL;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->next = head->next; // 新结点的指针域指向头结点的后继结点
        head->next = newNode; // 头结点的指针域指向新结点
    }
    
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 尾插法：

LinkList InitList (LinkList &L){
    LinkNode *newNode, *head, *tail;
    int x;

    // 建立头结点
    head = (LinkList) malloc(sizeof(LinkList));
    head->next = NULL;
    tail = head;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->next = NULL;
        tail->next = newNode; // 原先尾结点的指针域指向新结点
        tail = newNode; // 尾指针指向新结点
    }
    
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.1.3 按序号查找结点

LinkNode *GetNumNode (LinkList &L, int pos){
    LinkNode *findNode = L; // 初始指向头结点
    
    if (pos == 0) // 第 0 个结点即头结点
        return L;
    else if (pos < 0) // 必须为非负值
        return NULL;
    
    while ((findNode != NULL) && (pos != 0)){
        findNode = findNode->next;
        pos--;
    }
    return findNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.1.4 按值查找结点

LinkNode *GetDataNode (LinkList &L, const int x){
    LinkNode *findNode = L;
    
    while ((findNode != NULL) && (findNode->data != x))
        findNode = findNode->next;

    return findNode;
}
1
2
3
4
5
6
7
8

1.1.5 插入操作

• 新结点插入到第 pos 个位置上（找到其前驱结点即第 pos-1 个结点，进行后插操作）：

bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0) // 不能插在头结点的位置上
        return false;
    
    posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
    if (posPrev == NULL)
        return false;
    posNode = posPrev->next;
    
    newNode = (LinkNode *) malloc(sizeof(LinkNode));
    newNode->data = x;
    newNode->next = posNode; // 新结点的指针域指向原先第 pos 个结点
    posPrev->next = newNode; // 第 pos-1 个结点的指针域指向新结点
    
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 新结点插入到第 pos 个位置上（找到该结点即第 pos 个结点，进行伪前插操作，实质是新结点插入到第 pos 个结点的后面，然后交换数据域）：

bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posNext; // 记录第 pos+1 个结点
    
    if (pos <= 0) // 不能插在头结点的位置上
        return false;
    
    posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
    if (posNode == NULL)
        return false;
    posNext = posNode->next; // 记录第 pos+1 个结点
    
    newNode = (LinkNode *) malloc(sizeof(LinkNode));
    newNode->data = posNode->data; // 交换数据，posNode 变为新结点，newNode 变为旧结点
    newNode->next = posNext; 
    posNode->data = x;
    posNode->next = newNode; 
    
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.1.6 删除操作

• 删除第 pos 个结点（找到其前驱结点即第 pos-1 个结点）：

bool DeleteNode (LinkList &L, int pos){
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posNext; // 记录第 pos+1 个结点
    
    if (pos <= 0) // 不能删除头结点
        return false;
    
    posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
    if (posPrev == NULL)
        return false;
    posNode = posPrev->next; // 记录第 pos 个结点
    posNext = posNode->next; // 记录第 pos+1 个结点
    
    posPrev->next = posNext; // 第 pos-1 个结点的指针域指向原先第 pos 个结点的后继结点（即原先第 pos+1 个结点）
    free(posNode);
    
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 删除第 pos 个结点（找到该结点即第 pos 个结点，将其后继结点的值赋值给第 pos 个结点，然后删除其后继结点）：

bool DeleteNode (LinkList &L, int pos){
    LinkNode *posNext; // 记录第 pos+1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0) // 不能删除头结点
        return false;
    
    posNode = GetNode(L, pos); // 先找到第 pos 个结点
    if (posNode == NULL)
        return false;
    posNext = posNode->next; // 记录第 pos+1 个结点
    
    if (posNext != NULL){ // 如果第 pos 个结点不是最后一个结点
        posNode->data = posNext->data; // 将其后继结点的值赋值给第 pos 个结点
        posNode->next = posNext->next; // 更新指针域
        free(posNext);
    }
    else{ // 如果第 pos 个结点是最后一个结点
        free(posNode);
        前驱结点的指针域 = NULL; // 这里还是需要再遍历一遍链表找到前驱结点，比较麻烦
    }
    
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.2 无头结点的单向链表

1.2.1 数据结构定义

typedef struct LinkNode{
    int data;
    LinkNode *next;
} *LinkNode, LinkList;
1
2
3
4

1.2.2 初始化建立链表

• 头插法：

LinkList InitList (LinkList &L){
    LinkNode *newNode, *head;
    int x;

    // 建立第一个结点
    x = 读入数据;
    head = (LinkList) malloc(sizeof(LinkList));
    head->data = x;
    head->next = NULL;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->next = head;
        head = newNode; // 头指针指向新结点
        L = head; // 更新头指针（即链表的入口）
    }
    
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 尾插法：

LinkList InitList (LinkList &L){
    LinkNode *newNode, *head, *tail;
    int x;

    // 建立第一个结点
    x = 读入数据;
    head = (LinkList) malloc(sizeof(LinkList));
    head->data = x;
    head->next = NULL;
    tail = head;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->next = NULL;
        tail->next = newNode; // 原先尾结点的指针域指向新结点
        tail = newNode; // 尾指针指向新结点
    }
    
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.2.3 按序号查找结点

LinkNode *GetNumNode (LinkList &L, int pos){
    LinkNode *findNode = L; // 初始时指向链表头部
    
    if (pos < 1) // 必须为非负值
        return NULL;
    
    while ((findNode != NULL) && (pos != 0)){
        findNode = findNode->next;
        pos--;
    }
    return findNode;
}
1
2
3
4
5
6
7
8
9
10
11
12

1.2.4 按值查找结点

LinkNode *GetDataNode (LinkList &L, const int x){
    LinkNode *findNode = L; // 初始时指向链表头部
    
    while ((findNode != NULL) && (findNode->data != x))
        findNode = findNode->next;

    return findNode;
}
1
2
3
4
5
6
7
8

1.2.5 插入操作

• 新结点插入到第 pos 个位置上（找到其前驱结点即第 pos-1 个结点，进行后插操作）：

bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0) // 不能插在头结点的位置上
        return false;
    
    if (pos == 1){ // 如果要插入到第 1 个位置
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->next = L; // 指针域指向头结点
        L = newNode; // 更新头指针（即链表的入口）
    }
    else{
        posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
        if (posPrev == NULL)
            return false;
        posNode = posPrev->next; // 记录第 pos 个结点
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->next = posNode; // 新结点的指针域指向原先第 pos 个结点
        posPrev->next = newNode; // 第 pos-1 个结点的指针域指向新结点
    }
    
    return true;
}
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

• 新结点插入到第 pos 个位置上（找到该结点即第 pos 个结点，进行伪前插操作，实质是新结点插入到第 pos 个结点的后面，然后交换数据域）：

bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posNext; // 记录第 pos+1 个结点
    
    if (pos <= 0) // 不能插在头结点的位置上
        return false;
    
    posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
    if (posNode == NULL)
        return false;
    posNext = posNode->next;
    
    newNode = (LinkNode *) malloc(sizeof(LinkNode));
    newNode->data = posNode->data; // 交换数据，posNode 变为新结点，newNode 变为旧结点
    newNode->next = posNext; 
    posNode->data = x;
    posNode->next = newNode; 
    
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.2.6 删除操作

• 删除第 pos 个结点（找到其前驱结点即第 pos-1 个结点）：

bool DeleteNode (LinkList &L, int pos){
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posNext; // 记录第 pos+1 个结点
    
    if (pos <= 0)
        return false;
    
    if (pos == 1){ // 如果要删除第 1 个结点
        posNext = L->next; // 记录第 2 个结点
        free(L);
        L = posNext; // 头指针指向第 2 个结点
    }
    else{
        posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
        if (posPrev == NULL)
            return false;
        posNode = posPrev->next; // 记录第 pos 个结点
        posNext =  posNode->next; // 记录第 pos+1 个结点
        posPrev->next = posNext; // 第 pos-1 个结点的指针域指向原先第 pos 个结点的后继结点（即原先第 pos+1 个结点）
        free(posNode);
    }
    
    return true;
}
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

• 删除第 pos 个结点（找到该结点即第 pos 个结点，将其后继结点的值赋值给第 pos 个结点，然后删除其后继结点）：

bool DeleteNode (LinkList &L, int pos){
    LinkNode *posNext; // 记录第 pos+1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0)
        return false;
    
    posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
    if (posNode == NULL)
        return false;
    posNext = posNode->next; // 记录第 pos+1 个结点
    
    if (posNext != NULL){ // 如果第 pos 个结点不是最后一个结点
        posNode->data = posNext->data; // 将其后继结点的值赋值给第 pos 个结点
        posNode->next = posNext->next; // 更新指针域
        free(posNext);
    }
    else{ // 如果第 pos 个结点是最后一个结点
        free(posNode);
        前驱结点的指针域 = NULL; // 这里还是需要再遍历一遍链表找到前驱结点，比较麻烦
    }
    
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2 双向链表

2.1 有头结点的双向链表

2.1.1 数据结构定义

typedef struct LinkNode{
    int data;
    LinkNode *prev;
    LinkNode *next;
} *LinkNode, LinkList;
1
2
3
4
5

2.1.2 初始化建立链表

• 头插法：

LinkList InitList (LinkList &L){
    LinkNode *newNode, *head;
    int x;

    // 建立头结点
    head = (LinkList) malloc(sizeof(LinkList));
    head->prev = NULL;
    head->next = NULL;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = head;
        newNode->next = head->next; // 新结点的指针域指向头结点的后继结点
        head->next = newNode; // 头结点的指针域指向新结点
    }
    
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 尾插法：

LinkList InitList (LinkList &L){
    LinkNode *newNode, *head, *tail;
    int x;

    // 建立头结点
    head = (LinkList) malloc(sizeof(LinkList));
    head->prev = NULL;
    head->next = NULL;
    tail = head;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = tail;
        newNode->next = NULL;
        tail->next = newNode; // 原先尾结点的指针域指向新结点
        tail = newNode; // 尾指针指向新结点
    }
    
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.1.3 按序号查找结点

LinkNode *GetNumNode (LinkList &L, int pos){
    LinkNode *findNode = L; // 初始指向头结点
    
    if (pos == 0) // 第 0 个结点即头结点
        return L;
    else if (pos < 0) // 必须为非负值
        return NULL;
    
    while ((findNode != NULL) && (pos != 0)){
        findNode = findNode->next;
        pos--;
    }
    return findNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.1.4 按值查找结点

LinkNode *GetDataNode (LinkList &L, const int x){
    LinkNode *findNode = L;
    
    while ((findNode != NULL) && (findNode->data != x))
        findNode = findNode->next;

    return findNode;
}
1
2
3
4
5
6
7
8

2.1.5 插入操作

• 新结点插入到第 pos 个位置上（找到其前驱结点即第 pos-1 个结点，进行后插操作）：

bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0) // 不能插在头结点的位置上
        return false;
    
    posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
    if (posPrev == NULL)
        return false;
    posNode = posPrev->next; // 记录第 pos 个结点
    
    newNode = (LinkNode *) malloc(sizeof(LinkNode));
    newNode->data = x;
    newNode->prev = posPrev; // 新结点的前驱指针域指向第 pos-1 个结点
    newNode->next = posNode; // 新结点的后继指针域指向第 pos 个结点
    posPrev->next = newNode; // 第 pos-1 个结点的后继指针域指向新结点
    posNode->prev = newNode; // 第 pos 个结点的前驱指针域指向新结点
    
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 新结点插入到第 pos 个位置上（找到该结点即第 pos 个结点，进行前插操作）：

bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0) // 不能插在头结点的位置上
        return false;
    
    posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
    if (posNode == NULL)
        return false;
    posPrev = posNode->prev; // 记录第 pos-1 个结点
    
    newNode = (LinkNode *) malloc(sizeof(LinkNode));
    newNode->data = x;
    newNode->prev = posPrev; // 新结点的前驱指针域指向第 pos-1 个结点
    newNode->next = posNode; // 新结点的后继指针域指向第 pos 个结点
    posPrev->next = newNode; // 第 pos-1 个结点的后继指针域指向新结点
    posNode->prev = newNode; // 第 pos 个结点的前驱指针域指向新结点
    
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.1.6 删除操作

• 删除第 pos 个结点（找到其前驱结点即第 pos-1 个结点）：

bool DeleteNode (LinkList &L, int pos){
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posNext; // 记录第 pos+1 个结点
    
    if (pos <= 0) // 不能删除头结点
        return false;
    
    posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
    if (posPrev == NULL)
        return false;
    posNode = posPrev->next; // 记录第 pos 个结点
    posNext = posNode->next; // 记录第 pos+1 个结点
    posPrev->next = posNext; // 第 pos-1 个结点的后继指针域指向原先第 pos 个结点的后继结点（即原先第 pos+1 个结点）
    posNext->prev = posPrev; // 第 pos+1 个结点的前驱指针域指向原先第 pos 个结点的前驱结点（即原先第 pos-1 个结点）
    free(posNode);
    
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 删除第 pos 个结点（找到该结点即第 pos 个结点）：

bool DeleteNode (LinkList &L, int pos){
    LinkNode *posNext; // 记录第 pos+1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    
    if (pos <= 0) // 不能删除头结点
        return false;
    
    posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
    if (posNode == NULL)
        return false;
    posNext = posNode->next; // 记录第 pos+1 个结点
    posPrev = posNode->prev; // 记录第 pos-1 个结点
    
    if (posNext != NULL){ // 如果第 pos 个结点不是最后一个结点
        posPrev->next = posNext;
        posNext->prev = posPrev;
        free(posNode);
    }
    else{ // 如果第 pos 个结点是最后一个结点
        posPrev->next = NULL;
        free(posNode);
    }
    
    return true;
}
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

2.2 无头结点的双向链表

2.2.1 数据结构定义

typedef struct LinkNode{
    int data;
    LinkNode *prev;
    LinkNode *next;
} *LinkNode, LinkList;
1
2
3
4
5

2.2.2 初始化建立链表

• 头插法：

LinkList InitList (LinkList &L){
    LinkNode *newNode, *head;
    int x;

    // 建立第一个结点
    x = 读入数据;
    head = (LinkList) malloc(sizeof(LinkList));
    head->data = x;
    head->prev = NULL;
    head->next = NULL;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = NULL;
        newNode->next = head;
        head = newNode; // 头指针指向新结点
        L = head; // 更新头指针（即链表的入口）
    }
    
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 尾插法：

LinkList InitList (LinkList &L){
    LinkNode *newNode, *head, *tail;
    int x;

    // 建立第一个结点
    x = 读入数据;
    head = (LinkList) malloc(sizeof(LinkList));
    head->data = x;
    head->prev = NULL;
    head->next = NULL;
    tail = head;
    L = head;
    
    while (不符合终止条件){
        x = 读入数据;
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = tail;
        newNode->next = NULL;
        tail->next = newNode; // 原先尾结点的指针域指向新结点
        tail = newNode; // 尾指针指向新结点
    }
    
    return L;
}
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

2.2.3 按序号查找结点

LinkNode *GetNumNode (LinkList &L, int pos){
    LinkNode *findNode = L; // 初始时指向链表头部
    
    if (pos < 1) // 必须为非负值
        return NULL;
    
    while ((findNode != NULL) && (pos != 0)){
        findNode = findNode->next;
        pos--;
    }
    return findNode;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.2.4 按值查找结点

LinkNode *GetDataNode (LinkList &L, const int x){
    LinkNode *findNode = L; // 初始时指向链表头部
    
    while ((findNode != NULL) && (findNode->data != x))
        findNode = findNode->next;

    return findNode;
}
1
2
3
4
5
6
7
8

2.2.5 插入操作

• 新结点插入到第 pos 个位置上（找到其前驱结点即第 pos-1 个结点，进行后插操作）：

bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    
    if (pos <= 0) 
        return false;
    
    if (pos == 1){ // 如果要插入到第 1 个位置
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = NULL;
        newNode->next = L;
        L = newNode; // 更新头指针（即链表的入口）
    }
    else{
        posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
        if (posPrev == NULL)
            return false;
        posNode = posPrev->next; // 记录第 pos 个结点
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = posPrev; // 新结点的前驱指针域指向第 pos-1 个结点
        newNode->next = posNode; // 新结点的后继指针域指向第 pos 个结点
        posPrev->next = newNode; // 第 pos-1 个结点的后继指针域指向新结点
        posNode->prev = newNode; // 第 pos 个结点的前驱指针域指向新结点
    }
    
    return true;
}
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

• 新结点插入到第 pos 个位置上（找到该结点即第 pos 个结点，进行前插操作）：

bool InsertNode (LinkList &L, int pos, const int x){
    LinkNode *newNode; // 新结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posPrev; // 记录第 pos+1 个结点
    
    if (pos <= 0) 
        return false;
    
    if (pos == 1){ // 如果要插入到第 1 个位置
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = NULL;
        newNode->next = L;
        L = newNode; // 更新头指针（即链表的入口）
    }
    else{
        posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
        if (posPrev == NULL)
            return false;
        posPrev = posNode->prev; // 记录第 pos-1 个结点
        newNode = (LinkNode *) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->prev = posPrev; // 新结点的前驱指针域指向第 pos-1 个结点
        newNode->next = posNode; // 新结点的后继指针域指向第 pos 个结点
        posPrev->next = newNode; // 第 pos-1 个结点的后继指针域指向新结点
        posNode->prev = newNode; // 第 pos 个结点的前驱指针域指向新结点
    }
    
    return true;
}
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

2.2.6 删除操作

• 删除第 pos 个结点（找到其前驱结点即第 pos-1 个结点）：

bool DeleteNode (LinkList &L, int pos){
    LinkNode *posPrev; // 记录第 pos-1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posNext; // 记录第 pos+1 个结点
    
    if (pos <= 0) 
        return false;
    
    if (pos == 1){ // 如果要删除第 1 个结点
        posNext = L->next; // 记录第 2 个结点
        free(L);
        L = posNext; // 更新头指针（即链表的入口）
    }
    else{
        posPrev = GetNumNode(L, pos-1); // 先找到第 pos-1 个结点
        if (posPrev == NULL)
            return false;
        posNode = posPrev->next; // 记录第 pos 个结点
        posNext = posNode->next; // 记录第 pos+1 个结点
        posPrev->next = posNext; // 第 pos-1 个结点的后继指针域指向原先第 pos 个结点的后继结点（即原先第 pos+1 个结点）
        posNext->prev = posPrev; // 第 pos+1 个结点的前驱指针域指向原先第 pos 个结点的前驱结点（即原先第 pos-1 个结点）
        free(posNode);
    }
    
    return true;
}
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

• 删除第 pos 个结点（找到该结点即第 pos 个结点）：

bool DeleteNode (LinkList &L, int pos){
    LinkNode *posNext; // 记录第 pos+1 个结点
    LinkNode *posNode; // 记录第 pos 个结点
    LinkNode *posPrev; // 记录第 pos-1 个结点
    
    if (pos <= 0) 
        return false;
    
    if (pos == 1){ // 如果要删除第 1 个结点
        posNext = L->next; // 记录第 2 个结点
        free(L);
        L = posNext; // 更新头指针（即链表的入口）
    }
    else{
        posNode = GetNumNode(L, pos); // 先找到第 pos 个结点
        if (posNode == NULL)
            return false;
        posNext = posNode->next; // 记录第 pos+1 个结点
        posPrev = posNode->prev; // 记录第 pos-1 个结点
        
        if (posNext != NULL){ // 如果第 pos 个结点不是最后一个结点
            posPrev->next = posNext;
            posNext->prev = posPrev;
            free(posNode);
        }
        else{ // 如果第 pos 个结点是最后一个结点
            posPrev->next = NULL;
            free(posNode);
        }
    }
    
    return true;
}
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
33