linked lists

Linked List Concept:

A linked list is a linear data structure consisting of nodes, where each node contains an element and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists don't require contiguous memory allocation. Instead, each element (node) is independently allocated and connected through pointers.

Terminology:

  • Node: A single unit of data in a linked list, consisting of two parts: the data (or payload) and a reference to the next node.

  • Head: The first node in a linked list.

  • Tail: The last node in a linked list.

  • Pointer/Reference: A reference to the next node in the sequence.

  • Singly Linked List: Each node points to the next node.

  • Doubly Linked List: Each node points to both the next and the previous nodes.

  • Circular Linked List: The last node points back to the first node, creating a circular structure.

Types of Linked Lists:

  1. Singly Linked List: Each node has a data element and a pointer to the next node.

  2. Doubly Linked List: Each node has a data element, a pointer to the next node, and a pointer to the previous node.

  3. Circular Linked List: Similar to a singly linked list, but the last node points back to the first node, forming a closed loop.

Linked List Operations:

  1. Insertion: Adding a new node to the linked list.

    • Insert at the beginning.
    • Insert at the end.
    • Insert after a specific node.

  2. Deletion: Removing a node from the linked list.

    • Delete the first node.
    • Delete the last node.
    • Delete a specific node.

  3. Traversal: Iterating through the linked list to access or process each node's data.

  4. Searching: Finding a node with a specific value.

Advantages of Linked Lists:

  1. Dynamic Size: Linked lists can grow or shrink dynamically, unlike arrays, which have a fixed size.

  2. Memory Management: Nodes are allocated individually, allowing efficient memory utilization.

  3. Insertion and Deletion: Adding or removing elements in linked lists is generally faster than in arrays, especially in the middle.

  4. No Memory Wastage: Linked lists don't suffer from memory wastage due to resizing, as is the case with dynamic arrays.

Disadvantages of Linked Lists:

  1. Memory Overhead: Each node requires additional memory for the pointer, increasing memory usage compared to arrays.

  2. No Random Access: Accessing an element at a specific index takes O(n) time in linked lists, while arrays offer O(1) time complexity.

  3. Traversal Complexity: Traversing a linked list can take longer compared to direct memory access in arrays.

Below is the example of a singly linked list implemented in C, followed by its equivalent implementations in JavaScript and Python.

C Implementation:

1
2#include <stdio.h>
3
4#include <stdlib.h>
5
6
7// Node structure
8
9struct Node {
10    int data;
11    struct Node* next;
12};
13
14
15int main() {
16    // Creating nodes
17    struct Node* first = NULL;
18    struct Node* second = NULL;
19    struct Node* third = NULL;
20
21    first = (struct Node*)malloc(sizeof(struct Node));
22    second = (struct Node*)malloc(sizeof(struct Node));
23    third = (struct Node*)malloc(sizeof(struct Node));
24
25    first->data = 1;
26    first->next = second;
27
28    second->data = 2;
29    second->next = third;
30
31    third->data = 3;
32    third->next = NULL;
33
34    return 0;
35}
36

JavaScript Implementation:

1
2// Node class
3
4class Node {
5    constructor(data) {
6        this.data = data;
7        this.next = null;
8    }
9}
10
11
12// Creating nodes
13
14const first = new Node(1);
15
16const second = new Node(2);
17
18const third = new Node(3);
19
20
21first.next = second;
22
23second.next = third;
24

Python Implementation:

1
2# Node class
3
4class Node:
5    def __init__(self, data):
6        self.data = data
7        self.next = None
8
9# Creating nodes
10
11first = Node(1)
12
13second = Node(2)
14
15third = Node(3)
16
17
18first.next = second
19
20second.next = third
21

In all three implementations, we create nodes and link them together to form a singly linked list. Each node has a data field to store the value and a next field to point to the next node in the list. This arrangement forms the basis of a simple linked list structure.