数据结构之链表（算法之初）

首先脑补一下单向链表和双向链表：

• 单向链表（C语言实现）：

  • 每个节点只包含一个指向下一个节点的指针。
  • 只能从头节点开始向后遍历，无法回溯。

• 双向链表（C++实现）：

  • 每个节点包含两个指针，一个指向下一个节点，一个指向前一个节点。
  • 可以在链表中前后遍历，增加了操作的灵活性。

下面是具体的代码展示，通过代码展示如何操作，我就不写注释了，完全的代码附上，都用了标准的变量和函数命名，方便大家阅读，希望大家能在标准代码中更深入的理解链表难关，大家也可以把代码复制下来在自己电脑运行和修改，最后，祝大家能够有所收获！

C语言实现单向链表

1. 定义节点结构和链表初始化

#include <stdio.h>
#include <stdlib.h>
 
typedef struct ListNode {
    int value;
    struct ListNode *next;
} ListNode;
 
ListNode* create_node(int value) {
    ListNode *new_node = (ListNode*)malloc(sizeof(ListNode));
    new_node->value = value;
    new_node->next = NULL;
    return new_node;
}
#include <stdio.h>
#include <stdlib.h>
 
typedef struct ListNode {
    int value;
    struct ListNode *next;
} ListNode;
 
ListNode* create_node(int value) {
    ListNode *new_node = (ListNode*)malloc(sizeof(ListNode));
    new_node->value = value;
    new_node->next = NULL;
    return new_node;
}

2. 插入节点（头插法和尾插法）

void insert_at_beginning(ListNode **head, int value) {
    ListNode *new_node = create_node(value);
    new_node->next = *head;
    *head = new_node;
}
 
void insert_at_end(ListNode **head, int value) {
    ListNode *new_node = create_node(value);
    if (*head == NULL) {
        *head = new_node;
        return;
    }
    ListNode *temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = new_node;
}

3. 删除节点和查找节点

void delete_node(ListNode **head, int key) {
    ListNode *temp = *head, *prev = NULL;
    if (temp != NULL && temp->value == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->value != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}
 
int search(ListNode *head, int key) {
    ListNode *current = head;
    while (current != NULL) {
        if (current->value == key) return 1;
        current = current->next;
    }
    return 0;
}

4. 打印链表

void print_list(ListNode *head) {
    ListNode *current = head;
    while (current != NULL) {
        printf("%d -> ", current->value);
        current = current->next;
    }
    printf("NULL\n");
}
 
int main() {
    ListNode *head = NULL;
    insert_at_beginning(&head, 3);
    insert_at_beginning(&head, 2);
    insert_at_end(&head, 4);
    print_list(head);  // 输出: 2 -> 3 -> 4 -> NULL
    printf("%d\n", search(head, 3));  // 输出: 1
    delete_node(&head, 3);
    print_list(head);  // 输出: 2 -> 4 -> NULL
    return 0;
}

C++实现双向链表

1. 定义节点结构和链表初始化

#include <iostream>
 
struct DoubleListNode {
    int value;
    DoubleListNode* next;
    DoubleListNode* prev;
    DoubleListNode(int val) : value(val), next(nullptr), prev(nullptr) {}
};
 
class DoublyLinkedList {
public:
    DoublyLinkedList() : head(nullptr) {}
    void insert_at_beginning(int value);
    void insert_at_end(int value);
    void delete_node(int key);
    bool search(int key);
    void print_list();
private:
    DoubleListNode* head;
};

2. 插入节点（头插法和尾插法） 

void DoublyLinkedList::insert_at_beginning(int value) {
    DoubleListNode* new_node = new DoubleListNode(value);
    new_node->next = head;
    if (head != nullptr) head->prev = new_node;
    head = new_node;
}
 
void DoublyLinkedList::insert_at_end(int value) {
    DoubleListNode* new_node = new DoubleListNode(value);
    if (head == nullptr) {
        head = new_node;
        return;
    }
    DoubleListNode* temp = head;
    while (temp->next != nullptr) temp = temp->next;
    temp->next = new_node;
    new_node->prev = temp;
}

3. 删除节点和查找节点

void DoublyLinkedList::delete_node(int key) {
    DoubleListNode* temp = head;
    while (temp != nullptr && temp->value != key) {
        temp = temp->next;
    }
    if (temp == nullptr) return;
    if (temp->prev != nullptr) temp->prev->next = temp->next;
    else head = temp->next;
    if (temp->next != nullptr) temp->next->prev = temp->prev;
    delete temp;
}
 
bool DoublyLinkedList::search(int key) {
    DoubleListNode* current = head;
    while (current != nullptr) {
        if (current->value == key) return true;
        current = current->next;
    }
    return false;
}

4. 打印链表

void DoublyLinkedList::print_list() {
    DoubleListNode* current = head;
    while (current != nullptr) {
        std::cout << current->value << " <-> ";
        current = current->next;
    }
    std::cout << "NULL" << std::endl;
}
 
int main() {
    DoublyLinkedList dll;
    dll.insert_at_beginning(3);
    dll.insert_at_beginning(2);
    dll.insert_at_end(4);
    dll.print_list();  // 输出: 2 <-> 3 <-> 4 <-> NULL
    std::cout << dll.search(3) << std::endl;  // 输出: 1
    dll.delete_node(3);
    dll.print_list();  // 输出: 2 <-> 4 <-> NULL
    return 0;
}