静态链表和动态链表（静态链表和动态链表的优缺点）

静态链表和动态链表

简介

链表是一种非连续存储数据的线性表结构。它由一系列结点组成，每个结点存储着数据和指向下一个结点的指针。链表分为两类：静态链表和动态链表。

静态链表

定义

静态链表是一种链表，其中结点的内存空间在程序运行前就分配好，并且结点的位置是固定的。

特点

结点个数固定，无法动态增加或减少

结点间的关系是通过指针来表示的

空间利用率低（可能存在很多空闲结点）

插入或删除结点时需要移动指针，时间复杂度较高

动态链表

定义

动态链表是一种链表，其中结点的内存空间在需要时动态分配，并且结点的物理位置可以动态变化。

特点

结点个数可动态增加或减少

结点间的关系是通过指针来表示的，但指针指向的结点可能在内存中移动

空间利用率高，内存只分配给实际需要的结点

插入或删除结点时只需要修改指针，时间复杂度低

比较

| 特征 | 静态链表 | 动态链表 | |---|---|---| | 结点分配 | 运行前分配好 | 运行时动态分配 | | 空间利用率 | 低 | 高 | | 插入/删除时间复杂度 | 高 | 低 |

应用

静态链表：适合结点个数固定或变化较小的场合，例如编译器中的符号表

动态链表：适合结点个数动态变化较大的场合，例如栈、队列、图的邻接表等

**静态链表和动态链表****简介**链表是一种非连续存储数据的线性表结构。它由一系列结点组成，每个结点存储着数据和指向下一个结点的指针。链表分为两类：静态链表和动态链表。**静态链表****定义**静态链表是一种链表，其中结点的内存空间在程序运行前就分配好，并且结点的位置是固定的。**特点*** 结点个数固定，无法动态增加或减少 * 结点间的关系是通过指针来表示的 * 空间利用率低（可能存在很多空闲结点） * 插入或删除结点时需要移动指针，时间复杂度较高**动态链表****定义**动态链表是一种链表，其中结点的内存空间在需要时动态分配，并且结点的物理位置可以动态变化。**特点*** 结点个数可动态增加或减少 * 结点间的关系是通过指针来表示的，但指针指向的结点可能在内存中移动 * 空间利用率高，内存只分配给实际需要的结点 * 插入或删除结点时只需要修改指针，时间复杂度低**比较**| 特征 | 静态链表 | 动态链表 | |---|---|---| | 结点分配 | 运行前分配好 | 运行时动态分配 | | 空间利用率 | 低 | 高 | | 插入/删除时间复杂度 | 高 | 低 |**应用*** 静态链表：适合结点个数固定或变化较小的场合，例如编译器中的符号表 * 动态链表：适合结点个数动态变化较大的场合，例如栈、队列、图的邻接表等