LinkList Introduction

Linked List Overview

Memory space is a shared resource for all programs. In a complex system environment, free memory space may be scattered throughout memory. We know that the memory space for storing arrays must be contiguous. However, when the array is very large, it might not be possible to provide such a large contiguous space in memory. This is where the flexibility of linked lists becomes apparent.

A linked list is a linear data structure where each element is a node object, and the nodes are connected via "references." A reference stores the memory address of the next node, allowing access to the next node from the current one.

The design of linked lists allows the nodes to be dispersed throughout memory without needing contiguous memory addresses.

The first node of a linked list is known as the "head node," and the last node is called the "tail node." The tail node points to "null," represented as null in Java, nullptr in C++, and None in Python. In languages like C, C++, Go, and Rust that support pointers, the above "references" are replaced with "pointers."

1. Initializing a Linked List

To build a linked list, we first initialize the node objects and then establish the references between nodes. Once initialized, we can traverse all nodes starting from the head node via the next references.

Inserting a node in a linked list is easy. As shown in the diagram, to insert a new node P between two adjacent nodes n0 and n1, we only need to change two references (pointers), with a time complexity of O(1).

2. Inserting a Node

Compared to arrays, where the time complexity of inserting an element is O(n), linked lists are more efficient with large data. Inserting a node in a linked list is convenient; only a single reference (pointer) needs to be changed.

3. Deleting a Node

Note that even after the deletion operation is complete and node P still points to n1, it is effectively no longer part of the linked list as it can't be accessed during traversal.

4. Accessing a Node

Accessing a node in a linked list is less efficient. As mentioned earlier, we can access any element in an array in O(1) time. However, for linked lists, the program needs to start from the head node and traverse sequentially to find the target node. That is, accessing the i-th node in a linked list requires i iterations, making the time complexity O(n).

5. Finding a Node

Traverse the linked list to find the node with a value equal to target and return its index in the list. This process is also a linear search.

# Initializing the linked list: 1 -> 3 -> 2 -> 5 -> 4
# Initializing nodes
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
# Establishing references between nodes
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4


def insert(n0: ListNode, P: ListNode):
    """Insert node P after node n0 in the linked list"""
    n1 = n0.next
    P.next = n1
    n0.next = P

def remove(n0: ListNode):
    """Delete the first node after node n0 in the linked list"""
    if not n0.next:
        return
    # n0 -> P -> n1
    P = n0.next
    n1 = P.next
    n0.next = n1

def access(head: ListNode, index: int) -> ListNode | None:
    """Access the node at index in the linked list"""
    for _ in range(index):
        if not head:
            return None
        head = head.next
    return head

def find(head: ListNode, target: int) -> int:
    """Find the first node with value `target` in the linked list"""
    index = 0
    while head:
        if head.val == target:
            return index
        head = head.next
        index += 1
    return -1