数据结构概述|S1（线性数据结构）

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

1.数组

2.链表

3.栈

4.队列

Array

数组是一种数据结构, 用于在连续位置存储同类元素。在存储数据之前必须提供数组的大小。

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.单链表：

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

2.双链表：在这种类型的链接列表中, 每个节点都有两个引用, 一个引用指向下一个节点, 一个指向上一个节点。这种数据结构的优势在于, 我们可以在两个方向上遍历, 对于删除, 我们不需要显式访问上一个节点。例如。 NULL <-1 <-> 2 <-> 3-> NULL

3.通报链表：圆形链表是一个链表, 其中所有节点都连接在一起形成一个圆。最后没有NULL。循环链表可以是单循环链表或双循环链表。这种数据结构的优点是任何节点都可以作为起始节点。这在实现链表中的循环队列时很有用。例如。 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)时间。

叠放

堆栈或LIFO(后进先出)是用作元素集合的抽象数据类型, 它具有两个主要操作：push(向集合中添加一个元素)和pop(移除)最后添加的元素。在堆栈中, 推入和弹出操作都发生在堆栈顶部的同一端。可以同时使用数组和链接列表来实现。

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

示例：堆栈用于维护函数调用(最后一个调用的函数必须先完成执行), 我们总是可以借助堆栈来删除递归。在必须反转单词, 检查括号是否平衡的情况下, 以及在使用撤消操作时最后输入的单词是第一个被删除的编辑器中, 也会使用堆栈。同样, 在Web浏览器中实现后退功能。

队列

队列或FIFO(先进先出)是一种抽象数据类型, 用作元素的集合, 具有两个主要操作：队列, 将元素添加到集合的过程(元素从背面添加) )并出队, 即删除添加的第一个元素的过程。 (该元素已从正面移除)。可以同时使用数组和链接列表来实现。

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

示例：顾名思义, 队列是根据公交车站或火车的队列建立的数据结构, 其中站在队列前面(站立时间最长)的人是第一个获得车票的人。因此, 在多个用户之间共享资源并在先到先得的基础上提供服务的任何情况。示例包括CPU调度, 磁盘调度。队列的另一种应用是在两个进程之间异步传输数据(不一定以与发送数据相同的速率接收数据)。示例包括IO缓冲区, 管道, 文件IO等。

循环队列这种数据结构的优点是可以减少数组实现时的空间浪费, 因为如果第(n + 1)个元素为空, 则在第0个索引处进行插入。

数据结构概述|S2(二叉树, BST, 堆和哈希)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。