In this section, we will explore the different types of data structures that are commonly used in programming. Understanding these data structures is crucial for writing efficient and effective code. We will cover the following types:

1. Linear Data Structures
2. Non-Linear Data Structures

Linear data structures are those in which data elements are arranged sequentially or linearly, where each element is connected to its previous and next element. Here are some common linear data structures:

• Definition: An array is a collection of elements identified by index or key.
• Characteristics:
  • Fixed size.
  • Elements are stored in contiguous memory locations.
  • Allows random access to elements.
• Example:

  # Example of an array in Python
  array = [1, 2, 3, 4, 5]
  print(array[2])  # Output: 3
  

• Definition: A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node.
• Characteristics:
  • Dynamic size.
  • Elements are not stored in contiguous memory locations.
  • Allows easy insertion and deletion.
• Example:

  # Node class for a linked list
  class Node:
      def __init__(self, data):
          self.data = data
          self.next = None
  
  # Linked list class
  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
  
  # Creating a linked list and appending elements
  ll = LinkedList()
  ll.append(1)
  ll.append(2)
  ll.append(3)
  

• Definition: A stack is a linear data structure that follows the Last In First Out (LIFO) principle.
• Characteristics:
  • Elements are added and removed from the same end, called the "top".
  • Supports operations like push (add) and pop (remove).
• Example:

  # Stack implementation using a list
  stack = []
  stack.append(1)  # Push
  stack.append(2)
  stack.append(3)
  print(stack.pop())  # Output: 3 (Pop)
  

• Definition: A queue is a linear data structure that follows the First In First Out (FIFO) principle.
• Characteristics:
  • Elements are added at the rear and removed from the front.
  • Supports operations like enqueue (add) and dequeue (remove).
• Example:

  # Queue implementation using a list
  from collections import deque
  queue = deque()
  queue.append(1)  # Enqueue
  queue.append(2)
  queue.append(3)
  print(queue.popleft())  # Output: 1 (Dequeue)
  

Non-linear data structures are those in which data elements are not arranged sequentially. Here are some common non-linear data structures:

• Definition: A tree is a hierarchical data structure consisting of nodes, with a single node as the root and sub-nodes as children.
• Characteristics:
  • Each node contains data and references to its children.
  • Used to represent hierarchical relationships.
• Example:

  # Node class for a tree
  class TreeNode:
      def __init__(self, data):
          self.data = data
          self.children = []
  
      def add_child(self, child):
          self.children.append(child)
  
  # Creating a tree
  root = TreeNode('root')
  child1 = TreeNode('child1')
  child2 = TreeNode('child2')
  root.add_child(child1)
  root.add_child(child2)
  

• Definition: A graph is a collection of nodes (vertices) and edges connecting pairs of nodes.
• Characteristics:
  • Can be directed or undirected.
  • Used to represent networks.
• Example:

  # Graph representation using an adjacency list
  graph = {
      'A': ['B', 'C'],
      'B': ['A', 'D', 'E'],
      'C': ['A', 'F'],
      'D': ['B'],
      'E': ['B', 'F'],
      'F': ['C', 'E']
  }
  

In this section, we covered the two main types of data structures: linear and non-linear. Linear data structures include arrays, linked lists, stacks, and queues, which are characterized by their sequential arrangement of elements. Non-linear data structures include trees and graphs, which are used to represent hierarchical and networked relationships, respectively.

Understanding these data structures and their characteristics is fundamental for efficient programming and problem-solving. In the following modules, we will delve deeper into each of these data structures, exploring their implementations, operations, and applications.