Data Structures

Related Subjects: |Python |C |Java |C++ |C sharp |VB |Natural Language processing |How does a CPU work |Computer Networking |Computer Security |Concurrent Programming |Compilers |Cryptography |Data Structures |Database Management |Object orientated programming

Data structures are fundamental concepts in computer science that provide ways to store, organize, and manage data efficiently. They are essential for designing efficient algorithms and for solving complex computational problems. Understanding data structures is crucial for developing robust and high-performance software applications.

Types of Data Structures

• Linear Data Structures :
  • Elements are arranged in a sequential manner.
  • Examples: Arrays, Linked Lists, Stacks, Queues.
  • Example in Python:

  # Array
  arr = [1, 2, 3, 4, 5]
  # Linked List
  class Node:
   def __init__(self, data):
   self.data = data
   self.next = None
  class LinkedList:
   def __init__(self):
   self.head = None
   def append(self, data):
   new_node = Node(data)
   if not self.head:
   self.head = new_node
   return
   last = self.head
   while last.next:
   last = last.next
   last.next = new_node
  ll = LinkedList()
  ll.append(1)
  ll.append(2)
  ll.append(3)
   

• Non-Linear Data Structures :
  • Elements are arranged in a hierarchical manner.
  • Examples: Trees, Graphs.
  • Example in Python:

  # Binary Tree
  class TreeNode:
   def __init__(self, data):
   self.data = data
   self.left = None
   self.right = None
  root = TreeNode(1)
  root.left = TreeNode(2)
  root.right = TreeNode(3)
  root.left.left = TreeNode(4)
  root.left.right = TreeNode(5)
  # Graph using adjacency list
  class Graph:
   def __init__(self):
   self.graph = {}
   def add_edge(self, u, v):
   if u not in self.graph:
   self.graph[u] = []
   self.graph[u].append(v)
  g = Graph()
  g.add_edge(0, 1)
  g.add_edge(0, 2)
  g.add_edge(1, 2)
  g.add_edge(2, 0)
  g.add_edge(2, 3)
  g.add_edge(3, 3)
   

Common Data Structures

• Arrays :
  • Collection of elements identified by index or key.
  • Fixed size and contiguous memory allocation.
  • Example in Python:

  arr = [1, 2, 3, 4, 5]
  print(arr[2]) # Output: 3
   

• Linked Lists :
  • Collection of nodes where each node contains data and a reference to the next node.
  • Types: Singly Linked List, Doubly Linked List, Circular Linked List.
  • Example in Python:

  class Node:
   def __init__(self, data):
   self.data = data
   self.next = None
  class LinkedList:
   def __init__(self):
   self.head = None
   def append(self, data):
   new_node = Node(data)
   if not self.head:
   self.head = new_node
   return
   last = self.head
   while last.next:
   last = last.next
   last.next = new_node
  ll = LinkedList()
  ll.append(1)
  ll.append(2)
  ll.append(3)
   

• Stacks :
  • Linear data structure that follows Last In First Out (LIFO) principle.
  • Operations: push (add an element), pop (remove an element).
  • Example in Python:

  stack = []
  stack.append(1)
  stack.append(2)
  stack.append(3)
  print(stack.pop()) # Output: 3
   

• Queues :
  • Linear data structure that follows First In First Out (FIFO) principle.
  • Operations: enqueue (add an element), dequeue (remove an element).
  • Example in Python:

  from collections import deque
  queue = deque()
  queue.append(1)
  queue.append(2)
  queue.append(3)
  print(queue.popleft()) # Output: 1
   

• Trees :
  • Hierarchical data structure with a root node and child nodes forming a tree-like structure.
  • Types: Binary Tree, Binary Search Tree (BST), AVL Tree, Red-Black Tree.
  • Example of a Binary Tree in Python:

  class TreeNode:
   def __init__(self, data):
   self.data = data
   self.left = None
   self.right = None
  root = TreeNode(1)
  root.left = TreeNode(2)
  root.right = TreeNode(3)
  root.left.left = TreeNode(4)
  root.left.right = TreeNode(5)
   

• Graphs :
  • Collection of nodes (vertices) and edges connecting them.
  • Types: Directed Graph, Undirected Graph, Weighted Graph.
  • Example in Python using adjacency list:

  class Graph:
   def __init__(self):
   self.graph = {}
   def add_edge(self, u, v):
   if u not in self.graph:
   self.graph[u] = []
   self.graph[u].append(v)
  g = Graph()
  g.add_edge(0, 1)
  g.add_edge(0, 2)
  g.add_edge(1, 2)
  g.add_edge(2, 0)
  g.add_edge(2, 3)
  g.add_edge(3, 3)
   

• Hash Tables :
  • Data structure that maps keys to values using a hash function.
  • Provides average-case constant time complexity for lookups.
  • Example in Python using a dictionary:

  hash_table = {}
  hash_table["key1"] = "value1"
  hash_table["key2"] = "value2"
  print(hash_table["key1"]) # Output: value1
   

Applications of Data Structures

• Arrays and Lists :
  • Used in implementing other data structures like stacks, queues, and hash tables.
  • Efficient for indexed access to elements.
• Stacks :
  • Used in expression evaluation, backtracking algorithms, and function call management.
• Queues :
  • Used in scheduling algorithms, breadth-first search (BFS) in graphs, and buffering data streams.
• Trees :
  • Used in hierarchical data representation, search operations (e.g., BST), and memory management (e.g., heap).
• Graphs :
  • Used in network routing algorithms, social network analysis, and dependency resolution.
• Hash Tables :
  • Used in implementing associative arrays, database indexing, and caches.

Summary

Data structures are vital components in computer science, enabling efficient data storage, organization, and manipulation. Linear data structures include arrays, linked lists, stacks, and queues, while non-linear data structures include trees and graphs. Each data structure has its own set of operations and applications, making them suitable for various computational tasks. Understanding and implementing these data structures is essential for developing efficient algorithms and solving complex problems in computer science.