Data Structures

Data structures are different ways of storing data. After various years of research many people have come up with the following different kind of DS. These different DS are used based on the requirement. DS is chosen based on the problem.

In this blog we will look at the different structures which are helpful to tackle various computing problem. I have tried to put little information about all DS available, In future I will try to explain each one of them with their various versions. Hope it will help me to understand DS more.

Data Structure	Fields	Operations	Time Complexity	Pros	Cons	Comments
Array	MAX_CAPACITY	add(index, value) – On the specified index add the value.	O(1)	Index based Retrieval	1. Fixed Size of Array.	Arrays are the oldest and most DS. It is used to implement most of the other datastructures.
	index	delete(index) – Delete at specified index.	O(1)		2. Complex position based insertion
	objects[]	search(value) – Search the value.	O(n)		3. One block Allocation. It is not possible to use scattered memory with arrays
Linked List	Node{ Data, nextNode}	Insert – Add value at head.	O(1)	1. Linear Access	1. Retrieval at any index is slower wrt to Arrays.
	head of Node type	Delete – Search and delete the value.	O(n)	2. Does not need continuous memory locations.	2. Complex to use.	Linked list are useful when user is concentrating on insert operation instead index based retrieval.
		Search – Search the value.	O(n)	3. Size of the list is not fixed.
Stacks	MAX_CAPACITY	IsEmpty – If CURRENT_INDEX = -1	O(1)			Stacks works on last in first out methodology... Stacks are widely used in computer programming.
	CURRENT_INDEX	isFull CURRENT_INDEX = MAX_CAPACITY	O(1)			Stacks are used to validate compile time programs.
	objects[]	Push – Insert a object in array.	O(1)			Infix/postfix/prefix evaluation is done using stacks.
		Pop – removes a object and returns its value.	O(1)
Queue	MAX_CAPACITY	isEmpty – If HEAD = TAIL	O(1)			Queue works on First In/First out methodology.
	HEAD	isFull |HEAD - TAIL| = MAX_CAPACITY	O(1)			Queue are used to maintain threads.
	TAIL	Enqueue – inserting the record at head.	O(1)
	objects[]	Dequeue – Deletng the record from tail.	O(1)
Tree	Node{ Data, Node1, Node2, Node3 ....}	add(value) – Based on property of the tree add the node accordinly.	O(log(n))	1. Insertion is faster than array but slower than linked list.	1. Difficult to maintain the balance of the tree.	Trees are used for solving lot of algorithmic problems. It is known as most important and efficient data structure to solve multiple issues.
	depth	Delete – Search and delete the value.	O(n)	2. Searching is faster.	2. Complex and confusion at times.
	Leaves – Nodes which do not have any children.	Search – Search the value.	O(log(n))	3. Used with lot of different data structures.
	Internal Nodes – Nodes having one or more children.			4. Solves lot of problems.
Graph	Map of vertices and it's accessible vertices.	adjacent(G, x, y): tests whether there is an edge from node x to node y.	O(K)			Graphs are generally used for greedy solutions.
		neighbors(G, x): lists all nodes y such that there is an edge from x to y.	O(K)			Shortest path algorithms.
		add(G, x, y): adds to G the edge from x to y, if it is not there.	O(K)
		delete(G, x, y): removes the edge from x to y, if it is there.	O(1)
HashTable	objects[]	add(value) – Adds the value to the array.	O(1)	Fast searching operations are performed.	Need efficient hashing algorithms, otherwise it can be painful to search objects.	It is widely used in Database Indexing and caching operations.
	MAX_SIZE	delete(value) – Removes the value from the array.	O(1)	Used when program deals with huge chunk of data.
		Search(value)	O(1)