单向链表的应用

链表的概念，基本操作
- 创建节点
- 插入节点
表尾插入
链表遍历
- 为什么静态链表很少用
- 传统链表的思考

链表的概念，基本操作

链表是一种物理存储单元上非连续的存储结构，由一系列节点（链表中每一个元素称为节点）组成，结点可以在运行时动态生成，节点与节点之间通过指针链接。每个节点包括两个部分：一部分是存储数据元素的数据域，另一部分是存储下一个节点地址的指针域。

在这里插入图片描述

链表是一种常用的数据结构，它通过指针将一些列数据节点，连接成一个数据链。相对于数组，链表具有良好的动态性。
数据域用来存储数据，指针域用来建立与下一个节点的联系。
建立链表时无需预先知道数据总量的，可以随机的分配空间，可以高效的在链表中的任意位置实时插入或删除数据。
链表的开销，主要是访问顺序性和组织链的空间损失。

单向链表：
在这里插入图片描述
双向链表：

创建节点

在创建节点之前，我们已经创建好了结构体和表头

//创建结构体
struct Node
{int data;struct Node* next;
};
//创建表头
struct Node* createlist()
{struct Node* head = (struct Node*)malloc(sizeof(struct Node));head->next = NULL;//头节点指向空return head;
}
//创建节点
struct Node* createNode(int num)
{struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = num;newNode->next = NULL;return newNode;//返回节点的地址
}

插入节点

表头插入：

//表头法插入
struct Node* insertByHead(struct Node*head,int num)
{struct Node* newNode = createNode(num);//指向新节点的指针newNode->next = head->next;head->next = newNode;return newNode;
}

表尾插入

//表尾法插入
struct Node* insertByEnd(struct Node* head, int num)
{struct Node* newNode = createNode(num);//指向新节点的指针while (head->next != NULL)   //从头到位一直往后，直到找到最后一个节点{head = head->next;}head->next = newNode;      //将新节点接在原最后一个节点后面return newNode;            //返回一个地址
}

链表遍历

//链表的遍历
void printlist(struct Node* head)
{head = head->next;        //头节点一般不存放数据while (head != NULL)      //当节点不为空时即执行循环{printf("%d ", head->data);head = head->next;    //输出后移向下一节点}printf("\n");
}