Linked List

Overview

A singly linked list is a type of data structure that organizes elements into nodes, where each node contains data and a reference (pointer) to the next node in the list. The nodes are linked in a chain-like sequence.

The first node in a singly linked list is called the "head" and it marks the starting point of the list. The last node is known as the "tail" and its reference usually points to a special value (such as null) to indicate the end of the list.

Traversal in a singly linked list typically starts from the head and moves towards the tail, following the next pointers to access sequential nodes. Once the traversal reaches the end(tail), the next pointer will be null, which is the end of the list.

Advantages of singly linked lists include their dynamic size, which allows for easy resizing as elements are added or removed, unlike fixed-size arrays. Additionally, inserting or deleting elements can be efficient, particularly at the beginning or middle of the list, taking constant time with proper pointer adjustments.

However, singly linked lists lack random access, meaning accessing an element at a specific index requires traversing the list from the beginning, taking O(n) time in the worst case. Also, each node uses extra memory overhead to store the next pointer, which can be inefficient for small data types. Additionally, the lack of contiguous memory storage in singly linked lists can lead to cache inefficiencies during traversal.

Overall, singly linked lists are commonly used in scenarios where dynamic sizing and frequent insertions or deletions are required. They serve as fundamental building blocks for more complex data structures like stacks, queues, and linked list-based hash tables.

Code

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
# Create nodes
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
node4 = Node(40)
 
# Link nodes
node1.next = node2
node2.next = node3
node3.next = node4
 
# Print the linked list
current = node1
while current:
    print(current.data, end=" -> ")
    current = current.next
print("None")

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}
 
// Create nodes
const node1 = new Node(10);
const node2 = new Node(20);
const node3 = new Node(30);
const node4 = new Node(40);
 
// Link nodes
node1.next = node2;
node2.next = node3;
node3.next = node4;
 
// Print the linked list
let current = node1;
while (current !== null) {
    process.stdout.write(current.data + " -> ");
    current = current.next;
}
console.log("null");

class Node {
    int data;
    Node next;
 
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
 
public class Main {
    public static void main(String[] args) {
        // Create nodes
        Node node1 = new Node(10);
        Node node2 = new Node(20);
        Node node3 = new Node(30);
        Node node4 = new Node(40);
 
        // Link nodes
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
 
        // Print the linked list
        Node current = node1;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node* next;
};
 
int main() {
    // Create nodes
    struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* node4 = (struct Node*)malloc(sizeof(struct Node));
 
    node1->data = 10;
    node1->next = node2;
    node2->data = 20;
    node2->next = node3;
    node3->data = 30;
    node3->next = node4;
    node4->data = 40;
    node4->next = NULL;
 
    // Print the linked list
    struct Node* current = node1;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
 
    return 0;
}

<?php
class Node {
    public $data;
    public $next;
 
    function __construct($data) {
        $this->data = $data;
        $this->next = null;
    }
}
 
// Create nodes
$node1 = new Node(10);
$node2 = new Node(20);
$node3 = new Node(30);
$node4 = new Node(40);
 
// Link nodes
$node1->next = $node2;
$node2->next = $node3;
$node3->next = $node4;
 
// Print the linked list
$current = $node1;
while ($current != null) {
    echo $current->data . " -> ";
    $current = $current->next;
}
echo "null\n";
?>

We always try to improve this course so if you spot errors, inconsistencies or other issues, contact us.

Queue Doubly Linked List