链表的基本概念

链表引出

• 数组有缺陷
• 静态空间，一旦分配就不可以动态扩展，要不分配不够，要不分配过多。
• 对于数组头部进行插入和删除效率低

链表的组成

• 链表是有节点组成的
• 节点由 数据域和指针域组成
• struct LinkNode{int num; struct}

链表的分类

• 方式1： 静态链表 动态链表
• 方式2： 单向链表 双向链表 单向循环链表 双向循环链表

静态链表和动态链表

• 静态链表 创建在栈上
• 动态链表 创建在堆区

代码示例：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//节点声明
struct LinkNode
{
   
        int num;       //数据域
        struct LinkNode*next;  //指针域
};
void test01()
{
   
        //创建节点
        struct LinkNode node1 = {
   10,NULL};
        struct LinkNode node2 = {
    20,NULL };
        struct LinkNode node3 = {
    30,NULL };
        struct LinkNode node4 = {
    40,NULL };
        struct LinkNode node5 = {
    50,NULL };
        //建立关系
        node1.next = &node2;
        node2.next = &node3;
        node3.next = &node4;
        node4.next = &node5;
        //如何遍历这个链表
        //创建一个指针 指向第一个节点
        struct LinkNode*pCurrent = &node1;
        while (pCurrent != NULL)
        {
   
               printf("%d\n",pCurrent->num);
               pCurrent = pCurrent->next;
        }
}
//2.动态链表
void test02()
{
   
        struct LinkNode*node1 = malloc(sizeof(struct LinkNode));
        struct LinkNode*node2 = malloc(sizeof(struct LinkNode));
        struct LinkNode*node3 = malloc(sizeof(struct LinkNode));
        struct LinkNode*node4 = malloc(sizeof(struct LinkNode));
        struct LinkNode*node5 = malloc(sizeof(struct LinkNode));
        node1->num = 10;
        node2->num = 20;
        node3->num = 30;
        node4->num = 40;
        node5->num = 50;
        //建立关系
        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node5;
        node5->next = NULL;
        //遍历链表
        struct LinkNode*pCurrent = node1;
        while (pCurrent != NULL)
        {
   
               printf(":::%d\n",pCurrent->num);
               pCurrent = pCurrent->next;
        }
        //释放节点
        free(node1);
        free(node2);
        free(node3);
        free(node4);
        free(node5);
}
int main()
{
   
        test01();
        test02();
        return EXIT_SUCCESS;
}