【数据结构与算法】数组与链表的比较与应用

sockstack / 1011 / 2023-07-28 22:43:56

日常开发汇总

ChatGPT 可用网址，仅供交流学习使用，如对您有所帮助，请收藏并推荐给需要的朋友。 <a href="https://ckai.xyz/?sockstack&section=detail" target="__blank">https://ckai.xyz</a> ## 1、数组

数组是一个存储元素的线性集合，它使用一块`连续`的内存空间保存数据，保存的数据的个数在分配内存的时候就是确定的。

![](/upload/img/20230802/64ca0d71a7de.png)

访问数组中第 n 个元素的时间花费是O(1) ，在数组中查找一个指定的元素则是O(N)。

向数组中插入或删除元素时，最好的情况是在数组的末尾进行操作，时间复杂度是O(1) ，最坏情况是插入或者删除第一个元素，时间复杂度是O(N) 。

在数组的任意位置插入或删除元素时，后面的元素全部需要移动，移动的元素和元素个数有关，总体的时间复杂度仍然是O(N) 。

## 2、链表

链表是由一组节点组成的集合。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。每个节点都使用一个对象的引用指向它的后继，最后一个节点的指针指向NULL。

链表不需要提前分配固定大小存储空间，当需要存储数据的时候分配一块内存并将这块内存插入链表中。

![](/upload/img/20230802/64ca0bcf2492.png)

链表分为单链表、双链表、循环链表。

双链表和单链表类似，每一个元素都有前驱和后继，但是第一个元素没有前驱，最后一个元素没有后继，指针指向的都是NULL。

循环链表和单链表也类似，但是最后一个元素的后继指向第一个元素。

链表的删除和修改操作的复杂度都是O(1)，但是便利到指定的n元素的复杂度是O(n).

## 3、链表和数组的区别

|              | 数组                                                         | 链表                                                         |
| ------------ | ------------------------------------------------------------ | ------------------------------------------------------------ |
| 动态存储分配 | 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。 | 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）。 |
| 逻辑结构角度 | 数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。 | 链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。 |
| 内存存储角度 | (静态)数组从栈中分配空间, 对于程序员方便快速,但自由度小。    | 链表从堆中分配空间, 自由度大但申请管理比较麻烦。             |
| 总结         | 1）数组静态分配内存，链表动态分配内存；2）数组在内存中连续，链表不连续；3）数组元素在栈区，链表元素在堆区；4）数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；5）数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1 |                                                              |

【数据结构与算法】数组与链表的比较与应用

作者

sockstack

许可协议

CC BY 4.0

发布于

2023-07-28

修改于

2024-12-21

上一篇：半天实现的NextJS轮子项目下一篇：【代码仓库】使用Nginx搭建代码仓库 - 快速部署轻量级代码版本管理系统

尚未登录

【数据结构与算法】数组与链表的比较与应用

文章分类

博客重构之路

Spring Boot简单入门

k8s 入门教程

MySQL 知识

NSQ 消息队列

ThinkPHP5 源码分析

使用 Docker 从零开始搭建私人代码仓库

日常开发汇总

标签列表

springboot

hyperf

swoole

webman

php

多线程

数据结构

docker

k8s

thinkphp

mysql

tailwindcss

flowbite

css

前端