Data structures are fundamental computer science concepts for storing, organizing, and managing data efficiently. They directly impact how quickly and easily you can access, process, and modify your data. Choosing the right data structure for a given problem is crucial, as it can significantly affect both performance and memory usage.
We introduced the hashed table data structure in Chapter VI. Another core type of structure is the array, a fixed-size sequence of elements stored contiguously in memory. In Python, lists function as dynamic arrays, allowing for efficient indexing and automated resizing, while tuples are immutable sequences offering similar indexing performance. Beyond these, a wide range of data structures exist: linked lists, trees, stacks, queues, and graphs. Each structure has distinct strengths and use cases—for example, trees are excellent for hierarchical data, stacks and queues impose specific access patterns (LIFO and FIFO, respectively), and graphs model interconnected relationships.
A linked list is a linear collection of nodes, where each node contains two parts: the data value and a reference (pointer) to the next node. The advantage of linked lists is that they support dynamic sizing and allow fast insertions and deletions at any position if you already have a reference to the node. However, accessing or searching for an element typically requires sequential traversal from the head node, which can be less efficient than arrays when frequent random access is needed.
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
@staticmethod
def create_node(value):
return Node(value)
def append(self, value):
new_node = self.create_node(value)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
def prepend(self, value):
new_node = self.create_node(value)
new_node.next = self.head
self.head = new_node
def delete(self, value):
if not self.head:
return
if self.head.value == value:
self.head = self.head.next
return
current = self.head
next_node = current.next
while next_node and next_node.value != value:
current = next_node
next_node = current.next
if next_node:
current.next = next_node.next
def __str__(self):
values = []
current = self.head
while current:
values.append(str(current.value))
current = current.next
return ' -> '.join(values) + " -> None"
linked_list = LinkedList()
linked_list.append(42)
linked_list.append("Mango")
linked_list.prepend(3.14)
print(linked_list)
linked_list.delete(3.14)
print(linked_list)
An array is a collection of elements in contiguous memory locations, providing
constant-time
indexing (O(1) for retrieval by position). However, the size of an array is fixed at creation.
In Python, you can use the array module for compact numerical arrays. Python’s built-in
list type is not a low-level array, but a dynamic array that automatically resizes to
accommodate additional elements.
import array
# Create an array of integers
arr = array.array('i', [1, 2, 3, 4, 5])
# Access elements
print(arr[0]) # Output: 1
# Modify elements
arr[1] = 10
# Append elements
arr.append(6)
# Delete elements
arr.remove(3)
print(arr)
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle.
New elements are “pushed” onto the top of the stack and “popped” from the top. In Python, stacks are often
implemented using lists, leveraging append() and pop(). They’re useful in
scenarios like undo mechanisms, parsing expressions, and certain recursive-like processes.
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return not self.items
def push(self, item):
self.items.append(item)
print(f'Pushed {item} to stack.')
def pop(self):
if not self.is_empty():
item = self.items.pop()
print(f'Popped {item} from stack.')
return item
print('Stack is empty.')
return None
def peek(self):
if not self.is_empty():
return self.items[-1]
print('Stack is empty.')
return None
def __str__(self):
return 'Stack: ' + ' -> '.join(map(str, self.items)) + ' -> None'
# Example usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack)
stack.pop()
print(stack)
A queue is a linear data structure based on the First In, First Out (FIFO) principle.
Elements are added, or "enqueued," at the back and removed, or "dequeued," from the front. This structure
is handy for breadth-first searches (BFS), scheduling tasks, and buffering data. In Python, the
collections.deque class is a common choice for implementing queues efficiently.
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def is_empty(self):
return not self.items
def enqueue(self, item):
self.items.append(item)
print(f'Enqueued {item} to queue.')
def dequeue(self):
if not self.is_empty():
item = self.items.popleft()
print(f'Dequeued {item} from queue.')
return item
print('Queue is empty.')
return None
def peek(self):
if not self.is_empty():
return self.items[0]
print('Queue is empty.')
return None
def __str__(self):
return 'Queue: ' + ' -> '.join(map(str, self.items)) + ' -> None'
# Example usage
queue = Queue()
queue.enqueue('A')
queue.enqueue('B')
queue.enqueue('C')
print(queue)
queue.dequeue()
print(queue)
A tree is a hierarchical data structure composed of nodes, where each node may have zero or more child nodes. A particularly common form is the binary tree, where each node has up to two children. Trees have a wide range of applications, including file systems, databases, game development (e.g., AI decision trees), and search algorithms (e.g., binary search trees).
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, value):
if not self.root:
self.root = TreeNode(value)
print(f'Inserted root node with value {value}.')
else:
self._insert_recursive(self.root, value)
def _insert_recursive(self, current, value):
if value < current.value:
if current.left:
self._insert_recursive(current.left, value)
else:
current.left = TreeNode(value)
print(f'Inserted node with value {value} to the left of {current.value}.')
else:
if current.right:
self._insert_recursive(current.right, value)
else:
current.right = TreeNode(value)
print(f'Inserted node with value {value} to the right of {current.value}.')
def inorder_traversal(self):
elements = []
self._inorder_recursive(self.root, elements)
return elements
def _inorder_recursive(self, current, elements):
if current:
self._inorder_recursive(current.left, elements)
elements.append(current.value)
self._inorder_recursive(current.right, elements)
def __str__(self):
return 'Inorder Traversal: ' + ' -> '.join(map(str, self.inorder_traversal())) + ' -> None'
# Example usage
tree = BinaryTree()
tree.insert(10)
tree.insert(5)
tree.insert(15)
tree.insert(3)
tree.insert(7)
tree.insert(12)
tree.insert(18)
print(tree)
If you’re leveraging AI to generate data structure implementations, start with a precise prompt describing your requirements and the context. Instead of asking, “How do I use data structures?”, try: “Can you help me implement a linked list in Python with methods for adding, deleting, and displaying nodes?” The more detail you provide—including how you plan to use the data structure and why— the more targeted and helpful the generated code will be. You can also ask for comparisons, such as: “What are the differences between linked lists and arrays, and when is each preferable?”
Example Prompt:Resulting AI-generated code:
def create_node(value, next_node=None):
return {'value': value, 'next': next_node}
def append(head, value):
if head is None:
return create_node(value)
current = head
while current['next'] is not None:
current = current['next']
current['next'] = create_node(value)
return head
def prepend(head, value):
new_node = create_node(value, head)
return new_node
def delete_node(head, value):
if head is None:
return None
if head['value'] == value:
return head['next']
current = head
while current['next'] is not None and current['next']['value'] != value:
current = current['next']
if current['next'] is not None:
current['next'] = current['next']['next']
return head
def display(head):
current = head
values = []
while current is not None:
values.append(str(current['value']))
current = current['next']
return ' -> '.join(values) + ' -> None'
# Example usage
head = None
head = append(head, 42)
head = append(head, "Mango")
head = prepend(head, 3.14)
print(display(head))
head = delete_node(head, 3.14)
print(display(head))