数据结构概述|集合1（线性数据结构）

数据结构是在计算机中组织数据以便有效使用的一种特殊方式。其目的是减少不同任务的空间和时间复杂性。下面是一些流行的线性数据结构的概述。

1.数组 2.链表 3.堆叠 4.排队

大堆

数组是一种数据结构，用于在相邻位置存储同质元素。在存储数据之前，必须提供数组的大小。

Let size of array be n.Accessing Time: O(1) [This is possible because elements                      are stored at contiguous locations]   Search Time:   O(n) for Sequential Search:                O(log n) for Binary Search [If Array is sorted]Insertion Time: O(n) [The worst case occurs when insertion                      happens at the Beginning of an array and                      requires shifting all of the elements]Deletion Time: O(n) [The worst case occurs when deletion                      happens at the Beginning of an array and                      requires shifting all of the elements]

例子： 例如，假设我们想存储一个班级中所有学生的分数，我们可以使用数组来存储它们。这有助于减少许多变量的使用，因为我们不需要为每个主题的分数创建单独的变量。只需遍历数组即可访问所有标记。

链表

链表是一种线性数据结构（如数组），其中每个元素都是一个单独的对象。列表中的每个元素（即节点）都由两项组成——数据和对下一个节点的引用。

链表的类型： 1 单链表： 在这种类型的链表中，每个节点存储列表中下一个节点的地址或引用，最后一个节点的下一个地址或引用为空。例如1->2->3->4->NULL

2. 双链接列表： 在这种类型的链表中，有两个参照与每个节点关联，一个参照点指向下一个节点，另一个参照点指向上一个节点。这种数据结构的优点是，我们可以在两个方向上进行遍历，对于删除，我们不需要显式访问前一个节点。例如：空23->空

3. 循环链表： 循环链表是一种链表，其中所有节点都连接成一个圆。结尾没有空值。循环链表可以是单循环链表或双循环链表。这种数据结构的优点是，任何节点都可以作为起始节点。这在链表中循环队列的实现中很有用。例如1->2->3->1[最后一个节点的下一个指针指向第一个]

Accessing time of an element : O(n)Search time of an element : O(n)Insertion of an Element : O(1) [If we are at the position                                 where we have to insert                                 an element] Deletion of an Element : O(1) [If we know address of node                               previous the node to be                                deleted] 

例子： 考虑前面的例子，我们制作了学生成绩的数组。现在，如果一个新科目被添加到课程中，它的分数也将被添加到分数数组中。但是数组的大小是固定的，它已经满了，所以不能添加任何新元素。如果我们制作一个比主题数量大得多的数组，那么数组中的大部分可能仍然是空的。我们减少了空间浪费，形成链表，只在引入新元素时添加一个节点。使用链表，插入和删除也变得更容易。 链表的一大缺点是，不允许随机访问。使用数组，我们可以在O（1）时间内访问第i个元素。在链表中，它需要Θ（i）时间。

堆栈

堆栈或后进先出（last-in，first-out）是一种抽象数据类型，用作元素的集合，它有两个主要操作：push（向集合中添加元素）和pop（删除最后添加的元素）。在堆栈中，推送和弹出操作都在堆栈顶部的同一端进行。它可以通过使用数组和链表来实现。

Insertion : O(1)Deletion :  O(1)Access Time : O(n) [Worst Case]Insertion and Deletion are allowed on one end. 

例子： 堆栈用于维护函数调用（最后一个被调用的函数必须先完成执行），我们总是可以借助堆栈删除递归。堆栈还用于必须反转单词、检查平衡括号的情况，以及在编辑器中使用撤消操作时首先删除最后键入的单词的情况。类似地，在web浏览器中实现back功能。

队列

队列或FIFO（先进先出）是一种抽象数据类型，用作元素的集合，有两个主要操作：排队，即向集合中添加元素的过程。（该元素是从后侧添加的）并退出删除添加的第一个元素的过程。（从正面拆下滤芯）。它可以通过使用数组和链表来实现。

Insertion : O(1)Deletion  : O(1)Access Time : O(n) [Worst Case]

例子： Queue，顾名思义，是根据公交车站或火车的队列而构建的数据结构，站在队列前面（站立时间最长）的人是第一个拿到车票的人。因此，在任何情况下，资源在多个用户之间共享，并以先到先得的方式提供服务。例如CPU调度、磁盘调度。队列的另一个应用是在两个进程之间异步传输数据（数据不一定以与发送相同的速率接收）。例如IO缓冲区、管道、文件IO等。

循环队列 这种数据结构的优点是，在数组实现的情况下，它减少了空间浪费，因为如果第（n+1）个元素为空，则在第0个索引处插入该元素。

数据结构概述|集合2（二叉树、BST、堆和哈希）

本文由 阿比拉伊·斯密特 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。