Data Structures

Data Structures refer to specialized objects, that help us represent and manipulate data in a way that is efficient and easy to understand.
Data management is done by adding, removing, or updating data in the data structure.
The choice of a particular data structure depends on the nature of the data, the operations to be performed, and the efficiency requirements of those operations.

Data structures divide into 2 parts.

Linear Data Structures - data elements are arranged sequentially or linearly, where each element is connected to its previous and next element.
Non-Linear Data Structures - data elements are not arranged in a sequential manner.

Linear Data Structures

• Array - each element is identified by an index. The elements of an array are stored in contiguous memory locations.

  Static Array - has a fixed size, which is defined at the time of declaration.
  Dynamic Array - can grow or shrink in size, depending on the number of elements in the array. In JS, the Array object is a dynamic array.

• Linked List - each element is connected to the next element using pointers. The elements of a linked list are stored in non-contiguous memory locations.
  
  

  • Singly Linked List
    

  • Doubly Linked Lis (with UI)
    

---

The differences of the Linked List from Array is:

1. accessing elements - the array is faster than the linked list - array O(1) vs linked list O(n).
2. inserting or deleting elements - the linked list is faster than the array - array O(n) vs linked list O(1).
3. the size of a linked list is not fixed - it can grow or shrink in size.
4. memory allocation - the linked list uses more memory than the array.

---

• Stack - Last-In-First-Out (LIFO) principle.

• Queue - Last-In-First-Out (FIFO) principle.

  • Queue with Array
  • Queue with two Stacks

• Hash Table - is a data structure that stores data in key-value pairs. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Non-Linear Data Structures

• Trees - are hierarchical data structures consisting of nodes, with a single node as a root. Each node can have zero or more child nodes. Examples of usages in programming are - The HTML DOM model, Situation analysis in artificial intelligence, File folders in operating systems.

  • Binary Tree - each node has a maximum of two children, referred to as the left child and the right child.

  • Binary Search Tree - each node that descends to the left side of its parent must have a value less than its parent, and each node that descends to the right side of its parent must have a value bigger than its parent.
    
    

---

The differences of Binary tree from Binary search tree is:

1. searching - the binary search tree is faster than the binary tree as the binary search tree structure allows us to ignore half of the tree at each step - binary tree O(n) vs binary search tree O(log n).
2. duplicates - the binary search tree does not allow duplicates, while the binary tree does.

---

• Graphs - consists of nodes and edges. The nodes are connected by edges. Examples of usages in programming are - Social networks, Maps, Routing algorithms. In comparison to trees, graphs can have cycles, and the nodes can have multiple parents.

  • Directed Graph - edges have a direction.
  • Undirected Graph - edges do not have a direction.
  • Weighted Graph - edges have a weight meaning that we can weight edges to represent the distance between nodes.
  • Unweighted Graph - edges do not have a weight.
    
    

  Consider this example of a graph with 5 vertices and 5 edges:
  
  
  

  There are two ways to represent a graph.

1. Adjacency Matrix - a 2D array of size V x V, where V is the number of vertices in the graph. If there is an edge between vertices i and j, then the value of the matrix at row i and column j will be 1.
   
2. Adjacency List - an array of linked lists, where the size of the array is equal to the number of vertices in the graph. Each element of the array is a linked list that contains all the vertices that are adjacent to the vertex represented by the array index.