What are the main differences between an array and a linked list in data structures?

An array and a linked list are two fundamental data structures that differ in how they store and organize elements.

• Array — a contiguous block of memory where elements are stored sequentially. This allows for quick access to elements by index (access operation O(1)). However, the size of the array is fixed, and adding or removing elements in the middle requires shifting elements, which is time-consuming (O(n)).

• Linked list consists of nodes, each containing data and a reference to the next node. Elements may not be stored contiguously in memory. Adding and removing elements in the list is fast (O(1)) if there is a reference to the required node, but accessing an element by index requires sequential traversal (O(n)).

Example:

# Array in Python (list)
arr = [1, 2, 3, 4]
print(arr[2])  # Fast access to element at index 2

# Linked list (simplified example)
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# Accessing an element requires traversal
current = head
for _ in range(2):
    current = current.next
print(current.data)