数据结构中最简单的链表

(资料图片)

数据结构作为嵌入式工程师必修课程之一，今天，我们就来讲一讲数据结构中最简单的链表，包含链表的初始化、插入和遍历操作。 链表在项目开发中使用的场景很多，跟数组相比，它的优点就是，容量没有限制，插入删除效率比较高。 数组在内存中是一块连续的存储空间，而且随着存储数据的不断增多，想要找到这么一大块的连续内存也比较困难。 但是链表就能解决这个问题，它由节点组成，每个节点占用的内存不会很大，而且各个节点之间也不需要连续，为了方便访问，只要把下一个节点的地址记在上一个节点的指针域中就行，这样，所有节点之间就像有跟线一样串联起来。 跟数组相比，它的随机插入效率也要高很多。比如数组有100个元素，想要在第一个位置插入一个元素，那么每个元素都得向后移动一个位置，把第一个位置腾出来，数据量越大，移动的效率越低。 链表的插入完全不一样，不管在什么位置插入，只要适当的修改几个指针就能解决问题。 链表可以有头节点，也可以没有头节点，为了方便编程，我们一般都会加上头节点。 有了头节点，就有了头指针，用来保存头节点的地址。 既然链表是由很多个节点组成，第一步就得用代码来表示节点。节点分为数据域和指针域，数据域可以是任意类型，我们就用int吧，指针域保存下一个节点的地址，把这两个成员放在结构体中，后面就用Node来表示节点。

typedef struct Node{    int data;    struct Node *next;}Node;

所谓链表的初始化，就是形成一个空的链表，空的链表只有一个头节点，数据域没有数据，指针域为空。 定义头指针head，初始化的时候，因为要修改head的数值，所以必须传它的地址。

Node *head = NULL;int ret = InitLink(&head);if (SUCCESS == ret){       printf("链表初始化成功");}   else{       printf("链表初始化失败");}

先申请一个节点，把节点的地址保存在head中，节点的指针域为NULL，初始化的工作就完成了。

int InitLink(Node **h){    if (NULL == h)        return FAILURE;    (*h) = (Node *)malloc(sizeof(Node));    if ((*h) == NULL)    {           return FAILURE;    }       (*h)->next = NULL;    return SUCCESS;}

链表的插入操作是一个经典的笔试题。 过程就是：定义指针指向头节点，把指针移动到要插入位置的前一个位置，同时判断插入的位置是否合法，申请新的节点，填好指针域和数据域，最后再修改前一个节点的指针域，形成一个新的链表。 继续写代码，主函数中通过for循环，往链表中插入10个节点，插入的数据随机生成，位置就指定为i + 1，意思就是第一次往第一个位置插入，第二次往第二个位置插入，这种插入方法我们把它称作尾插法。

srand(time(NULL));int num;for (int i = 0; i < 10; i++){       num = rand() % 20;     ret = InsertLink(head, i + 1, num);    if (SUCCESS == ret)    {           printf("插入 %d 成功", num);    }       else    {           printf("插入 %d 失败", num);    }   }

来实现插入的功能。 先定义一个指针，指向头节点，根据插入的位置移动移动指针。接下来就是判断插入的位置是否合法，有两种情况要排除，一种是插入的位置小于等于0，一种是插入的位置太大，比如链表一共5个节点，在第七个位置插入肯定不行。然后在堆空间申请一个新的节点，填写数据域和指针域，最后把q指向的节点指针域改成新申请的节点，插入的操作就完成了。

int InsertLink(Node *h, int p, int num){    if (NULL == h)        return FAILURE;    Node *q = h;    int k = 1;    while (k < p && q)    {           q = q->next;        k++;    }       if (!q || k > p)    {        return FAILURE;    }    Node *n = (Node *)malloc(sizeof(Node) * 1);    if (NULL == n)    {        return FAILURE;    }    n->data = num;    n->next = q->next;    q->next = n;    return SUCCESS;}

运行看下现象，10个节点都显示插入成功。

root@Turbo:test# ./main链表初始化成功插入 1 成功插入 3 成功插入 4 成功插入 8 成功插入 18 成功插入 0 成功插入 16 成功插入 5 成功插入 6 成功插入 1 成功

但是到底有没有形成链表，还得遍历看下。 遍历操作只需要借助指针，每经过一个节点，打印该节点的数据就行。定义指针p，指向第一个节点，注意，第一个节点不是头节点，而是第一个保存数据的节点。只要指针p不为空，就说明链表还没有到最后，打印该节点数据，然后让p继续往下。

void TraverseLink(Node *h) {    if (NULL == h)        return;    Node *p = h->next;    while (p)     {           printf("%d ", p->data);        p = p->next;    }       printf("");}

运行看下结果，也没有问题。 这就是链表的几个基本操作，尤其是插入操作，基本是笔试必考，如果你有就业的需求，不妨把这段代码背下来。

审核编辑：汤梓红

关键词：