数组和链表的认识

布满荆棘的人生 2022-12-27 12:58 30阅读 0赞

# 1.    概念 #

## 1.1    链表 ##

链表是一种物理[存储单元][Link 1]上非连续、非顺序的[存储结构][Link 2]，[数据元素][Link 3]的逻辑顺序是通过链表中的[指针][Link 4]链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储[数据元素][Link 5]的数据域，另一个是存储下一个结点地址的[指针][Link 4]域。

链表有很多种不同的类型：[单向链表][Link 6]，[双向链表][Link 7]以及[循环链表][Link 8]。

单向链表（[单链表][Link 9]）是[链表][Link 10]的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用[指针][Link 4]进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针[成员变量][Link 11]指向列表中的下一个结点；链表是由[结点][Link 12]构成，head指针指向第一个成为表头结点，而终止于最后一个指向[NULL][]的指针。

双向链表也叫双链表，是链表的一种，它的每个数据[结点][Link 12]中都有两个[指针][Link 4]，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的[指针][Link 4]域指向[头结点][Link 13]，整个链表形成一个环。分为单循环链表和多循环链表。单循环链表——在[单链表][Link 14]中，将终端结点的[指针][Link 15]域NULL改为指向表头结点或开始结点即可。多重链的循环链表——将表中结点链在多个环上。

## 1.2    数组 ##

数组（Array）是有序的元素序列。把具有相同类型的若干元素按有序的形式组织起来的一种形式。数组是用于储存多个相同类型数据的集合。分类：一维、二维（矩阵）、三维数组。

# 2.    链表和数组的区别、优缺点 #

## 2.1    链表 ##

1.  链表在内存中，是分散的
2.  链表由于增加了结点的[指针][Link 4]域，空间开销比较大
3.  链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
4.  链表不能随机读取，需要从头指针开始，依次向一个节点查找数据，时间复杂度O(n)

## 2.2    数组 ##

1.  数组占用的是一块连续的内存区
2.  数组不用存储[指针][Link 4]域，空间开销比较小
3.  数组需要预先知道数据大小
4.  数组可以随机读取,时间复杂度O(1)
5.  常规[数组][Link 16]排列关联项目的方式可能不同于这些数据项目在[记忆体][Link 17]或[磁盘][Link 18]上顺序，数据的存取往往要在不同的排列顺序中转换

[Link 1]: https://baike.baidu.com/item/%E5%AD%98%E5%82%A8%E5%8D%95%E5%85%83/8727749
[Link 2]: https://baike.baidu.com/item/%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84/350782
[Link 3]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0/715313
[Link 4]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88/2878304
[Link 5]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0
[Link 6]: https://baike.baidu.com/item/%E5%8D%95%E5%90%91%E9%93%BE%E8%A1%A8/8671935
[Link 7]: https://baike.baidu.com/item/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/2968731
[Link 8]: https://baike.baidu.com/item/%E5%BE%AA%E7%8E%AF%E9%93%BE%E8%A1%A8/3228465
[Link 9]: https://baike.baidu.com/item/%E5%8D%95%E9%93%BE%E8%A1%A8/3228368
[Link 10]: https://baike.baidu.com/item/%E9%93%BE%E8%A1%A8/9794473
[Link 11]: https://baike.baidu.com/item/%E6%88%90%E5%91%98%E5%8F%98%E9%87%8F/11024994
[Link 12]: https://baike.baidu.com/item/%E7%BB%93%E7%82%B9/9794643
[NULL]: https://baike.baidu.com/item/NULL/19660387
[Link 13]: https://baike.baidu.com/item/%E5%A4%B4%E7%BB%93%E7%82%B9/9794729
[Link 14]: https://baike.baidu.com/item/%E5%8D%95%E9%93%BE%E8%A1%A8
[Link 15]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88
[Link 16]: https://baike.baidu.com/item/%E6%95%B0%E7%BB%84/3794097
[Link 17]: https://baike.baidu.com/item/%E8%AE%B0%E5%BF%86%E4%BD%93/3029693
[Link 18]: https://baike.baidu.com/item/%E7%A3%81%E7%9B%98/2842227