Data Structures
Introduction
Data structures are fundamental for organizing and managing data efficiently in computer science. They help in storing data, processing data, and retrieving data in an effective manner. This tutorial covers the basic data structures used in programming and data science.
Arrays
An array is a collection of elements, each identified by an index or key. Arrays are used to store multiple values in a single variable.
Example in Python
Accessing an element:
Linked Lists
A linked list is a linear data structure where each element is a separate object, known as a node. Each node contains data and a reference to the next node in the sequence.
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_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def print_list(self):
cur_node = self.head
while cur_node:
print(cur_node.data)
cur_node = cur_node.next
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.print_list()
Stacks
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. Operations on a stack include push (adding an element), pop (removing an element), and peek (viewing the top element).
Example in Python
stack = []
# Push elements
stack.append(1)
stack.append(2)
stack.append(3)
# Pop elements
print(stack.pop()) # Output: 3
print(stack.pop()) # Output: 2
# Peek at the top element
print(stack[-1]) # Output: 1
Queues
A queue is a linear data structure that follows the First In First Out (FIFO) principle. Operations on a queue include enqueue (adding an element) and dequeue (removing an element).
Example in Python
from collections import deque
queue = deque()
# Enqueue elements
queue.append(1)
queue.append(2)
queue.append(3)
# Dequeue elements
print(queue.popleft()) # Output: 1
print(queue.popleft()) # Output: 2
# Peek at the front element
print(queue[0]) # Output: 3
Trees
A tree is a hierarchical data structure consisting of nodes, with a single node called the root. Each node can have zero or more child nodes. Trees are used in various applications like representing hierarchical data and in search algorithms.
Example in Python
class TreeNode:
def __init__(self, data):
self.data = data
self.children = []
self.parent = None
def add_child(self, child):
child.parent = self
self.children.append(child)
def print_tree(node, level=0):
print(' ' * level * 4, node.data)
for child in node.children:
print_tree(child, level + 1)
root = TreeNode("Root")
child1 = TreeNode("Child1")
child2 = TreeNode("Child2")
root.add_child(child1)
root.add_child(child2)
child1.add_child(TreeNode("Child1.1"))
child2.add_child(TreeNode("Child2.1"))
print_tree(root)
Graphs
A graph is a collection of nodes, called vertices, and edges that connect pairs of vertices. Graphs can be used to model networks, such as social networks or communication networks.
Example in Python
class Graph:
def __init__(self):
self.nodes = {}
def add_node(self, node):
self.nodes[node] = []
def add_edge(self, node1, node2):
self.nodes[node1].append(node2)
self.nodes[node2].append(node1)
def print_graph(self):
for node in self.nodes:
print(node, "->", self.nodes[node])
graph = Graph()
graph.add_node("A")
graph.add_node("B")
graph.add_node("C")
graph.add_edge("A", "B")
graph.add_edge("A", "C")
graph.add_edge("B", "C")
graph.print_graph()
Hash Tables
A hash table is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets, from which the desired value can be found.
Example in Python
hash_table = {}
# Adding key-value pairs
hash_table["name"] = "Alice"
hash_table["age"] = 25
# Accessing values
print(hash_table["name"]) # Output: Alice
print(hash_table["age"]) # Output: 25
# Deleting a key-value pair
del hash_table["age"]
print(hash_table) # Output: {'name': 'Alice'}