数据结构与算法: 常用数据结构的应用场景-集合

数据结构主要研究什么?

数据结构(英语:data structure)是计算机中存储、组织数据的方式。

数据结构是一种具有一定逻辑关系,在计算机中应用某种存储结构,并且封装了相应操作的数据元素集合。它包含三方面的内容,逻辑关系、存储关系及操作。

逻辑结构和物理结构

数据的逻辑结构
指反映数据元素之间的相互关系,而与他们在计算机中的存储位置无关。按相互关系分类:集合结构,线性结构,树形结构

数据的物理结构(存储结构)
指数据的逻辑结构在计算机存储空间的存放形式. 常见的物理结构有顺序存储结构、链式存储结构

数据结构主要研究对象是逻辑结构

所有的算法必须基于数据结构生存。这也是为什么算法和数据结构两门分类不分家的原因

常见集合框架最佳使用场景

Array:

最佳使用场景:当你知道元素数量固定,且需要高效地访问元素时,数组是最佳选择。数组在内存中是连续的,因此访问速度非常快。且提供快速的随机访问,适用于索引操作频繁的场景。
特性:数组的大小在创建时确定,之后不能改变。

List

最佳使用场景:当需要动态大小的集合, 且频繁地添加和删除元素,同时需要快速的索引访问时。它提供了基于索引的访问。适合大多数通用的集合处理需求。
特性:List 是动态数组,可以动态地调整其大小。

HashSet

最佳使用场景:当需要存储不重复的元素,并且需要快速检查元素是否存在时,另外再集合运算(如交集、并集、差集)等场景。
特性:HashSet 使用了哈希表来存储元素,因此查找、添加和删除操作都非常快。

Dictionary<TKey, TValue>:

最佳使用场景:当需要存储键值对,并且需要基于键快速查找值时,适用于映射、查找表等场景,其中键值对关系明确。
特性:Dictionary<TKey, TValue> 内部使用哈希表来存储键值对,因此查找操作非常快。

LinkedList

最佳使用场景:当需要在列表的开头或结尾频繁地添加或删除元素时,LinkedList 是更好的选择。与 List 相比,它在这些操作上的性能更好。
特性:LinkedList 通过节点链接实现,因此元素的添加和删除不需要移动其他元素。

SortedList<TKey, TValue> 和 SortedDictionary<TKey, TValue>:

最佳使用场景:需要保持元素有序且唯一时, 且需要存储键值对,并且需要基于键进行排序和快速查找时,这些集合是合适的。SortedList<TKey, TValue> 在内存使用上更节省,而 SortedDictionary<TKey, TValue> 在插入和删除操作上更快。
特性:它们内部维护了键的排序顺序,因此提供了有序的键值对集合。

Stack

最佳使用场景:当需要实现后进先出(LIFO)的数据结构时,Stack 是合适的。例如,在解析表达式或实现函数调用栈时。
特性:Stack 提供了 Push(添加元素到栈顶)和 Pop(从栈顶移除元素)等操作。

Queue

最佳使用场景:当需要实现先进先出(FIFO)的数据结构时,Queue 是合适的。例如,在处理任务队列或消息队列时。
特性:Queue 提供了 Enqueue(在队尾添加元素)和 Dequeue(从队头移除元素)等操作。

常见数据结构及其应用场景

数组(顺序表)

数组是可以在内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。

适用场景:

  • 频繁查询,对存储空间要求不大,很少增加和删除的情况

优点:

  • 按照索引查询元素速度快
  • 按照索引遍历数组方便

缺点:

  • 数组的大小固定后就无法扩容了
  • 数组只能存储一种类型的数据
  • 添加,删除的操作慢,因为要移动其他的元素。

栈(先进后出)

栈是一种基于先进后出(FILO)的数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

我们称数据进入到栈的动作为压栈,数据从栈中出去的动作为弹栈

应用场景:

  • 括号匹配问题;逆波兰表达式求值问题;实现递归功能方面的场景,例如斐波那契数列。

队列(先进先出)

队列是一种基于先进先出(FIFO)的数据结构,是一种只能在一端进行插入,在另一端进行删除操作的特殊线性表,它按照先进先出的原则存储数据,先进入的数据,在读取数据时先被读取出来。

使用场景:

  • 因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。

链表

链表是一种物理存储单元上非连续、非顺序的存储结构,其物理结构不能只表示数据元素的逻辑顺序,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等

适用场景:

  • 数据量较小,需要频繁增加,删除操作的场景;
  • 快慢指针:求中间值问题、单向链表是否有环问题、有环链表入口问题;
  • 循环链表:约瑟夫问题

树是我们计算机中非常重要的一种数据结构,同时使用树这种数据结构,可以描述现实生活中的很多事物,例如家谱、单位的组织架构等。

应用场景:

  • JDK1.8中 HashMap的底层源码中用到了数组+链表+红黑树;
  • 磁盘文件中使用B树做为数据组织,B树大大提高了IO的操作效率;
  • mysql数据库索引结构采用B+树;

树具有以下特点:

  • 每个结点有零个或多个子结点;
  • 没有父结点的结点为根结点;
  • 每一个非根结点只有一个父结点;
  • 每个结点及其后代结点整体上可以看做是一棵树,称为当前结点的父结点的一个子树;

在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是

  • 二叉树
  • 平衡树
  • 红黑树
  • B树
  • B+树

散列表(哈希表)

应用场景:

  • 哈希表的应用场景很多,当然也有很多问题要考虑,比如哈希冲突的问题,如果处理的不好会浪费大量的时间,导致应用崩溃。
  • 解决哈希冲突问题:1 可以对数组扩容; 2 优化hash计算方式;

堆是计算机学科中一类特殊的数据结构的统称,堆通常可以被看作是一棵完全二叉树的数组对象。

应用场景:

  • 因为堆有序的特点,一般用来做数组中的排序,称为堆排序。

堆的特性:

  • 它是完全二叉树,除了树的最后一层结点不需要是满的,其它的每一层从左到右都是满的,如果最后一层结点不是满的,那么要求左满右不满;
  • 它通常用数组来实现;

图的定义:图是由一组顶点和一组能够将两个顶点相连的边组成的

应用场景:

  • 道路畅通工程
  • 最短路径

图的搜索:

  • 深度优先搜索:在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找子结点,然后找兄弟结点。
  • 广度优先搜索:在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找兄弟结点,然后找子结点。

扩展阅读

关于数据存储引擎结构,没有比这篇更详细的
常用八大数据结构总结及应用场景-附示例截图
数据结构与算法

此处评论已关闭