C语言之链表详解

时间:2024-01-10 01:03:46 标签:  算法  链表  数据结构  算法  c语言  

目录

一、链表定义

二、链表分类

三、链表操作

四、单向链表

1.链表定义

2.插入操作

3.删除操作

4.修改操作

5.查找操作

五、双向链表

1.链表定义

2.插入操作

3.删除操作

4.修改操作

5.查找操作


一、链表定义

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

二、链表分类

链表可以分为三种类型:

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

三、链表操作

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

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

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

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

四、单向链表

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

413c6e745fc63630140e7364e5c3bcf4.jpeg

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)的删除操作,缺点是每个节点需要额外的一个指针。

20200726124645552.png

 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://blоg.сsdn.nеt/Wаng_XB_3434/аrtiсlе/dеtаils/130049123

智能推荐

@目录1.双向链表的定义2.双向链表的创建3.双向链表的插入4.双向链表的删除5.双向链表更改节点数据6.双向链表的查找7.双向链表的打印8.测试函数及结果1.双向链表的定义上一节学习了单向链表单链表详解。今天学习双链表。学习之前先对单向链表和双向链表做个回顾。单向链表特点:  1.我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的.  2.只能从头遍历到尾或者从尾遍历到头(一般从头到尾)

标签:双向  详解  链表  语言  操作  

对于输入的 n 个数据 num 进行排序&#xff0c;要求将输入的数据按 num 升序建立带有表头

标签:链表  c语言  数据结构  

  本篇谈一谈单链表的改,具体操作就是找到他,然后修改元素即可,上一篇有相关代码,可以参考。  改函数代码如下:void Correct(LinkList header, int site_, char letter_){ LinkList q

标签:数据结构  链表  语言  

  上篇谈了谈尾插法和头插法,这篇谈谈中间插入元素和删除。  1、中间插入元素  既然谈到了要从中间插入那就得确定插入的位置是否合法了,我总不能链表总长为5,但是插入的位置是60,这就不对了。所以得先确定这个链表的长度为多少。这个比较简单,就是在寻找尾部的过程中计数,直到走到最后一个节点。  代码如下:int Get_Length(LinkList header){ LinkList p =

标签:数据结构  链表  语言  

  上一篇随笔谈了谈单链表是什么东西,然后进行了初始化,这篇随笔就开始对其进行操作了,首先是增,删,改,查的增。  增,顾名思义就是要增加新的元素,单链表是链式的,那就要考虑怎么去加新元素,有三种,从头部添加,从尾部添加,从中间添加。先说说从尾部添加,这个比较好理解,直接在尾部放一个结点然后连起来就好了。  1、尾插法,从尾部添加节点。  

标签:数据结构  链表  语言  

  当初刚开始学单链表学的是一头雾水,简直就是彻头彻尾灾难,一塌糊涂,过段时间后经过自己的重新认真思考再结合小练习明白了它是怎么个回事儿。  1、首先从它的逻辑上入手,对他有大体认知。  简单来说就是一个一个有方向小块儿连在一起,好像疫情期间大家排队做核酸,都朝着医护人员那个方向,医护人员会从第一个开始数有多少人。先看看怎么用图片表示单链表。  这是一些有方向的小块儿,他们叫结点,它包含两个部分,数据域和后继节点位置的指针。

标签:数据结构  链表  语言  

我们创建一个长度为n的链表时&#xff0c;可以采取头插法创建或者尾插法创建&#xff0c;本篇博客

标签:c++与数据结构系列  c++  c语言  开发语言  数据结构  单链表  头插法  

导语&#xff1a; 在C语言编程中&#xff0c;链表和指针是两个重要的概念。理解它们的使用方法和

标签:c语言  c语言  算法  数据结构  

(0)前言 C语言Pragma 指令的作用是设定编译器的状态或者是指示编译器完成一些

标签:c语言  java  linux  c++  开发语言  

一、链表分割 牛客网链接 题目描述&#xff1a;

标签:数据结构  C语言/C++练习题  c语言  c语言  算法  数据结构  

1.printf() 简介 printf() 是 C 语言标准库函数&#xff0

标签:c语言  算法  开发语言  

猜你喜欢

C语言一. C语言概述C语言是一种用于和计算机交流的高级语言, 它既具有高级语言的特点,又具有汇编语言的特点非常接近自然语言程序的执行效率非常高C语言是所有编程语言中的经典,很多高级语言都是从C语言中衍生出来的,例如:C++、C#、Object-C、Java、Go等等C语言是所有编程语言中的经典,很多著名的系统软件也是C语言编写的几乎所有的操作系统都是用C语言编写的几乎所有的计算机底层软件都是用C语言编写的几乎所有的编辑器都是C语言编写的二. 第一个C语言程序

标签:详解  语言  

前言 链表是一种常见的数据结构&#xff0c;它可以用来存储一组数据&#xff0

标签:数据结构  算法  链表  开发语言  c语言  c++  

C 语言中的运算符运算符用于对变量和值进行操作。在下面的示例中,我们使用 + 运算符将两个值相加:int myNum = 100 + 50;虽然 + 运算符通常用于将两个值相加,就像上面的示例一样,它还可以用于将变量和值相加,或者将变量和另一个变量相加:int sum1 = 100 + 50; // 150 (100 + 50)int sum2 = sum1 + 250; // 4

标签:详解  运算符  语言  

一、什么是素数 素数是指在大于1的自然数中&#xff0c;除了1和它本身以外不再有其

标签:初学c语言  c语言  学习  算法  

题目&#xff1a;         输入一系列自然数&#xff08;0和正整数

标签:数据结构  力扣  链表  c语言  数据结构  c++  算法  

什么是链接属性链接属性与C语言中各个目标文件及函数的链接过程有关,用于认定不同文件的标识符(即程序中定义的各种名称,包括变量名、函数名)是否是同一个实体。更通俗地说,就是在两个不同文件中的变量、函数声明是否指向同一个实体。比如:a、b文件同时声明了变量c,链接属性就指定了这两处变量c是否是同一个c。简单来说,链接属性的作用就是让你能在a文件中决定要不要访问b文件中的变量、函数。链接属性的分类链接属性有三种:external - 外部链接internal - 内部链接none - 无链接

标签:属性  语言  链接  

本程序采用链表的方式可以实现对于通讯录信息的管理操作主要有增 删 改 查 显示全部信息 退出六个功能

标签:c语言  c语言  蓝桥杯  链表  数据结构  开发语言  

一、什么是高精度        高精度本质上是一种计算&#xff0c;由于int

标签:数据结构与算法  算法  c语言  蓝桥杯  

相关问题

相关文章

热门文章

推荐文章

相关标签