Understanding Linked Lists: Types and Code Examples

In this guide, we delve into the fundamentals of linked lists, a type of linear data structure. Unlike arrays, linked lists do not allocate memory contiguously. Instead, each node secures its memory space independently, which is then connected through references to create the structure of the linked list.

One of the main advantages of linked lists is the efficiency of adding and removing elements at the start of the list, achievable in constant time or O(1). This efficiency is due to the capability to adjust references directly, eliminating the need to reposition elements as is necessary with arrays. Furthermore, linked lists are versatile, able to store data of any type supported by the programming language in use.

In this tutorial, you will learn:

1. An Introduction to Linked Lists
2. Various Types of Linked Lists
3. A Summary of Operations with Their Time and Space Complexities Presented in a Table
4. The Distinctions Between Arrays and Linked Lists
5. Algorithm Implementation: Removing Duplicates from a Sorted List in PHP and JavaScript

Let’s explore these aspects to gain a comprehensive understanding of linked lists and their application.

Understanding Linked list

The “head” refers to the initial node in the list, while the “tail” identifies the final node.

To retrieve the value from the first node:

• head.data yields 6.

For the second node’s value, we navigate via the “next” reference:

• head.next moves the focus to the subsequent node in the sequence.
• head.next.data provides the value 4.

To access the third node’s value, we continue following the “next” references:

• head.next.next advances the focus to the node after the next, effectively reaching the third node.
• head.next.next.data reveals the value 5.

This approach demonstrates how linked lists enable sequential access to their elements by traversing through their “next” references.

What is a node ?

A linked list node exemplifies self-referential structures in programming. It consists of nodes, each holding data and a reference (commonly known as a ‘pointer’) to another node of the same kind. These pointers enable the nodes to form a chain, creating the linked list’s structure.

The self-referential design of the nodes supports effective navigation and modification of the list’s contents. Linked lists can be constructed using either classes or structured arrays, depending on the programming language and the specific requirements of the application.

How to Implement a Linked List Using classes

Here’s a revised version of your code that defines a Node class, creates nodes, links them to form a linked list, and traverses the list:

class ListNode {
    public function __construct(
        public $value,
        public ?ListNode $nextNode = null
    ) {}
}

// Instantiation of nodes

$firstNode = new ListNode(10);
$secondNode = new ListNode(20);
$thirdNode = new ListNode(30);

// Connecting nodes to form the list

$firstNode->nextNode = $secondNode;
$secondNode->nextNode = $thirdNode;

// Iterating through the linked list

$currentNode = $firstNode;
while ($currentNode !== null) {
    echo $currentNode->value . " ";
    $currentNode = $currentNode->nextNode;
}

How to Implement a Linked List Using Using arrays

Here’s an alternative version of your code, which uses associative arrays to represent nodes in a linked list, links these nodes, and then iterates through the list:

// Initializing nodes as associative arrays

$firstNode = ['value' => 10, 'next' => null];
$secondNode = ['value' => 20, 'next' => null];
$thirdNode = ['value' => 30, 'next' => null];

// Connecting nodes

$firstNode['next'] = &$secondNode;
$secondNode['next'] = &$thirdNode;

// Iterating over the linked list

$currentNode = $firstNode;
while ($currentNode !== null) {
    echo $currentNode['value'] . " ";
    $currentNode = &$currentNode['next'];
}

This version follows the same structure as your original script, with slight adjustments to the naming for clarity, demonstrating how to create, link, and traverse a linked list using associative arrays in PHP.

In both approaches, we construct a system where each unit, referred to as a node, holds a piece of data and a reference (termed “next”) to another node of identical structure, creating a self-referential setup. These nodes are then interconnected to craft a data structure known as a linked list. The process culminates with the traversal of this structure to engage with and adjust its components.

Contrary to arrays, which permit direct access to any element based on its index in constant time, a linked list lacks this capability. To locate the nth element, one must sequentially navigate through the list, moving from node to node, until the desired position is reached.

Traversing a linked list involves moving from the initial node and proceeding through each subsequent node until the concluding node is encountered.

Types of Linked list

We’ll discuss the types under the Traversal, Memory and Complexity categories.

A Singly Linked List is a basic but foundational data structure that consists of a series of elements, called nodes, linked together in a sequence. Here’s a breakdown of its structure and characteristics:

Structure

• Node: Each node in a singly linked list contains two components:
• Data: The information or value stored in the node.
• Next Pointer: A reference to the next node in the sequence. This is what links the nodes together.
• Head: The first node in the list is known as the head. It is the entry point to the list and used as the starting point for any traversal or operation.
• Tail: The last node in the list, which does not point to any next node (its next pointer is null), marking the end of the list.

Characteristics

• Linear Structure: The nodes are connected in a linear sequence. Each node (except the last one) points to the next node, creating a chain-like structure.
• Dynamic Size: Unlike arrays, a singly linked list does not have a fixed size. It can grow or shrink dynamically as nodes are added or removed.
• Sequential Access: Elements in a singly linked list can only be accessed sequentially, starting from the head and following the next pointers until the desired node is reached.
• Efficiency: Operations like insertion and deletion at the beginning of the list are very efficient, taking constant time ((O(1))). However, accessing or deleting a node by value or position (especially towards the end of the list) can be less efficient, as it may require traversing a significant part of the list ((O(n)) for a list of (n) elements).

Operations

Common operations performed on singly linked lists include:

• Traversal: Walking through each node of the list, typically starting from the head, to perform operations like printing out values or calculating the sum of all elements.
• Insertion: Adding a new node to the list, which can be done at the beginning (push front), at the end (append), or after/before a given node.
• Deletion: Removing a node from the list, which could be based on a specific value, its position, or directly deleting the head or tail node.
• Search: Looking for a node with a specific value, starting from the head and moving through each node sequentially.

Implementation

In most programming languages, a singly linked list is implemented using a class for the nodes that contains the data and the next pointer. The list itself can be managed by a separate class or simply by controlling the head of the list through various functions or methods.

Understanding and implementing singly linked lists is a fundamental skill in computer science, as they form the basis for more complex structures and algorithms.

Non-code explanation

Envision embarking on a rail journey, where each train and its route symbolize a part of your adventure, and every station marks a decision point for changing your course.

• Train A marks the outset of your voyage, transporting you from Station A to Station B. Upon arrival at Station B, a directive guides you to board another train to proceed.
• Train B carries you from Station B to Station C, the subsequent leg of your journey. Reaching Station C signifies the conclusion of your travel, as no further instructions are provided for onward movement.

This scenario parallels the structure of a singly linked list in the following manner:

• The Train Segments (Train A, Train B, Train C) symbolize the list’s nodes, each segment representing a distinct node.
• The Role of Each Train mirrors the data housed within each node, encapsulating a portion of your journey.
• Switching Trains at the Stations reflects the “next” pointer in a linked list, pointing to the succeeding segment of your expedition.
• The Final Stop (Station C) indicates the end of the list, where no subsequent pointers or directions are necessary, marking the journey’s conclusion.

In essence, a singly linked list can be likened to a series of train rides that sequentially carry you from one point to another until you reach your endpoint. The transitions from one train to the next serve as pointers, seamlessly guiding you through your journey.

Performance Characteristics of a Singly Linked List:

• Traversal Dynamics: Navigation through the list is unidirectional, allowing forward progression only. Unlike a round-trip ticket, there’s no straightforward way to backtrack.
• Memory Considerations: This structure is typically more memory-friendly, as it necessitates just a single reference for each node to point to the next.
• Operational Simplicity: The process of adding or removing elements is relatively straightforward, requiring adjustments to pointers in only one direction.

Time and Space Complexity Overview

Let’s delve into the efficiency of various operations within a linked list, considering both time and space complexities, based on the concepts of constant and linear time complexities:

Traversing the List

• Time Complexity: (O(n)), where (n) represents the total number of nodes in the list. This is because each node must be visited to complete the traversal.
• Space Complexity: (O(1)), as traversal doesn’t require extra space that scales with the size of the input.

Adding an Element at the Start

• Time Complexity: (O(1)), since this action merely requires adjusting the head reference.
• Space Complexity: (O(1)), as no additional space scaling with the list size is needed.

Adding an Element at the End

• Time Complexity: (O(n)), necessitating a walk through the entire list to find the last element.
• Space Complexity: (O(1)), because the operation does not increase space usage in proportion to the list’s length.

Removing an Element from the Start

• Time Complexity: (O(1)), involving simple updates to the head reference.
• Space Complexity: (O(1)), remaining constant regardless of the list size.

Removing an Element from the End

• Time Complexity: (O(n)), as it may involve traversing to the end of the list.
• Space Complexity: (O(1)), constant, without additional space needed based on list size.

These insights highlight the nuanced balance between time and space efficiency across different linked list operations, emphasizing the context-specific advantages of this data structure.

Doubly Linked List

A Doubly Linked List is an advanced form of the linked list data structure where each node contains three components: data, a pointer to the next node, and a pointer to the previous node. This two-way linkage allows traversal of the list in both forward and backward directions, providing greater flexibility and efficiency in certain operations compared to singly linked lists.

Structure

• Node: In a doubly linked list, every node consists of:
• Data: The actual value or information that the node stores.
• Next Pointer: A reference to the next node in the sequence, similar to singly linked lists.
• Previous Pointer: A reference to the preceding node, which is what distinguishes it from singly linked lists and enables backward traversal.
• Head: The first node in the list, from which the forward traversal begins. The previous pointer of the head node is typically null, indicating the start of the list.
• Tail: The last node in the list, from which backward traversal can begin. The next pointer of the tail node is null, marking the end of the list.

Characteristics

• Bidirectional Traversal: Thanks to the previous pointers, nodes can be accessed in both directions, offering more direct paths to certain elements and facilitating operations like reverse traversal.
• Dynamic Size: Like singly linked lists, the size of a doubly linked list is not fixed and can grow or shrink as nodes are added or removed.
• Direct Element Access: While direct access (like array indexing) is not provided, the ability to traverse from both ends can make reaching certain elements faster, especially in large lists.

Operations

Operations in a doubly linked list include:

• Traversal: Moving through the list can be done in both directions, enhancing flexibility for certain algorithms.
• Insertion: Adding nodes can be more efficient because you don’t always need to traverse from the head; nodes can be inserted from either direction, depending on the closest access point.
• Deletion: Removing nodes is more straightforward, as a node can update its next and previous pointers without needing to traverse from the head to find its predecessor.
• Search: Searching can potentially be faster, especially if the element is closer to the tail, as backward traversal is possible.

Implementation

Implementing a doubly linked list typically involves defining a Node class with data, next, and previous properties, along with methods for adding, removing, and traversing nodes. The list itself may be managed by a separate class that maintains references to both the head and tail nodes, facilitating efficient operations at both ends of the list.

Doubly linked lists are particularly useful in applications where frequent navigation in both directions is required, such as in certain types of caching mechanisms, navigation systems, and complex data management scenarios.

Doubly Linked Lists: Performance Insights

Doubly linked lists enhance navigation flexibility through their bidirectional traversal capability, allowing movement both forward and backward through the list. This section delves into the performance characteristics of doubly linked lists, examining traversal, memory efficiency, and the complexity of operations, along with specific time and space complexities for common operations.

Traversal Flexibility

Doubly linked lists stand out for their ability to traverse in two directions. This feature not only facilitates forward movement through the list but also allows for reverse iteration, enhancing the ease of navigating the list.

Memory Considerations

Due to each node in a doubly linked list holding two references—one for the next node and one for the previous—more memory is used compared to singly linked lists. This increased memory requirement per node can affect the list’s overall memory footprint, particularly in larger lists.

Operational Complexity

The structure of doubly linked lists introduces added flexibility for insertions and deletions, thanks to the dual references in each node. However, managing two pointers for each node can add to the operational complexity, especially when it comes to ensuring the integrity of the list during these operations.

Time and Space Complexity Analysis

Traversing the List

• Time and Space Complexity: Mirrors that of singly linked lists, with traversal time complexity at (O(n)) and space complexity at (O(1)), regardless of traversal direction.

Adding Elements at the Start

• Time and Space Complexity: Comparable to singly linked lists, with both operations completing in (O(1)) time and requiring minimal space, independent of the list’s size.

Adding Elements at the End

• Time Complexity: Reduced to (O(1)) due to immediate access to the tail node, eliminating the need for full-list traversal.
• Space Complexity: Maintains at (O(1)), not increasing with the size of the input.

Removing Elements from the Start

• Time and Space Complexity: Aligns with singly linked lists, maintaining efficiency with (O(1)) for both metrics.

Removing Elements from the End

• Time Complexity: Improved to (O(1)) as direct access to the tail node allows for quick updates to pointers.
• Space Complexity: Remains constant at (O(1)), unaffected by the list’s length.

Doubly linked lists offer nuanced advantages in terms of traversal and operational flexibility, with certain operations notably more efficient due to direct access to both the beginning and end of the list. However, this comes at the cost of increased memory usage and potential complexity in managing node references.

Circular Linked List

A circular linked list is a variant of the linked list in which the final node links back to the first node, creating a closed loop. This looping feature sets it apart from conventional linked lists, which terminate with a null pointer to signify the end. Instead of ending, the circular linked list’s last node establishes a direct connection to the first node, facilitating an endless traversal cycle. This design eliminates the concept of a terminal null pointer, enabling a seamless and continuous navigation throughout the list, as if the list wraps around in a circle.

Imagine a circular train route where the train moves continuously around a loop, allowing passengers to embark and disembark at various stops. This loop symbolizes a circular linked list, with each stop representing a node. In this scenario, the train’s endless circuit around the loop mirrors the circular linked list’s structure, where data (passengers) can be added or removed at any point (node), without ever encountering an endpoint.

Like the circular train route, a circular linked list ensures that navigation can proceed indefinitely, circling back to the beginning without interruption. This structure is beneficial for certain scenarios but necessitates careful management of links and memory to preserve the circular integrity and avoid complications such as endless cycles.

Performance Insights for Circular Linked Lists

Traversal Dynamics

• Circular linked lists support a continuous loop for traversal, enabling smooth transition from one node to the next. This looped structure allows for efficient navigation, as there’s no need to return to the start when the end is reached, potentially enhancing traversal performance.

Memory Utilization

• Singly circular linked lists maintain similar memory efficiency as their singly linked counterparts, with each node requiring just one pointer to connect to the subsequent node. This efficient pointer usage can offer advantages in memory management, especially for larger lists.

Operational Complexity

• Operations like insertion and deletion in singly circular linked lists involve adjusting links to preserve the circular format, which can introduce a level of complexity over linear linked lists.

Time and Space Complexity Overview

Traversal

• Time Complexity: (O(n)) – To complete a full loop, traversal may involve passing through each node.
• Space Complexity: (O(1)) – Traversal requires a minimal, fixed amount of additional space.

Insertion at the Start

• Time Complexity: (O(1)) – Adding a new node at the beginning is a quick process, involving only a modification of the head reference.
• Space Complexity: (O(1)) – This operation does not necessitate extra space.

Insertion at the End

• Time Complexity: (O(n)) – Inserting at the end may necessitate a full loop to identify the correct insertion point.
• Space Complexity: (O(1)) – Requires no additional space.

Deletion from the Start

• Time Complexity: (O(1)) – Removing the first node involves straightforward reference updates.
• Space Complexity: (O(1)) – This operation uses a constant amount of space.

Deletion from the End

• Time Complexity: (O(n)) – To remove the last node, potentially the entire list must be traversed.
• Space Complexity: (O(1)) – Like other operations, this one also maintains a constant space requirement.

Summary of Operations for the Time Complexity

Here’s the information presented in a table format for clear comparison of time complexities across different operations in Singly Linked Lists, Doubly Linked Lists, and Circular Linked Lists:

Operation	Singly Linked List	Doubly Linked List	Circular Linked List
Traversal	O(n)	O(n)	O(n)
Insertion at Beginning	O(1)	O(1)	O(1)
Insertion at End	O(n)	O(1)	O(n)
Deletion at Beginning	O(1)	O(1)	O(1)
Deletion at End	O(n)	O(1)	O(n)

Summary of Operations for the Space Complexity

Operation	Singly Linked List	Doubly Linked List	Circular Linked List
Traversal	O(1)	O(1)	O(1)
Insertion at Beginning	O(1)	O(1)	O(1)
Insertion at End	O(1)	O(1)	O(1)
Deletion at Beginning	O(1)	O(1)	O(1)
Deletion at End	O(1)	O(1)	O(1)

This table provides a uniform view of time complexities as O(1) across all operations and list types. However, it’s important to note that, in practice, traversal, insertion at the end, and deletion at the end in singly and circularly linked lists typically have time complexities greater than O(1), often O(n), because they may require traversing the list to locate the relevant node or tail. The table above does not reflect the conventional complexities associated with these operations.

Differences Between Array and Linked list

Arrays and linked lists are fundamental data structures in computer science, each with its unique set of characteristics and use cases. Here’s a comparison of the key differences between arrays and linked lists:

Structure

• Array: A collection of elements stored in contiguous memory locations, accessible by index.
• Linked List: A sequence of elements in which each element is contained in a separate object, called a node, and each node has a reference (pointer) to the next node in the sequence.

Memory Allocation

• Array: Memory is allocated at the time of array declaration in a contiguous block. The size of the array is fixed and needs to be known ahead of time or requires resizing operations to add more elements.
• Linked List: Nodes are dynamically allocated, meaning memory for new elements can be allocated at runtime, and it’s not necessary to determine the size ahead of time.

Access Time

• Array: Offers direct access to elements, allowing for constant-time ((O(1))) access if the index is known.
• Linked List: Elements can only be accessed sequentially, starting from the first node and following the links (pointers) to the desired node, resulting in linear time ((O(n))) access.

Insertion and Deletion

• Array: Inserting or deleting an element requires shifting subsequent elements, which can be costly ((O(n)) time complexity). Adding elements to an array that has reached its capacity requires allocating a new array and copying existing elements to the new array, which is also (O(n)).
• Linked List: Adding or removing nodes is more efficient, especially at the beginning or within the list, as it requires only the adjustment of pointers ((O(1)) time complexity if the node is known and accessible).

Memory Efficiency

• Array: Can waste memory if allocated more than needed or can be insufficient if a fixed size is chosen. However, it has less overhead per stored value.
• Linked List: Each node requires extra memory for a pointer, making it less memory efficient for storing the same number of elements as an array.

Use Cases

• Array: Preferred when you need to frequently access elements by index or when the number of elements is known and fixed.
• Linked List: Ideal for situations where frequent insertion and deletion of elements occur, or when the size of the list is unknown or changes dynamically.

These distinctions highlight the importance of choosing the right data structure based on the specific needs and constraints of your application. Arrays offer simplicity and fast access for indexed data, while linked lists provide flexibility for dynamic data where the size might change over time.

How to Solve the Remove Duplicates from Sorted List Problem

The challenge is to eliminate all duplicate elements from a sorted linked list, ensuring that each value appears precisely once. The goal is to modify the original linked list by removing duplicates, and then return it, maintaining the sorted order. This task involves traversing the list, comparing each node with its successor, and removing any nodes that contain duplicate values, thus ensuring each element in the resulting list is unique.

Solution in PHP

Node Definition

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

This ListNode class establishes the blueprint for each element in the linked list. It contains a value ($val) and a pointer to the next node ($next).

Removing Duplicates

class Solution {
    /**
     * Removes duplicate values from a sorted linked list.
     * @param ListNode $head The head node of the linked list.
     * @return ListNode The head of the modified list without duplicates.
     */
    function deleteDuplicates($head) {
        // Start with the first node.
        $current = $head;

        // Continue as long as there are nodes to process.
        while ($current !== null && $current->next !== null) {
            // Compare current node with the next node.
            if ($current->val == $current->next->val) {
                // Skip the next node if it's a duplicate.
                $current->next = $current->next->next;
            } else {
                // Move to the next node if it's not a duplicate.
                $current = $current->next;
            }
        }

        // Return the head of the modified list.
        return $head;
    }
}

How It Works

• The Solution class contains a method deleteDuplicates to clean the linked list of any repeating elements, ensuring each value appears only once.
• Starting from the head, it iterates through the list with a while loop that checks if the current node and its successor are not null.
• Within each iteration, it compares the current node’s value with that of the next. If they match, the current node’s next pointer is updated to skip over the next node, effectively removing it from the list.
• If the values do not match, the iteration continues to the next node.
• The process repeats until the end of the list is reached, resulting in a list free of duplicates.

This approach modifies the list in place, maintaining its sorted order while ensuring each value is unique.

Conclusion

Through this discussion, we’ve explored the concept of linked lists, the various forms they can take, and tackled a practical challenge: eliminating duplicates from a sorted linked list.

Continue on your learning journey, and happy coding!