Data Structures

Types of Data Structures

• Arrays
• Linked list
• Single
• Double
• Circular
• Stack
• Queue
• Hash table
• Trees and Graphs
• Binary search tree

Array	Linked list
Dynamic array allocation requires effort. Need to use realloc	Dynamic allocation and de-allocation is easy
Entire array in stack or can be malloced and used in heap	Head in stack, ll in heap
Time to access any element is a constant	Time to access an element is related to how far it is located from the head

ARRAY:

• Contiguous space for same data type
• Need to take care of buffer flow. Do a boundary check wherever required

LINKED LIST

• Operations performed - add, delete, edit 
• In a single linked list, the best place to add a new element is the head of the list.
• Very important boundary condition is to check for empty  list case i.e head is null
• How to reverse a single linked list.? 

Sample solution
Node * reverse( Node * ptr )
{
Node * temp;
 Node * previous = NULL;
 while(ptr != NULL) {
     temp = ptr->next;
     ptr->next = previous;
     previous = ptr;
     ptr = temp;
    }
 return previous;

 }

HASH TABLE 

• Given a random set of data, hash table gives the optimum way to search for the data
• perform hash function on the key to get the index
• If multiple keys lead to the same index, we create a bucket with the index pointing a linked list of all possible entries. Parse through the linked list to fetch the desired entry

STACK:

• LIFO

QUEUE:

• FIFO

TREE:

Traversal methods

• Pre order      RoLR
• Inorder         LRoR
• Post order      LRRo

Search Methods

• BFS
• DFS