常见的数据结构及算法

用户头像
stars
关注
发布于: 2020 年 07 月 29 日
常见的数据结构及算法

1、数据结构

1.1、数组

数组是比较常见的数据结构。创建数据必须是内存中的一段连续的空间,另外,数组中也必须存放相同类型的数据。数组通过下标读取数组元素,随机读写速度快是数组的一大特性。内存结构如下图:

数组的特点:随机读写快,插入较慢。

1.2、链表



链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表中的每个数据元素都必须存储指向下一个元素地址的指针。如果要在链表中查找一个元素,必须从第一个元素开始找。链表的结构如下图:

链表的特点:查询较慢,插入较快。

1.3、Hash表

hash表是根据Key而直接进行访问的数据结构。它通过把key值映射到表中一个位置来访问记录,以加快查找的速度。本质上是数组与链表的一种结合,内存结构如下图:

上图中,左侧是数组,数组元素存放的是key的hashcode,不同的key计算出的hashcode有可能相同,这时就是“hash冲突”。当hash冲突时,在采用链表顺序存储。hash表的特点:既能快速访问数据,也能快速增删数据。

1.4、栈

栈也叫堆栈,是一种操作受限的线性表(数组、链表都是线性表)。结构如下图:

特点:后进先出,即后面加进来的数据,必须首先比删除。

用户头像

stars

关注

架构师的肚是杂货铺 2018.02.19 加入

还未添加个人简介

评论

发布
暂无评论
常见的数据结构及算法