C语言之链表详解

目录

一、链表定义

二、链表分类

三、链表操作

四、单向链表

1.链表定义

2.插入操作

3.删除操作

4.修改操作

5.查找操作

五、双向链表

1.链表定义

2.插入操作

3.删除操作

4.修改操作

5.查找操作

一、链表定义

        链表是一种基本的数据结构，它由一系列节点组成，每个节点包含一个值和指向下一个节点的指针。链表的特点是可以动态添加和删除节点，而不需要预先知道数据的数量。与数组不同，链表中的节点不一定是连续的存储空间，因此可以有效地利用内存空间。

二、链表分类

链表可以分为三种类型：

• 单向链表：每个节点只有一个指针指向下一个节点，最后一个节点的指针指向NULL。
• 双向链表：每个节点有两个指针，分别指向上一个节点和下一个节点，可以在O(1)时间内实现向前和向后遍历。
• 循环链表：在单向或双向链表的基础上，将最后一个节点的指针指向头节点，形成一个环。

三、链表操作

链表的操作包括插入、删除、查找、遍历等。

• 插入操作：可以在链表头或尾插入节点，也可以在指定位置插入节点。
• 删除操作：可以删除指定节点或按照值删除节点。
• 查找操作：可以查找指定节点或按照值查找节点。
• 遍历操作：可以遍历整个链表，输出每个节点的值或执行其他操作。

        链表的优点是可以动态添加和删除节点，因此非常适用于需要频繁插入和删除数据的场景。链表的缺点是访问操作的时间复杂度为O(n)，而且需要额外的空间存储节点的指针，因此在需要频繁访问数据的场景中，效率可能不如数组。

        链表在计算机科学中有广泛的应用，例如操作系统中的进程链表、文件系统中的目录链表、图论中的邻接表等。在C语言中，链表常常用于实现动态内存分配、函数调用栈、多项式运算等问题。

四、单向链表

        单向链表是由若干个节点组成的数据结构，每个节点包含两个部分：数据域和指针域。数据域存储节点的数据，指针域存储下一个节点的地址。

1.链表定义

单向链表定义如下：

struct ListNode {
    int val;
    struct ListNode* next;
};

2.插入操作

链表的插入操作可以在链表的头部、尾部或指定位置插入节点。具体实现如下：

// 在头部插入节点
struct ListNode* insertAtHead(struct ListNode* head, int val) {
    struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));
    new_node->val = val;
    new_node->next = head;
    return new_node;
}

// 在尾部插入节点
struct ListNode* insertAtTail(struct ListNode* head, int val) {
    struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));
    new_node->val = val;
    new_node->next = NULL;
    if (head == NULL) {
        return new_node;
    }
    struct ListNode* p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = new_node;

    return head;
}

// 在指定位置插入节点
struct ListNode* insertAtIndex(struct ListNode* head, int index, int val) {
    int i = 0;

    struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));
    new_node->val = val;
    if (index == 0) {
        new_node->next = head;
        return new_node;
    }
    struct ListNode* p = head;
    
    while (i < index - 1 && p != NULL) {
        p = p->next;
        i++;
    }
    if (p == NULL) {
        free(new_node);
        return head;
    }
    new_node->next = p->next;
    p->next = new_node;

    return head;
}

3.删除操作

链表的删除操作可以删除指定位置或指定值的节点。具体实现如下：

// 删除指定位置的节点
struct ListNode* deleteAtIndex(struct ListNode* head, int index) {
    int i = 0;
   
    if (head == NULL) {
        return NULL;
    }
    if (index == 0) {
        struct ListNode* temp = head;
        head = head->next;

        free(temp);
        return head;
    }
    struct ListNode* p = head;
    
    while (i < index - 1 && p != NULL) {
        p = p->next;
        i++;
    }

    if (p == NULL || p->next == NULL) {
        return head;
    }

    struct ListNode* temp = p->next;
    p->next = p->next->next;
    free(temp);

    return head;
}
// 删除指定值的节点
struct ListNode* deleteNode(struct ListNode* head, int val) {
    struct ListNode* p = head;
    struct ListNode* prev = NULL;

    while (p != NULL && p->val != val) {
        prev = p;
        p = p->next;
    }

    if (p == NULL) {
        return head;
    }

    if (prev == NULL) {
        head = head->next;
    } else {
        prev->next = p->next;
    }

    free(p);

    return head;
}

4.修改操作

链表的修改操作可以修改指定位置或指定值的节点的值。具体实现如下：

// 修改指定位置的节点的值
struct ListNode* modifyAtIndex(struct ListNode* head, int index, int val) {
    struct ListNode* p = head;
    int i = 0;

    while (i < index && p != NULL) {
        p = p->next;
        i++;
    }
    if (p == NULL) {
        return head;
    }
    p->val = val;

    return head;
}

// 修改指定值的节点的值
struct ListNode* modifyNode(struct ListNode* head, int old_val, int new_val) {
    struct ListNode* p = head;

    while (p != NULL && p->val != old_val) {
        p = p->next;
    }
    if (p == NULL) {
        return head;
    }
    p->val = new_val;

    return head;
}

5.查找操作

链表的查找操作可以查找指定位置或指定值的节点。具体实现如下：

// 查找指定位置的节点的值
int getValAtIndex(struct ListNode* head, int index) {
    struct ListNode* p = head;
    int i = 0;

    while (i < index && p != NULL) {
        p = p->next;
        i++;
    }
    if (p == NULL) {
        return -1;
    }

    return p->val;
}

// 查找指定值的节点的位置
int getIndexByVal(struct ListNode* head, int val) {
    struct ListNode* p = head;
    int i = 0;

    while (p != NULL && p->val != val) {
        p = p->next;
        i++;
    }
    if (p == NULL) {
        return -1;
    }

    return i;
}

        以上是链表的基本操作，实现时需要注意空指针和越界等问题。

五、双向链表

        双向链表和单向链表的不同在于每个节点有两个指针，分别指向前驱节点和后继节点。双向链表的优点是可以实现双向遍历和O(1)的删除操作，缺点是每个节点需要额外的一个指针。

 1.链表定义

双向链表定义如下：

struct ListNode {
    int val;
    struct ListNode* prev;
    struct ListNode* next;
};

2.插入操作

双向链表的插入操作可以在指定位置前面或后面插入节点，具体实现如下：

// 在指定位置前面插入节点
struct ListNode* insertBefore(struct ListNode* head, int index, int val) {
    struct ListNode* p = head;
    int i = 0;

    while (i < index && p != NULL) {
        p = p->next;
        i++;
    }
    if (p == NULL) {
        return head;
    }

    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->prev = p->prev;
    node->next = p;
    if (p->prev != NULL) {
        p->prev->next = node;
    } else {
        head = node;
    }
    p->prev = node;

    return head;
}

// 在指定位置后面插入节点
struct ListNode* insertAfter(struct ListNode* head, int index, int val) {
    struct ListNode* p = head;
    int i = 0;

    while (i < index && p != NULL) {
        p = p->next;
        i++;
    }
    if (p == NULL) {
        return head;
    }

    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->prev = p;
    node->next = p->next;
    if (p->next != NULL) {
        p->next->prev = node;
    }
    p->next = node;

    return head;
}

3.删除操作

双向链表的删除操作可以删除指定位置或指定值的节点，具体实现如下：

// 删除指定位置的节点
struct ListNode* deleteAtIndex(struct ListNode* head, int index) {
    struct ListNode* p = head;
    int i = 0;

    while (i < index && p != NULL) {
        p = p->next;
        i++;
    }
    if (p == NULL) {
        return head;
    }
    if (p->prev != NULL) {
        p->prev->next = p->next;
    } else {
        head = p->next;
    }
    if (p->next != NULL) {
        p->next->prev = p->prev;
    }
    free(p);

    return head;
}

// 删除指定值的节点
struct ListNode* deleteNode(struct ListNode* head, int val) {
    struct ListNode* p = head;

    while (p != NULL && p->val != val) {
        p = p->next;
    }
    if (p == NULL) {
        return head;
    }
    if (p->prev != NULL) {
        p->prev->next = p->next;
    } else {
        head = p->next;
    }
    if (p->next != NULL) {
        p->next->prev = p->prev;
    }
    free(p);

    return head;
}

4.修改操作

双向链表的修改操作可以直接修改指定节点的值，具体实现如下：

// 修改指定位置的节点值
struct ListNode* updateAtIndex(struct ListNode* head, int index, int val) {
    struct ListNode* p = head;
    int i = 0;

    while (i < index && p != NULL) {
        p = p->next;
        i++;
    }
    if (p == NULL) {
        return head;
    }
    p->val = val;

    return head;
}

5.查找操作

双向链表的查找操作可以按位置或按值查找，具体实现如下：

// 按位置查找节点
struct ListNode* getNodeAtIndex(struct ListNode* head, int index) {
    struct ListNode* p = head;
    int i = 0;

    while (i < index && p != NULL) {
        p = p->next;
        i++;
    }

    return p;
}

// 按值查找节点
struct ListNode* getNodeByValue(struct ListNode* head, int val) {
    struct ListNode* p = head;

    while (p != NULL && p->val != val) {
        p = p->next;
    }

    return p;
}

以上是双向链表的增删改查操作的实现，可以根据需要进行调用。需要注意的是，在使用完链表后要及时释放内存，避免内存泄漏。

        如果觉得文章写的还不错，麻烦点赞，收藏加关注哦​！

        关于更多嵌入式C语言、FreeRTOS、RT-Thread、Linux应用编程、linux驱动等相关知识，关注公众号【嵌入式Linux知识共享】，后续精彩内容及时收看了解。

 文章来源地址https://www.toymoban.com/news/detail-528636.html

到了这里，关于C语言之链表详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！