Array in Python | Array vs Linked List

Understanding the fundamental data structures is crucial for any programmer or software developer. Two of the most common and essential data structures are arrays and linked lists.

In this article, we will explore what arrays are, how they differ from linked lists, and provide clear Python examples to help you grasp these concepts.

What is an Array?

An array is a fixed-size collection of elements of the same data type, stored in contiguous memory locations. Arrays are simple yet powerful data structures that allow for efficient random access to elements.

Key Features of Arrays:

• Fixed Size: The size of an array is defined when it is created and cannot be changed.
• Efficient Access: Accessing any element in an array is fast and takes constant time (O(1)).
• Homogeneous Elements: All elements in an array are of the same data type.

Real-World Example of an Array

Consider an online store’s shopping cart, where each item added to the cart is represented by a unique product ID. We can use an array to store these product IDs.

Python Code Example

# Example: Shopping Cart
shopping_cart = [101, 102, 103, 104]  # Array of product IDs

# Accessing elements
print(shopping_cart[0])  # Output: 101
print(shopping_cart[2])  # Output: 103

# Adding an element (Note: This creates a new array since arrays are fixed-size)
shopping_cart = shopping_cart + [105]
print(shopping_cart)  # Output: [101, 102, 103, 104, 105]

In this example, we create an array to store product IDs. We can access any product ID quickly using its index. However, adding a new item to the array requires creating a new array because arrays have a fixed size.

What is a Linked List?

A linked list is a dynamic data structure consisting of nodes, where each node contains data and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists can grow and shrink in size as needed.

Key Features of Linked Lists:

• Dynamic Size: Linked lists can easily grow or shrink in size by adding or removing nodes.
• Efficient Insertions/Deletions: Adding or removing elements is efficient (O(1)) if the position is known.
• Sequential Access: Elements must be accessed sequentially, which means accessing an element takes linear time (O(n)).

Real-World Example of a Linked List

Consider a social media news feed, where new posts are added in chronological order. Each post can be represented as a node in a linked list.

Python Code Example

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 print_list(self):
        current = self.head
        while current:
            print(current.data, end=' -> ')
            current = current.next
        print('None')

# Example: Social Media News Feed
news_feed = LinkedList()
news_feed.append('Post 1')
news_feed.append('Post 2')
news_feed.append('Post 3')

news_feed.print_list()  # Output: Post 1 -> Post 2 -> Post 3 -> None

In this example, we create a linked list to store posts in a social media news feed. Each post is a node that points to the next post, forming a sequence. Linked lists allow easy insertion of new posts without needing to resize the structure.

Array vs. Linked List

Both arrays and linked lists are used to store collections of data, but they have different strengths and weaknesses. Here’s a comparison to help you understand when to use each:

Comparison Table

Feature	Array	Linked List
Size	Fixed	Dynamic
Memory Allocation	Contiguous	Non-contiguous
Access Time	O(1) for random access	O(n) for sequential access
Insertions/Deletions	Costly (O(n) if not at the end)	Efficient (O(1) if position is known)
Memory Overhead	Lower (no extra memory for pointers)	Higher (extra memory for pointers)
Use Case	When the number of elements is known and fixed	When the number of elements changes frequently

When to Use Arrays

• Fixed Size: When the number of elements is known in advance and does not change.
• Fast Access: When you need fast access to elements using their index.

When to Use Linked Lists

• Dynamic Size: When the number of elements changes frequently.
• Frequent Insertions/Deletions: When you need to insert or delete elements often.

Conclusion

Arrays and linked lists are fundamental data structures each suited to different scenarios. Arrays offer fast access and are ideal for fixed-size collections, while linked lists provide flexibility and efficiency for dynamic data. Understanding the differences between them helps in selecting the right data structure for your specific needs.

By mastering these basic data structures, you lay the foundation for more advanced concepts in computer science and software development. Experiment with the provided Python examples to deepen your understanding and become more proficient in handling data structures.