Diving into Data Structures: Arrays, Linked Lists, and Trees in Python

Introduction to Data Structures

Data structures organize and store data in a way that allows efficient access and modification. Understanding data structures is key to building efficient algorithms and applications. In this post, we’ll explore three foundational data structures: arrays, linked lists, and trees, using Python examples to illustrate each.

Arrays

An array is a collection of elements stored at contiguous memory locations, making it easy to access each element using an index. Python has built-in support for lists, which work like dynamic arrays:

# Creating an array (list) in Python
array = [1, 2, 3, 4, 5]
print("Array:", array)

# Accessing elements by index
print("First element:", array[0])

# Adding an element
array.append(6)
print("Array after appending:", array)

Arrays provide constant-time access for reads and writes by index, but resizing them can be costly. They are ideal for ordered data where fast access is important.

Linked Lists

A linked list is a linear data structure where elements, known as nodes, contain both data and a reference to the next node. Unlike arrays, linked lists do not store elements in contiguous memory locations, making them efficient for dynamic memory allocation.

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

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Creating and displaying a linked list
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display()

Linked lists are excellent for applications where data needs frequent insertions and deletions, but they lack direct access to elements by index, making them slower for searching.

Trees

A tree is a hierarchical data structure that consists of nodes, with a root node at the top and child nodes branching down. A common type is the binary tree, where each node has at most two children (left and right). Trees are useful for representing hierarchical data.

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

# Creating a binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)

# Function to perform inorder traversal
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.data, end=" ")
        inorder_traversal(node.right)

# Displaying the tree using inorder traversal
print("Inorder Traversal:")
inorder_traversal(root)

Binary trees are highly flexible and are the basis for more advanced data structures like binary search trees and heaps. They are commonly used in applications such as parsers, expression evaluators, and file systems.

Conclusion

Understanding arrays, linked lists, and trees will give you a solid foundation in data structures. These structures are the building blocks of more complex algorithms and applications, enabling efficient data storage, access, and manipulation. Practice implementing these data structures to deepen your understanding and enhance your problem-solving skills.