5 Best Ways to Add Elements to a Linked List in Python

💡 Problem Formulation: If you need to add elements into a linked list in Python, you will be dealing with inserting nodes at different points. You might want to add a node at the end, at the beginning, or even in between two existing nodes. For example, starting with a linked list 3 -> 5 -> 7, you may want to add an element 10 at the end to make it 3 -> 5 -> 7 -> 10.

Method 1: Appending Elements to the End of a Linked List

The append method allows us to add an element at the end of the linked list. This is useful when we want to maintain the order of elements and do not care about the position of the new element relative to others except that it should be last.

Here’s an 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_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

llist = LinkedList()
llist.append(3)
llist.append(5)
llist.append(7)

# Printing the linked list
current_node = llist.head
while current_node:
    print(current_node.data, end=" -> " if current_node.next else "")
    current_node = current_node.next

Output:

3 -> 5 -> 7

In this code, we define a Node class and a LinkedList class with an append method. This method creates a new node and iteratively traverses to the end of the list to add it, handling an empty list case as well.

Method 2: Prepending Elements to the Start of a Linked List

Prepending is the process of adding an element at the beginning of the linked list. This operation is generally faster than appending as you don’t need to traverse the whole list.

Here’s an example:

class LinkedList:
    # Assuming Node class and __init__ method are already defined
    
    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

llist.prepend(2)
llist.prepend(1)

Output:

1 -> 2 -> 3 -> 5 -> 7

The prepend method adds a new node with the given data at the start of the list, adjusting the head of the list to point to the new node, making it the first element.

Method 3: Inserting Elements at a Specific Position

Inserting an element at a specific position involves traversing the list to the desired point and adjusting the pointers to include the new node. This method gives you control over where exactly in the list the new element should appear.

Here’s an example:

class LinkedList:
    # Assuming Node class and __init__ method are already defined
    
    def insert_after_node(self, prev_node, data):
        if not prev_node:
            print("Previous node is not in the list")
            return
        new_node = Node(data)
        new_node.next = prev_node.next
        prev_node.next = new_node

# Assuming we have a method to get the reference of a node by its data
prev_node = llist.get_node(3)
llist.insert_after_node(prev_node, 4)

Output:

1 -> 2 -> 3 -> 4 -> 5 -> 7

The insert_after_node method allows inserting a new node after the node referenced by prev_node. It’s important to check if the prev_node actually exists in the list.

Method 4: Inserting Elements at a Specific Index

Instead of working with node references, you might want to insert an element by specifying an index. This requires traversing the list just until the desired index.

Here’s an example:

class LinkedList:
    # Assuming Node class and __init__ method are already defined
    
    def insert_at_index(self, index, data):
        if index == 0:
            self.prepend(data)
            return
        new_node = Node(data)
        current = self.head
        count = 0
        while current and count < index - 1:
            count += 1
            current = current.next
        if not current:
            raise IndexError("Index out of range")
        new_node.next = current.next
        current.next = new_node

llist.insert_at_index(2, 6)

Output:

1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 7

This insert_at_index method allows you to insert a node at a specific list index. We account for potential index errors, preventing attempts to insert beyond the end of the list.

Bonus One-Liner Method 5: Using List Comprehension for LinkedList Initialization

This one-liner technique can be used for quickly initializing a linked list with multiple elements. It’s concise, but not suitable for all applications due to its limitations in insert positioning.

Here’s an example:

class LinkedList:
    # Assuming Node class and __init__ method are already defined
    
    def __init__(self, elements):
        self.head = None if not elements else Node(elements.pop(0))
        current_node = self.head
        [self.append(element) for element in elements]

llist = LinkedList([1, 2, 3, 4, 5, 6, 7])

No specific output is provided as it depends on what functions you call after initializing the list.

This initialization method makes use of a list comprehension within the constructor to append all elements of a given list while constructing the linked list object.

Summary/Discussion

Method 1: Appending to End. Simple and straightforward. Most suitable when the order of insertion is crucial, and the list is not too long as the operation has O(n) complexity.
Method 2: Prepending to Start. Efficient for quickly adding elements to the beginning of the list with constant time complexity, O(1).
Method 3: Inserting After Node. Provides control over insertion point. Efficiency depends on the position of the previous node but can get to O(n) in the worst case.
Method 4: Inserting at Index. More intuitive when dealing with list indices. Suitable for middle insertions, although it can be as inefficient as O(n) if the index is towards the end.
Bonus Method 5: List Comprehension Initialization. Quick and pythonic, best for initializing a new linked list but not designed for inserting into an existing list.