数据结构

链表

链表和数组的区别

1. 存储方式

• 数组：
  • 元素在内存中连续存储，占用一块连续的内存空间
  • 元素的地址可以通过索引计算（基地址 + 索引 × 元素大小）
  • 大小固定，在创建时需要指定容量
• 链表：
  • 元素（节点）在内存中分散存储，不要求连续
  • 每个节点包含数据和指向下一个（或上一个）节点的指针
  • 大小动态变化，可根据需要随时增减节点

2. 访问效率

• 数组：
  • 支持随机访问，通过索引可以直接访问任意元素，时间复杂度为 O (1)
  • 访问效率高，适合需要频繁随机访问的场景
• 链表：
  • 不支持随机访问，必须从表头（或表尾）开始依次遍历，时间复杂度为 O (n)
  • 访问效率低，不适合需要频繁随机访问的场景

3. 插入和删除操作

• 数组：
  • 插入 / 删除元素时，需要移动该位置后的所有元素，时间复杂度为 O (n)
  • 尤其在数组头部操作时效率极低
  • 动态扩容时需要重新分配内存并复制元素
• 链表：
  • 插入 / 删除元素时，只需修改相关节点的指针，时间复杂度为 O (1)（已知前驱节点时）
  • 不需要移动其他元素，操作效率高
  • 没有扩容问题，内存利用率更高

4. 内存占用

• 数组：
  • 可能存在内存浪费（预分配的容量可能大于实际需要）
  • 内存利用率较低
• 链表：
  • 每个节点需要额外存储指针信息，有一定内存开销
  • 但整体内存利用率更高，不会浪费空间

5. 适用场景

• 数组：
  • 适合需要频繁随机访问元素的场景（如查找操作多）
  • 元素数量固定或变化不大的情况
  • 例如：数据库索引、矩阵存储、缓存实现等
• 链表：
  • 适合需要频繁插入和删除元素的场景
  • 元素数量动态变化较大的情况
  • 例如：链表式队列 / 栈、哈希表链地址法冲突解决、邻接表等

总结对比表

特性	数组	链表
存储方式	连续内存	分散内存 + 指针
随机访问	支持 (O (1))	不支持 (O (n))
插入删除	低效 (O (n))	高效 (O (1))
内存效率	可能浪费空间	有指针开销但利用率高
大小	固定	动态

• 数组中的数据我们称之为元素

• 链表中的数据我们称之为节点

  每一个节点都是一个结构体,当前结构体包含两种信息

  1. 数据(每个节点中所存储的信息)
  2. 节点指针(保存下一个节点的信息)

  将节点插入链表:头插法/尾插法/中间插入

  eg:

                                                节点对应结构体
typedef struct Node 
{int num;		   /每个节点中存储的数据,可以有多个struct Node* pNext;   /用于保存下一个节点(结构体)的指针
} Node;函数功能:      创建一个节点int n --------当前节点的数据NODE*  head---------当前链表首节点地址返回类型:成功返回当前节点首地址,失败返回NULLNODE* createNode(int n,NODE* head)
{//创建一个新节点NODE* pNew = (NODE*)malloc(sizeof(NODE));if(pNew == NULL){printf("createNode %d fail:%s!\n",n,strerror(errno));return NULL;}//初始化新节点中的成员变量pNew -> num = n;pNew -> pNext = NULL;//返回当前节点的首地址return pNew;}函数功能:      删除整个链表NODE*  head---------当前链表首节点地址void distroyList(NODE* head){if(head == NULL){return;}NODE* P = head;while(p != NULL){head = p -> pNext;free(p);p = head;}}函数功能:    输出整个链表NODE*  head---------当前链表首节点地址返回类型:成功返回当前节点首地址,失败返回NULLvoid displayList(NODE* head){while(p != NULL){printf("%d",p->num);p = p->pNext;}}                                  void insert_head1(int n,NODE** head)
{//创建新节点NODE*  pNew = createNode(n);//如果是空链表if(*head == NULL){*head = pNew;return}//新节点指向原链表的首节点pNew -> pNext = *head;//将新节点的起始地址给*head*head = pNew;}NODE*	 insert_head2(int n,NODE* head)
{NODE*  pNew = createNode(n);//如果是空链表if(head == NULL){return pNew;}pNew -> pNext = *head;//将新节点的起始地址给*headreturn  pNew;}//插入到结尾NODE* insert_tail(int n, NODE* head)
{//创建节点NODE* pNew == createNode(n);if(pNew == NULL){return pNew;}//获取原链表尾节点的指针NODE* pTail = getTaiilNode(head);if(pTail) = getTaiilNode(head);{return pNew;}pTail ->P=pNext = pNew;return head;}NODE* insertNode(int n,NODE* head,int pos)
{}int main()
{// 用于记录当前链表中首节点的地址NODE* pHead = NULL;// 将节点插入链表中：头插法//insert_head1(5, &pHead);//insert_head1(4, &pHead);//insert_head1(3, &pHead);//insert_head1(2, &pHead);//insert_head1(1, &pHead);//pHead = insert_head2(-5, pHead);//pHead = insert_head2(-4, pHead);//pHead = insert_head2(-3, pHead);//pHead = insert_head2(-2, pHead);//pHead = insert_head2(-1, pHead);// 将节点插入链表中：尾插法//pHead = insert_tail(1, pHead);//pHead = insert_tail(2, pHead);//pHead = insert_tail(3, pHead);//pHead = insert_tail(4, pHead);// 将节点插入链表中：任意位置插入// 假设位置 0 代表头插pHead = insertNode(1, pHead, 3);displayList(pHead);distroyList(pHead);return 0;
}