单链表

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

// 定义链表节点
typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode, *LinkList;

// 初始化链表
LinkList initList()
{
    LinkList head = (LinkList)malloc(sizeof(LNode));
    if (head == NULL)
    {
        printf("Memory allocation failed\n");
        exit(1);
    }
    head->next = NULL;
    return head;
}

// 头插法插入节点
void insertAtHead(LinkList head, int data)
{
    LNode *newNode = (LNode *)malloc(sizeof(LNode));
    if (newNode == NULL)
    {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = head->next;
    head->next = newNode;
}

// 尾插法插入节点
void insertAtTail(LinkList head, int data)
{
    LNode *newNode = (LNode *)malloc(sizeof(LNode));
    if (newNode == NULL)
    {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;

    LNode *p = head;
    while (p->next != NULL)
    {
        p = p->next;
    }
    p->next = newNode;
}

// 删除节点
void deleteNode(LinkList head, int data)
{
    LNode *p = head->next;
    LNode *pre = head;
    while (p != NULL && p->data != data)
    {
        pre = p;
        p = p->next;
    }
    if (p != NULL)
    {
        pre->next = p->next;
        free(p);
    }
    else
    {
        printf("Node with data %d not found\n", data);
    }
}

// 修改节点
void updateNode(LinkList head, int oldData, int newData)
{
    LNode *p = head->next;
    while (p != NULL && p->data != oldData)
    {
        p = p->next;
    }
    if (p != NULL)
    {
        p->data = newData;
    }
    else
    {
        printf("Node with data %d not found\n", oldData);
    }
}

// 查找节点
LNode *findNode(LinkList head, int data)
{
    LNode *p = head->next;
    while (p != NULL && p->data != data)
    {
        p = p->next;
    }
    return p;
}

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

int main()
{
    LinkList list = initList();

    insertAtHead(list, 3);
    insertAtHead(list, 2);
    insertAtHead(list, 1);
    printList(list);

    insertAtTail(list, 4);
    insertAtTail(list, 5);
    printList(list);

    deleteNode(list, 3);
    printList(list);

    updateNode(list, 2, 10);
    printList(list);

    LNode *node = findNode(list, 10);
    if (node != NULL)
    {
        printf("Node found with data %d\n", node->data);
    }
    else
    {
        printf("Node not found\n");
    }
    // 等待用户按键退出
    printf("Press any key to exit...\n");
    getchar();
    return 0;
}

循环链表

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

// 定义循环链表节点
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

// 初始化循环链表
LinkList initList() {
    LinkList head = (LinkList)malloc(sizeof(LNode));
    if (head == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    head->next = head; // 循环链表的头节点指向自己
    return head;
}

// 头插法插入节点
void insertAtHead(LinkList head, int data) {
    LNode *newNode = (LNode *)malloc(sizeof(LNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = head->next;
    head->next = newNode;
}

// 尾插法插入节点
void insertAtTail(LinkList head, int data) {
    LNode *newNode = (LNode *)malloc(sizeof(LNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    
    LNode *p = head;
    while (p->next != head) {
        p = p->next;
    }
    newNode->next = head;
    p->next = newNode;
}

// 删除节点
void deleteNode(LinkList head, int data) {
    LNode *p = head->next;
    LNode *pre = head;
    while (p != head && p->data != data) {
        pre = p;
        p = p->next;
    }
    if (p != head) {
        pre->next = p->next;
        free(p);
    } else {
        printf("Node with data %d not found\n", data);
    }
}

// 修改节点
void updateNode(LinkList head, int oldData, int newData) {
    LNode *p = head->next;
    while (p != head && p->data != oldData) {
        p = p->next;
    }
    if (p != head) {
        p->data = newData;
    } else {
        printf("Node with data %d not found\n", oldData);
    }
}

// 查找节点
LNode* findNode(LinkList head, int data) {
    LNode *p = head->next;
    while (p != head && p->data != data) {
        p = p->next;
    }
    return p != head ? p : NULL;
}

// 打印循环链表
void printList(LinkList head) {
    LNode *p = head->next;
    while (p != head) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("HEAD\n");
}

int main() {
    LinkList list = initList();

    insertAtHead(list, 3);
    insertAtHead(list, 2);
    insertAtHead(list, 1);
    printList(list);

    insertAtTail(list, 4);
    insertAtTail(list, 5);
    printList(list);

    deleteNode(list, 3);
    printList(list);

    updateNode(list, 2, 10);
    printList(list);

    LNode *node = findNode(list, 10);
    if (node != NULL) {
        printf("Node found with data %d\n", node->data);
    } else {
        printf("Node not found\n");
    }

    return 0;
}

双向链表

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

// 定义双向链表节点
typedef struct DLNode {
    int data;
    struct DLNode *left;
    struct DLNode *right;
} DLNode, *DLinkList;

// 初始化双向链表
DLinkList initList() {
    DLinkList head = (DLinkList)malloc(sizeof(DLNode));
    if (head == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    head->left = head->right = head;
    return head;
}

// 头插法插入节点
void insertAtHead(DLinkList head, int data) {
    DLNode *newNode = (DLNode *)malloc(sizeof(DLNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;

    newNode->right = head->right;
    head->right->left = newNode;
    head->right = newNode;
    newNode->left = head;
}

// 尾插法插入节点
void insertAtTail(DLinkList head, int data) {
    DLNode *newNode = (DLNode *)malloc(sizeof(DLNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;

    newNode->left = head->left;
    head->left->right = newNode;
    head->left = newNode;
    newNode->right = head;
}

// 删除节点
void deleteNode(DLinkList head, int data) {
    DLNode *p = head->right;
    while (p != head && p->data != data) {
        p = p->right;
    }
    if (p != head) {
        p->left->right = p->right;
        p->right->left = p->left;
        free(p);
    } else {
        printf("Node with data %d not found\n", data);
    }
}

// 修改节点
void updateNode(DLinkList head, int oldData, int newData) {
    DLNode *p = head->right;
    while (p != head && p->data != oldData) {
        p = p->right;
    }
    if (p != head) {
        p->data = newData;
    } else {
        printf("Node with data %d not found\n", oldData);
    }
}

// 查找节点
DLNode* findNode(DLinkList head, int data) {
    DLNode *p = head->right;
    while (p != head && p->data != data) {
        p = p->right;
    }
    return p != head ? p : NULL;
}

// 打印双向链表
void printList(DLinkList head) {
    DLNode *p = head->right;
    while (p != head) {
        printf("%d <-> ", p->data);
        p = p->right;
    }
    printf("HEAD\n");
}

int main() {
    DLinkList list = initList();

    insertAtHead(list, 3);
    insertAtHead(list, 2);
    insertAtHead(list, 1);
    printList(list);

    insertAtTail(list, 4);
    insertAtTail(list, 5);
    printList(list);

    deleteNode(list, 3);
    printList(list);

    updateNode(list, 2, 10);
    printList(list);

    DLNode *node = findNode(list, 10);
    if (node != NULL) {
        printf("Node found with data %d\n", node->data);
    } else {
        printf("Node not found\n");
    }

    return 0;
}

顺序存储和链式存储的比较

静态链表

链表的双指针技巧

从几个例子看这个技巧：

例子1:

例子2:

例子3:

后面这俩有缘再看吧

复杂链表的拷贝

跳跃表

参考资料：

朱允刚老师PPT

纯C语言完整代码操作单链表(初始化、插入、删除、查找...)_c语言单链表插入-CSDN博客