数据结构主要研究什么?

数据结构（英语：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计算方式；

堆

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

应用场景：

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

堆的特性：

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

图

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

应用场景：

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

图的搜索：

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

扩展阅读

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

最后更新于  2024-04-29 17:45:13  并被添加「」标签，已有 1108 位童鞋阅读过。

本站使用「署名 4.0 国际」创作共享协议，可自由转载、引用，但需署名作者且注明文章出处