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.

        C++ STL <queue>

Java Queue

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s