Arrays vs. Linked Lists: Which Is Better?

Just an Intro

Arrays and linked lists are two of the most fundamental data structures in computer science. They both have their advantages and disadvantages, and knowing when to use one over the other can make a big difference in the efficiency of your code.

In this article, we'll explore some common use cases for both arrays and linked lists and how they apply in the real world.

Arrays: Fast & Furious

Arrays are one of the simplest and most widely used data structures in programming. They are essentially a collection of items that are stored in contiguous memory locations. This makes accessing and manipulating individual elements in an array very fast and efficient.

Arrays also have a fixed size, which means that they are perfect for storing a known number of items. It is worth noting that in some languages, like python, we have dynamic arrays so size is not always fixed.

One of the most common use cases for arrays is in storing and processing large amounts of data.

For example, if you were building a weather forecasting application for a city in Africa, you might use an array to store daily temperature readings for the past year. This would allow you to quickly access and manipulate individual temperature values for a particular day or range of days.

Another example of where arrays can be useful in Africa is in sorting large amounts of data. If you were building a logistics application to track the movement of goods across the continent, you might use an array to store the location and status of each shipment.

This would allow you to quickly sort and filter shipments based on their current status, such as "in transit" or "delivered."

Arrays are also very efficient when it comes to adding or removing elements at the end of the collection, which is known as an append operation. This is because appending to an array simply involves updating the size of the array and copying the new element to the end.

However, adding or removing elements in the middle of an array can be much slower, as it requires shifting all the subsequent elements by one position.

Linked Lists: Flexible and Adaptable

Linked lists are a more complex data structure that can be used in situations where the size of the collection is not known in advance or where elements need to be added or removed frequently.

A linked list consists of a sequence of nodes, each containing a value and a pointer to the next node in the list.

This makes linked lists more flexible than arrays, as they can be easily resized and modified without needing to move large amounts of data around.

One example of where linked lists might be useful is in managing healthcare records for a large hospital or clinic. Patients may need to be added or removed from the system at any time, and their medical history and treatment information may need to be updated frequently.

A linked list would allow healthcare providers to easily add or remove patient records and modify their medical information as needed.

Another example of where linked lists can be useful is in building a social network or messaging application.

In these types of applications, users may need to be added or removed from the system at any time, and messages may need to be added or removed from their conversation threads.

A linked list would allow you to easily add or remove users and messages and keep track of the order in which they were added.

Linked lists also have some advantages over arrays when it comes to memory usage. Because linked lists only allocate memory for the nodes that are currently in use, they can be more memory-efficient than arrays for collections that are not always fully populated.

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        
class LinkedList:
    def __init__(self):
        self.head = None
        
    def append(self, data):
        new_node = Node(data)
        
        if self.head is None:
            self.head = new_node
            return
        
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
        
        current_node.next = new_node
        
    def insert(self, data, position):
        new_node = Node(data)
        
        if position == 0:
            new_node.next = self.head
            self.head = new_node
            return
        
        current_node = self.head
        current_position = 0
        
        while current_node.next is not None and current_position < position - 1:
            current_node = current_node.next
            current_position += 1
        
        new_node.next = current_node.next
        current_node.next = new_node
        
    def delete(self, data):
        if self.head is None:
            return
        
        if self.head.data == data:
            self.head = self.head.next
            return
        
        current_node = self.head
        while current_node.next is not None and current_node.next.data != data:
            current_node = current_node.next
        
        if current_node.next is not None:
            current_node.next = current_node.next.next
            
    def print_list(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next

Conclusion

In conclusion, the choice between using an array or a linked list depends on the specific requirements of your application. Arrays are best suited for situations where the size of the collection is known in advance and where elements need to be accessed or manipulated quickly.

Linked lists are more flexible and adaptable and are best suited for situations where the size of the collection is not known.