Data Structures Explained: Arrays, Linked Lists, and More

Understanding data structures is crucial for efficient programming. This guide covers fundamental data structures every programmer should know.

Arrays

Arrays store elements in contiguous memory locations:

python
# Python list (dynamic array)
numbers = [1, 2, 3, 4, 5]
numbers.append(6)  # O(1) amortized

Time Complexity:

• Access: O(1)
• Search: O(n)
• Insert/Delete: O(n)

Linked Lists

Linked lists store elements with pointers to next elements:

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

class LinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

Time Complexity:

• Access: O(n)
• Search: O(n)
• Insert/Delete at head: O(1)

Stacks and Queues

Stack (LIFO):

• Push: Add to top
• Pop: Remove from top

Queue (FIFO):

• Enqueue: Add to rear
• Dequeue: Remove from front

Trees and Graphs

Binary Trees:

• Each node has at most two children
• Binary Search Trees (BST) enable O(log n) operations

Graphs:

• Collections of nodes connected by edges
• Used for networks, social connections, maps

Choosing the Right Data Structure

| Operation | Array | LinkedList | Stack | Queue | |-----------|-------|------------|-------|-------| | Access | O(1) | O(n) | O(n) | O(n) | | Search | O(n) | O(n) | O(n) | O(n) | | Insert | O(n) | O(1) | O(1) | O(1) | | Delete | O(n) | O(1) | O(1) | O(1) |