数据结构和类型

数据结构是为了在编程语言中存储、组织和操作数据而引入的。它们的设计方式使得访问和处理数据更加轻松便捷。这些数据结构并不局限于某一特定的编程语言；它们只是在内存中构建数据的代码片段。

数据类型经常被误认为是一种数据结构，但即使它们被称为抽象数据类型，这种说法也不完全正确。数据类型代表数据的性质，而数据结构只是相似或不同数据类型的集合。

数据结构通常只有两种类型 −

• 线性

• 非线性

线性数据结构

数据按顺序存储在线性数据结构中。这些是基本结构，因为元素是逐个存储的，不进行任何数学运算。

线性数据结构通常易于实现，但由于内存分配可能变得复杂，时间和空间复杂度也会增加。线性数据结构的一些示例包括 −

• 数组

• 链表

• 堆栈

• 队列

根据数据存储方式，这些线性数据结构分为两种子类型。它们是 − 静态和动态数据结构。

静态线性数据结构

在静态线性数据结构中，内存分配不可扩展。一旦使用了全部内存，就无法再检索更多空间来存储更多数据。因此，需要根据程序的大小预留内存。这也会成为一个缺点，因为预留的内存超过所需会导致内存块的浪费。

静态线性数据结构的最佳示例是数组。

动态线性数据结构

在动态线性数据结构中，可以根据需要动态地进行内存分配。考虑到程序的空间复杂度，这些数据结构非常高效。

动态线性数据结构的一些示例包括：链表、堆栈和队列。

非线性数据结构

非线性数据结构以层次结构的形式存储数据。因此，与线性数据结构相比，数据可以存在于多个层级中，并且难以遍历。

然而，它们的设计旨在克服线性数据结构的问题和局限性。例如，线性数据结构的主要缺点是内存分配。由于数据在线性数据结构中是顺序分配的，因此这些数据结构中的每个元素都会占用一整个内存块。但是，如果数据占用的内存小于分配的块所能容纳的内存，则块中多余的内存空间就会被浪费。因此，引入了非线性数据结构。它们可以降低空间复杂度并优化内存利用率。

少数几种非线性数据结构是 −

• 图

• 树

• 字典树

• 映射