Introduction to Linear data Structures

Which data Structure is can be called as linear Data Structure ?

Data Structure is called linear, If its elements form a Sequence.

Array

This is most commonly used linear data structure, used for collection of sequential data to be stored and accessed using index.

memory requirements are array size + some extra buffer.

in c/c++

int array[100];

array is linear data structure with ((100*(size of int on respective machine)) + some buffer ) size

Dynamic Array

Dynamic Array overcomes array in terms of size restriction.

Dynamic array is auto-resizable.

Vector: C+ STL <vector> and Java ArrayList

Linked List:

Linked list is similar to array and dynamic array but it plays with pointers.

you can created and connect/ link two nodes two form list

variations of linked list includes Singly Linked List, Doubly Linked List.

Linked list is theoretically slow for accessing data.

C++ STL <list>

Stack

Stack only allows insertion and deletion from top. we can co-relate stack with keeping books in box open from top end only, so we can insert or remove from top. Not from in between and not from bottom. this is called as Last In First Out(LIFO) . insertion is refer to as push() and removal as pop(). Stack DS is used in problems like Postfix Calculations.

C++ STL <stack>

Java Stack

Queue

Queue allows insertion from front end and deletion from rear end. Imagine queue outside ATM people can enter queue from last end, after last person and as ATM gets available person from front end uses ATM. No person waiting in queue in between violates queue(Well, lets assume that). This is called as First In First Out(FIFO) . insertion is refer to as push() and removal as pop().

Queue is used in algorithms like Breadth First Search.