Linked Lists

• A data structure consisting of a sequence of elements, each containing a reference (link) to the next element in the sequence.
• Elements, commonly referred to as nodes, typically contain two fields: data and a pointer/reference to the next node.
• The first node is called the head, and the last node points to null, indicating the end of the list.

Advantages

• Dynamic Size: Can grow and shrink in size dynamically, making efficient use of memory.
• Ease of Insertion/Deletion: Adding or removing elements is more efficient than arrays (at the start position) as it involves only updating pointers (no need for shifting elements).

Disadvantages

• Memory Usage: Requires extra memory for storing pointers in addition to data.
• Access Time: Linear time complexity (O(n)) for accessing elements, as it requires traversal from the head to the desired node.
• Cache Locality: Poor cache performance due to non-contiguous memory allocation.

Real-Life Applications

• Implementation of Stacks and Queues: Using linked lists to manage dynamic datasets.
• Graph Adjacency List: Representation of graphs for efficient traversal and space utilization.
• Memory Management: Managing free memory blocks in operating systems.
• Music Playlists: Where each song points to the next, enabling easy addition/removal of songs.

Implementation

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

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

    def append(self, data):
        node = Node(data)
        
        if self.head is None:
            self.head = node
        else:    
            runner = self.head
        
            while runner.next is not None:
                runner = runner.next

            runner.next = node
        
    def remove(self, data):
        if self.head is None:
            return False
        
        if self.head.data == data:
            self.head = self.head.next
            return True
        
        previous = None
        runner = self.head
        
        while runner is not None and runner.data != data:
            previous = runner
            runner = runner.next
            
        # 'data' not found
        if runner is None:
            return False
        
        previous.next = runner.next
        return True
    
    def display(self):
        elements = []
        current = self.head
        
        while current is not None:
            elements.append(current.data)
            current = current.next

        print(elements)        

More code implementations of LinkedList (in all of your favourite languages - Java, Swift, C++) can be found here.

That's a wrap. Subscribe if you haven't already. Come back tomorrow for more.

And if you found this useful, share it with your friends.