How does LinkedList work internally?

A LinkedList is a linear data structure that stores elements in a sequential manner, but unlike an array, it doesn't store elements in contiguous memory locations. Instead, each element in a LinkedList is a node that contains data and a reference (or pointer) to the next node in the sequence.

Understanding the Structure

Imagine a chain of linked rings. Each ring represents a node in the LinkedList, and the connection between rings represents the reference to the next node.

Node: A node is the fundamental building block of a LinkedList. It typically consists of two parts:
- Data: The actual value stored in the node.
- Reference: A pointer or link to the next node in the list.
Head: The head node is the starting point of the LinkedList. It is the first node in the sequence and serves as the entry point for accessing the list.
Tail: The tail node is the last node in the LinkedList. It has a null reference, indicating the end of the list.

Operations in a LinkedList

Here are some common operations performed on a LinkedList:

Insertion: To insert a new node, you need to modify the references of existing nodes. You find the node before the desired insertion point, update its reference to point to the new node, and then set the new node's reference to point to the node that was originally after the insertion point.
Deletion: To delete a node, you need to adjust the references of the nodes before and after the node to be deleted. The node before the deleted node points to the node after the deleted node, effectively removing the deleted node from the chain.
Traversal: Traversing a LinkedList involves iterating through each node, starting from the head node and following the references to the next node until you reach the tail node.

Advantages of LinkedLists

Dynamic Size: LinkedLists can grow or shrink dynamically as needed, unlike arrays which have a fixed size.
Efficient Insertion and Deletion: Insertion and deletion operations are more efficient than arrays, especially when inserting or deleting elements at the beginning or middle of the list.
Memory Flexibility: LinkedLists don't require contiguous memory locations, allowing for better memory utilization.

Disadvantages of LinkedLists

Random Access: Accessing a specific node by its index requires traversing the list from the head, making random access less efficient than arrays.
Memory Overhead: Each node in a LinkedList requires additional memory for storing the reference to the next node.

Example

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

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

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

  def print_list(self):
    current = self.head
    while current:
      print(current.data, end=" ")
      current = current.next

# Example usage
my_list = LinkedList()
my_list.insert_at_beginning(5)
my_list.insert_at_beginning(10)
my_list.insert_at_beginning(15)
my_list.print_list()  # Output: 15 10 5

A2oz