devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C语言之链表详解_c 链表

作者：知新_RL | 2024-07-10 16:45:45

赞

踩

c 链表

目录

一、链表定义

二、链表分类

三、链表操作

四、单向链表

1.链表定义

2.插入操作

3.删除操作

4.修改操作

5.查找操作

五、双向链表

1.链表定义

2.插入操作

3.删除操作

4.修改操作

5.查找操作

一、链表定义

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

二、链表分类

链表可以分为三种类型：

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

三、链表操作

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

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

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

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

四、单向链表

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

413c6e745fc63630140e7364e5c3bcf4.jpeg

1.链表定义

单向链表定义如下：

  1. struct ListNode {
  2.     int val;
  3.     struct ListNode* next;
  4. };

2.插入操作

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

  1. // 在头部插入节点
  2. struct ListNode* insertAtHead(struct ListNode* head, int val) {
  3.     struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));
  4.     new_node->val = val;
  5.     new_node->next = head;
  6.     return new_node;
  7. }
  8.  
  9. // 在尾部插入节点
  10. struct ListNode* insertAtTail(struct ListNode* head, int val) {
  11.     struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));
  12.     new_node->val = val;
  13.     new_node->next = NULL;
  14.     if (head == NULL) {
  15.         return new_node;
  16.     }
  17.     struct ListNode* p = head;
  18.     while (p->next != NULL) {
  19.         p = p->next;
  20.     }
  21.     p->next = new_node;
  22.  
  23.     return head;
  24. }
  25.  
  26. // 在指定位置插入节点
  27. struct ListNode* insertAtIndex(struct ListNode* head, int index, int val) {
  28.     int i = 0;
  29.  
  30.     struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));
  31.     new_node->val = val;
  32.     if (index == 0) {
  33.         new_node->next = head;
  34.         return new_node;
  35.     }
  36.     struct ListNode* p = head;
  37.     
  38.     while (i < index - 1 && p != NULL) {
  39.         p = p->next;
  40.         i++;
  41.     }
  42.     if (p == NULL) {
  43.         free(new_node);
  44.         return head;
  45.     }
  46.     new_node->next = p->next;
  47.     p->next = new_node;
  48.  
  49.     return head;
  50. }

3.删除操作

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

  1. // 删除指定位置的节点
  2. struct ListNode* deleteAtIndex(struct ListNode* head, int index) {
  3.     int i = 0;
  4.    
  5.     if (head == NULL) {
  6.         return NULL;
  7.     }
  8.     if (index == 0) {
  9.         struct ListNode* temp = head;
  10.         head = head->next;
  11.  
  12.         free(temp);
  13.         return head;
  14.     }
  15.     struct ListNode* p = head;
  16.     
  17.     while (i < index - 1 && p != NULL) {
  18.         p = p->next;
  19.         i++;
  20.     }
  21.  
  22.     if (p == NULL || p->next == NULL) {
  23.         return head;
  24.     }
  25.  
  26.     struct ListNode* temp = p->next;
  27.     p->next = p->next->next;
  28.     free(temp);
  29.  
  30.     return head;
  31. }
  32. // 删除指定值的节点
  33. struct ListNode* deleteNode(struct ListNode* head, int val) {
  34.     struct ListNode* p = head;
  35.     struct ListNode* prev = NULL;
  36.  
  37.     while (p != NULL && p->val != val) {
  38.         prev = p;
  39.         p = p->next;
  40.     }
  41.  
  42.     if (p == NULL) {
  43.         return head;
  44.     }
  45.  
  46.     if (prev == NULL) {
  47.         head = head->next;
  48.     } else {
  49.         prev->next = p->next;
  50.     }
  51.  
  52.     free(p);
  53.  
  54.     return head;
  55. }

4.修改操作

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

  1. // 修改指定位置的节点的值
  2. struct ListNode* modifyAtIndex(struct ListNode* head, int index, int val) {
  3.     struct ListNode* p = head;
  4.     int i = 0;
  5.  
  6.     while (i < index && p != NULL) {
  7.         p = p->next;
  8.         i++;
  9.     }
  10.     if (p == NULL) {
  11.         return head;
  12.     }
  13.     p->val = val;
  14.  
  15.     return head;
  16. }
  17.  
  18. // 修改指定值的节点的值
  19. struct ListNode* modifyNode(struct ListNode* head, int old_val, int new_val) {
  20.     struct ListNode* p = head;
  21.  
  22.     while (p != NULL && p->val != old_val) {
  23.         p = p->next;
  24.     }
  25.     if (p == NULL) {
  26.         return head;
  27.     }
  28.     p->val = new_val;
  29.  
  30.     return head;
  31. }

5.查找操作

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

  1. // 查找指定位置的节点的值
  2. int getValAtIndex(struct ListNode* head, int index) {
  3.     struct ListNode* p = head;
  4.     int i = 0;
  5.  
  6.     while (i < index && p != NULL) {
  7.         p = p->next;
  8.         i++;
  9.     }
  10.     if (p == NULL) {
  11.         return -1;
  12.     }
  13.  
  14.     return p->val;
  15. }
  16.  
  17. // 查找指定值的节点的位置
  18. int getIndexByVal(struct ListNode* head, int val) {
  19.     struct ListNode* p = head;
  20.     int i = 0;
  21.  
  22.     while (p != NULL && p->val != val) {
  23.         p = p->next;
  24.         i++;
  25.     }
  26.     if (p == NULL) {
  27.         return -1;
  28.     }
  29.  
  30.     return i;
  31. }

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

五、双向链表

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

20200726124645552.png

 1.链表定义

双向链表定义如下：

  1. struct ListNode {
  2.     int val;
  3.     struct ListNode* prev;
  4.     struct ListNode* next;
  5. };

2.插入操作

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

  1. // 在指定位置前面插入节点
  2. struct ListNode* insertBefore(struct ListNode* head, int index, int val) {
  3.     struct ListNode* p = head;
  4.     int i = 0;
  5.  
  6.     while (i < index && p != NULL) {
  7.         p = p->next;
  8.         i++;
  9.     }
  10.     if (p == NULL) {
  11.         return head;
  12.     }
  13.  
  14.     struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
  15.     node->val = val;
  16.     node->prev = p->prev;
  17.     node->next = p;
  18.     if (p->prev != NULL) {
  19.         p->prev->next = node;
  20.     } else {
  21.         head = node;
  22.     }
  23.     p->prev = node;
  24.  
  25.     return head;
  26. }
  27.  
  28. // 在指定位置后面插入节点
  29. struct ListNode* insertAfter(struct ListNode* head, int index, int val) {
  30.     struct ListNode* p = head;
  31.     int i = 0;
  32.  
  33.     while (i < index && p != NULL) {
  34.         p = p->next;
  35.         i++;
  36.     }
  37.     if (p == NULL) {
  38.         return head;
  39.     }
  40.  
  41.     struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
  42.     node->val = val;
  43.     node->prev = p;
  44.     node->next = p->next;
  45.     if (p->next != NULL) {
  46.         p->next->prev = node;
  47.     }
  48.     p->next = node;
  49.  
  50.     return head;
  51. }

3.删除操作

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

  1. // 删除指定位置的节点
  2. struct ListNode* deleteAtIndex(struct ListNode* head, int index) {
  3.     struct ListNode* p = head;
  4.     int i = 0;
  5.  
  6.     while (i < index && p != NULL) {
  7.         p = p->next;
  8.         i++;
  9.     }
  10.     if (p == NULL) {
  11.         return head;
  12.     }
  13.     if (p->prev != NULL) {
  14.         p->prev->next = p->next;
  15.     } else {
  16.         head = p->next;
  17.     }
  18.     if (p->next != NULL) {
  19.         p->next->prev = p->prev;
  20.     }
  21.     free(p);
  22.  
  23.     return head;
  24. }
  25.  
  26. // 删除指定值的节点
  27. struct ListNode* deleteNode(struct ListNode* head, int val) {
  28.     struct ListNode* p = head;
  29.  
  30.     while (p != NULL && p->val != val) {
  31.         p = p->next;
  32.     }
  33.     if (p == NULL) {
  34.         return head;
  35.     }
  36.     if (p->prev != NULL) {
  37.         p->prev->next = p->next;
  38.     } else {
  39.         head = p->next;
  40.     }
  41.     if (p->next != NULL) {
  42.         p->next->prev = p->prev;
  43.     }
  44.     free(p);
  45.  
  46.     return head;
  47. }

4.修改操作

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

  1. // 修改指定位置的节点值
  2. struct ListNode* updateAtIndex(struct ListNode* head, int index, int val) {
  3.     struct ListNode* p = head;
  4.     int i = 0;
  5.  
  6.     while (i < index && p != NULL) {
  7.         p = p->next;
  8.         i++;
  9.     }
  10.     if (p == NULL) {
  11.         return head;
  12.     }
  13.     p->val = val;
  14.  
  15.     return head;
  16. }

5.查找操作

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

  1. // 按位置查找节点
  2. struct ListNode* getNodeAtIndex(struct ListNode* head, int index) {
  3.     struct ListNode* p = head;
  4.     int i = 0;
  5.  
  6.     while (i < index && p != NULL) {
  7.         p = p->next;
  8.         i++;
  9.     }
  10.  
  11.     return p;
  12. }
  13.  
  14. // 按值查找节点
  15. struct ListNode* getNodeByValue(struct ListNode* head, int val) {
  16.     struct ListNode* p = head;
  17.  
  18.     while (p != NULL && p->val != val) {
  19.         p = p->next;
  20.     }
  21.  
  22.     return p;
  23. }

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

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

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

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/806954
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号