Data Structures

A data structure is a particular way of organizing data in a computer so that it can be used effectively.
Try to avoid from envisioning data structures as drawings. It will make it more difficult to use complex data structures and implementation of algorithms.
‍
There are types of data structures:

Linear Data Structures

A linear data structure is one where data items are arragend in a linear fashion.
Each member is attached to its neighboring elements.

Array

Array is a data structure used to store elements at contiguous locations.
Size of an array must be provided before storing data.

When To Use :

• Data size is known
• Need index to access elements

Matrix

A matrix represents a collection of numbers arranged in an order of rows and columns.
It is necessary to enclose the elements of a matrix in parentheses or brackets.

When to use:

• Need for rows and columns identifiers

Linked List

A linked list is a linear data structure (like arrays) where each element is a separate object.
Each element (that is a node) of a list is comprising of two items – the data and a reference to the next node.

There are multiple types of linked list :

• Singly Linked List
  In this type of linked list, every node stores address or reference of next node in list and the last node has next address or reference as NULL.
  For example 1->2->3->4->NULL
  ‍
• Doubly Linked List
  In this type of Linked list, there are two references associated with each node, One of the reference points to the next node and one to the previous node.
  ‍
  Advantage of this data structure is that we can traverse in both the directions and for deletion we don’t need to have explicit access to previous node.
  ‍
  Eg. NULL<-1<->2<->3->NULL
  ‍
• Circular Linked List
  Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end.
  A circular linked list can be a singly circular linked list or doubly circular linked list.
  ‍
  Advantage of this data structure is that any node can be made as starting node.
  This is useful in implementation of circular queue in linked list.
  ‍
  Eg. 1->2->3->1 [The next pointer of last node is pointing to the first]

Methods:

• Append - add element to end of list
• Remove - remove element from list
• Len - return total elements in list

When to use:

• Data is dynamically changing
• Constant add, delete, search elements

Stack

A stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the last element that was added.

In stack both the operations of push and pop takes place at the same end that is top of the stack.

It can be implemented by using both array and linked list.

Methods :

• Push : Pushes an element on the top of the stack.
• Pop: Removes and returns the top element of the stack.
• Peek : Returns the element on the top of the stack, but does not remove it.
• Empty : Returns true if nothing is on the top of the stack. Else, returns false.

When to use:

• Need for LIFO (Like when backtracking operations)

Queue

A queue or FIFO (first in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: enqueue, the process of adding an element to the collection (The element is added from the rear side) and dequeue, the process of removing the first element that was added. (The element is removed from the front side).

It can be implemented by using both array and linked list.

Methods :
‍

• Add - This method is used to add elements at the tail of queue.
• Remove - This method removes and returns the head of the queue.
• Peek - This method is used to view the head of queue without removing it.
• Empty : Returns true if the queue is empty and false if not empty

When to use:

• Need for FIFO (like in multithreading with locks)

Double-ended queue is abstract data type that generalizes a queue, for which elements can be added to or removed from either the front or back.

Hierarchical Data Structures

Hierarchical data is a data structure when items are linked to each other in parent-child relationships in an overall tree structure.

Binary Tree

Data structure in which each node has at most two children, which are referred to as the left child and the right child.

A tree is represented by a pointer to the topmost node in tree. If the tree is empty, then value of root is NULL.

A Binary Tree node contains following parts:

• Data
• Pointer to left child
• Pointer to right child

A Binary Tree can be traversed in several ways:

• Depth First Traversal: Inorder (Left-Root-Right)
• Preorder (Root-Left-Right)
• Postorder (Left-Right-Root)
• Breadth First Traversal: Level Order Traversal

In Binary Search Tree is a Binary Tree with following additional properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

A Binary Heap is a Binary Tree with following properties:

• It’s a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible).
  This property of Binary Heap makes them suitable to be stored in an array.
• A Binary Heap is either Min Heap or Max Heap.
  In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap.
  The same property must be recursively true for all nodes in Binary Tree.
  Max Binary Heap is similar to Min Heap.

When to use:

• Need to sort data

Graph

A Graph is a non-linear data structure consisting of nodes and edges.
The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.

A Graph consists of a finite set of vertices(or nodes) and set of Edges which connect a pair of nodes.
It is good with OSPF (open shortest path first) algorithm .

When To Use :

• Graph represent the most successful the data.
  Graphs are used to solve many real-life problems.
  Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network.
  Graphs are also used in social networks like linkedIn, Facebook. For example, in Facebook, each person is represented with a vertex (or node). Each node is a structure and contains information like person id, name, gender, locale etc.
  Also it used when calculating shortest path between locations.

Additional links:

• How to build a graph data structure

Hash Table

Data structure which stores data in an associative manner.
In a hash table, data is stored in an array format, where each data value has its own unique index value.
Access of data becomes very fast if we know the index of the desired data.
Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the size of the data.
‍
Hash Table uses an array as a storage medium and uses hash technique to generate an index where an element is to be inserted or is to be located from.
‍Hashing is a technique to convert a range of key values into a range of indexes of an array (for example, use modulo or by last characters in strings).

Methods :

• Search - search for element
• Insert - insert element
• Delete - delete element
• hashCode - calculating key hash code

When to use:

• When hashing function makes search operation efficient