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

2021年4月17日17:58:13 发表评论 494 次浏览

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

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]``````

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

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