【数据结构C/C++】单向链表的增删改查

单向链表是比较常用的数据结构，最近再面试手撕算法的时候偶尔有遇到，所以就花了一点时间简单的写了一下C/C++版本的单向链表的代码。
这里我推荐使用C++版本，因为C++版本我特地优化了一下，提供了用户输入的功能，当然两个语言差异不大，注释可以直接看C版本的，比较容易理解。
对于这种比较容易理解的数据机构我就不会再次附上我对这个结构的理解了，
直接show u my code。

C

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构
struct Node {
    int data;
    struct Node* next;
};

// 初始化链表
struct Node* initializeList() {
    return NULL; // 返回一个空链表
}

// 在链表尾部插入节点
struct Node* insertAtEnd(struct Node* head, int data) {
    //先申请并开辟空间
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL) {
        return newNode; // 如果链表为空，新节点成为链表头
    }

    struct Node* current = head;
    while (current->next != NULL) {
        current = current->next; // 移动到链表末尾
    }

    current->next = newNode;
    return head;
}

// 在链表头部插入节点
struct Node* insertAtBeginning(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = head;
    return newNode; // 新节点成为链表头
}

// 删除节点
struct Node* deleteNode(struct Node* head, int data) {
    if (head == NULL) {
        return NULL; // 空链表，无需删除
    }
    //要删除的数据就是链表头节点
    if (head->data == data) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
        return head; // 删除链表头节点
    }
    //要删除的数据不是链表头节点 从链表头下一个结点开始寻找要删除的数据
    struct Node* current = head;
    while (current->next != NULL && current->next->data != data) {
        current = current->next;
    }
    //停止时存在条件1：没有找到要删除的 2：cur-next-data是要删除的数据
    if (current->next != NULL) {
        struct Node* temp = current->next; //temp就是要删除的数据
        current->next = current->next->next;
        free(temp); // 删除中间或末尾节点
    }

    return head;
}

// 查找节点
struct Node* searchNode(struct Node* head, int data) {
    struct Node* current = head;
    while (current != NULL) {
        if (current->data == data) {
            return current; // 找到匹配的节点
        }
        current = current->next;
    }
    return NULL; // 未找到匹配的节点
}

// 修改节点的数据
void modifyNode(struct Node* head, int oldData, int newData) {
    struct Node* nodeToModify = searchNode(head, oldData);
    if (nodeToModify != NULL) {
        nodeToModify->data = newData; // 修改节点的数据
    }
}

// 打印链表
void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 释放链表内存
void freeList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        struct Node* temp = current;
        current = current->next;
        free(temp);
    }
}

int main() {
    struct Node* list = initializeList();

    list = insertAtEnd(list, 10);
    list = insertAtEnd(list, 20);
    list = insertAtBeginning(list, 5);

    printf("Original List: ");
    printList(list);

    modifyNode(list, 20, 25);
    printf("Modified List: ");
    printList(list);

    list = deleteNode(list, 10);
    printf("List after deleting 10: ");
    printList(list);

    struct Node* foundNode = searchNode(list, 5);
    if (foundNode != NULL) {
        printf("Found node with data 5\n");
    } else {
        printf("Node with data 5 not found\n");
    }

    freeList(list); // 释放链表内存

    return 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

C++

#include 

class Node {
public:
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;

    LinkedList() : head(nullptr) {}

    // 插入节点到链表尾部
    void insertAtEnd(int val) {
        Node* newNode = new Node(val);
        if (head == nullptr) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // 删除节点
    void deleteNode(int val) {
        if (head == nullptr) {
            return; // 空链表，无需删除
        }

        if (head->data == val) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        Node* current = head;
        while (current->next != nullptr && current->next->data != val) {
            current = current->next;
        }

        if (current->next != nullptr) {
            Node* temp = current->next;
            current->next = current->next->next;
            delete temp;
        }
    }

    // 查找节点
    Node* searchNode(int val) {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == val) {
                return current; // 找到匹配的节点
            }
            current = current->next;
        }
        return nullptr; // 未找到匹配的节点
    }

    // 修改节点的数据
    void modifyNode(int oldVal, int newVal) {
        Node* nodeToModify = searchNode(oldVal);
        if (nodeToModify != nullptr) {
            nodeToModify->data = newVal; // 修改节点的数据
        }
    }

    // 打印链表
    void printList() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }

    // 释放链表内存
    ~LinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* temp = current;
            current = current->next;
            delete temp;
        }
    }
};

int main() {
    LinkedList list;
    int choice, data, oldData, newData;

    while (true) {
        std::cout << "\nMenu:\n";
        std::cout << "1. Insert at the end\n";
        std::cout << "2. Delete node\n";
        std::cout << "3. Search node\n";
        std::cout << "4. Modify node\n";
        std::cout << "5. Print list\n";
        std::cout << "6. Exit\n";
        std::cout << "Enter your choice: ";
        std::cin >> choice;

        switch (choice) {
            case 1:
                std::cout << "Enter data to insert: ";
                std::cin >> data;
                list.insertAtEnd(data);
                break;
            case 2:
                std::cout << "Enter data to delete: ";
                std::cin >> data;
                list.deleteNode(data);
                break;
            case 3:
                std::cout << "Enter data to search: ";
                std::cin >> data;
                if (list.searchNode(data) != nullptr) {
                    std::cout << "Found node with data " << data << std::endl;
                } else {
                    std::cout << "Node with data " << data << " not found" << std::endl;
                }
                break;
            case 4:
                std::cout << "Enter data to modify: ";
                std::cin >> oldData;
                std::cout << "Enter new data: ";
                std::cin >> newData;
                list.modifyNode(oldData, newData);
                break;
            case 5:
                std::cout << "List: ";
                list.printList();
                break;
            case 6:
                return 0;
            default:
                std::cout << "Invalid choice! Please try again." << std::endl;
        }
    }

    return 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

408考研各数据结构C/C++代码（Continually updating）

408考研各数据结构C/C++代码（Continually updating）
这个模块是我应一些朋友的需求，希望我能开一个专栏，专门提供考研408中各种常用的数据结构的代码，并且希望我附上比较完整的注释以及提供用户输入功能，ok，fine，这个专栏会一直更新，直到我认为没有新的数据结构可以讲解了。
目前我比较熟悉的数据结构如下：
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。
所以我会先有空更新出如下几个数据结构的代码，欢迎关注。 当然，在我前两年的博客中，对于链表、哈夫曼树等常用数据结构，我都提供了比较完整的详细的实现以及思路讲解，有兴趣可以去考古。