Data Structures in Python

 Introduction to Data Structures

• Definition: A data structure is a way of organizing and storing data so it can be accessed and worked with efficiently.
• Purpose: Helps in managing large amounts of data efficiently for various operations like searching, sorting, and modifying data.

Types of Data Structures

Data structures are broadly divided into two categories:

1. Built-in Data Structures
2. User-defined Data Structures

1. Built-in Data Structures

These are provided by Python and are easy to use. They include:

a. Lists

• Definition: A list is an ordered collection of items, which can hold a mix of data types.
• Syntax:

  my_list = [1, 2, 3, 'apple', True]
  

• Key Operations:
  • Append: my_list.append(4)
  • Remove: my_list.remove(2)
  • Indexing: my_list[0] (gives 1)

b. Tuples

• Definition: A tuple is similar to a list but is immutable (cannot be changed).
• Syntax:

  my_tuple = (1, 2, 3, 'apple')
  

• Key Operations:
  • Accessing: my_tuple[1] (gives 2)

c. Sets

• Definition: A set is an unordered collection of unique items.
• Syntax:

  my_set = {1, 2, 3, 4}
  

• Key Operations:
  • Add: my_set.add(5)
  • Remove: my_set.remove(3)

d. Dictionaries

• Definition: A dictionary stores data in key-value pairs.
• Syntax:

  my_dict = {'name': 'John', 'age': 25}
  

• Key Operations:
  • Add/Update: my_dict['city'] = 'Delhi'
  • Access: my_dict['name'] (gives 'John')

2. User-defined Data Structures

These are created by the programmer to solve specific problems. Common examples include:

a. Stacks

• Definition: A stack follows the LIFO (Last In, First Out) principle.
• Implementation:

  stack = []
  stack.append(1)  # Push
  stack.pop()      # Pop
  

b. Queues

• Definition: A queue follows the FIFO (First In, First Out) principle.
• Implementation:

  from collections import deque
  queue = deque()
  queue.append(1)  # Enqueue
  queue.popleft()  # Dequeue
  

c. Linked Lists

• Definition: A linked list is a sequence of nodes where each node contains data and a reference to the next node.
• Implementation:

  class Node:
      def __init__(self, data):
          self.data = data
          self.next = None
  
  class LinkedList:
      def __init__(self):
          self.head = None
  

d. Trees

• Definition: A tree is a hierarchical data structure with a root node and child nodes.
• Types: Binary Trees, Binary Search Trees, etc.
• Implementation:

  class Node:
      def __init__(self, data):
          self.data = data
          self.left = None
          self.right = None
  

e. Graphs

• Definition: A graph is a set of nodes (vertices) connected by edges.
• Representation: Adjacency Matrix, Adjacency List

  graph = {
      'A': ['B', 'C'],
      'B': ['A', 'D'],
      'C': ['A', 'D'],
      'D': ['B', 'C']
  }
  

Choosing the Right Data Structure

• List: When you need an ordered, mutable collection.
• Tuple: When you need an ordered, immutable collection.
• Set: When you need a collection of unique items.
• Dictionary: When you need key-value pairs for fast lookups.
• Stack/Queue: When specific order of operations (LIFO/FIFO) is required.
• Trees/Graphs: When working with hierarchical or networked data.