Imagine you have a box of treasures, each treasure carefully linked to the next with a magical thread. This magical thread allows you to move from one treasure to the next without knowing the exact location of each treasure. This is similar to how a linked list works in programming.

In the world of coding, a linked list is a fundamental data structure where each element, called a node, contains both data and a reference (or link) to the next node in the sequence. This link is what sets linked lists apart from other data structures like arrays, where elements are stored in contiguous memory locations.

Let’s dive deeper into this concept using a simple story:

Once upon a time, in a small village, there was a library with many books. The librarian wanted to organize the books in a way that made it easy for villagers to find them. Instead of placing all the books on one shelf (like an array), the librarian decided to create a linked list of books.

Each book was a node in the linked list, containing its title and a reference to the next book. This way, the librarian could add new books to the list or remove books without having to rearrange the entire library.

One day, a young reader came to the library looking for a specific book. The librarian, using the linked list, started at the first book and followed the references until the desired book was found. The young reader was amazed at how quickly the book was located!

In real-life coding, linked lists are used in various scenarios. For example:

1. Dynamic Memory Allocation: Linked lists allow for efficient memory allocation and deallocation, as nodes can be easily added or removed.
2. Implementing Stacks and Queues: Linked lists are used to implement stack and queue data structures, where elements are added or removed from one end.
3. Music Playlist: Imagine a music playlist where each song is a node in a linked list, with links to the next and previous songs. You can easily add, remove, or shuffle songs using this structure.

Now let us dive into coding for each like Python, c++,c, and Java how to write code for Linkedlist

LinkedList in Python(Single Linked List)

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 self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" ")
            current_node = current_node.next
        print()

# Example usage
if __name__ == "__main__":
    ll = LinkedList()
    ll.append(1)
    ll.append(2)
    ll.append(3)
    ll.print_list()

Output: 1 2 3

Explanation of the Above Code:

1. Node Class: This class represents a single node in a linked list.
   • __init__(self, data): This is the constructor method for the Node class. It initializes a new node with the given data value and sets the next attribute to None. Each node contains some data and a reference to the next node in the linked list.
2. LinkedList Class: This class represents the linked list itself.
   • __init__(self): This is the constructor method for the LinkedList class. It initializes an empty linked list with a head attribute set to None, indicating that the list is initially empty.
   • append(self, data): This method adds a new node with the given data to the end of the linked list.
     • It creates a new node using the Node class and the provided data.
     • If the linked list is empty (i.e., self.head is None), it sets the new node as the head of the linked list and returns.
     • Otherwise, it iterates through the linked list to find the last node (last_node) and sets the next attribute of the last node to the new node.
   • print_list(self): This method prints the data of each node in the linked list.
     • It starts at the head of the linked list (current_node = self.head) and iterates through each node (while current_node:).
     • For each node, it prints the node’s data (print(current_node.data, end=" ")) and moves to the next node (current_node = current_node.next).
     • Once it reaches the end of the linked list (i.e., current_node becomes None), it prints a newline to move to the next line (print()).
3. Example Usage: This part of the code demonstrates how to create a linked list instance (ll), append three nodes with data values 1, 2, and 3 to the linked list, and then print the contents of the linked list using the print_list method.
   • if __name__ == "__main__": is a Python idiom that checks if the script is being run directly (as opposed to being imported as a module). If the script is being run directly, it creates a new instance of the LinkedList class (ll), appends three nodes to the linked list with data values 1, 2, and 3, and then prints the contents of the linked list using the print_list method.

Multi Linked List :

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.child = None

class MultiLevelLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def append_child(self, parent_data, child_data):
        parent_node = self.find_node(parent_data)
        if parent_node is None:
            print(f"Parent node with data {parent_data} not found")
            return
        new_child = Node(child_data)
        parent_node.child = new_child

    def find_node(self, data):
        current_node = self.head
        while current_node:
            if current_node.data == data:
                return current_node
            current_node = current_node.next
        return None

    def print_list(self):
        current_node = self.head
        while current_node:
            print(f"{current_node.data}", end=" -> ")
            if current_node.child:
                print(f"{current_node.child.data}", end=" -> ")
            current_node = current_node.next
        print("None")

# Example Usage
if __name__ == "__main__":
    ml_ll = MultiLevelLinkedList()
    ml_ll.append(1)
    ml_ll.append(2)
    ml_ll.append(3)
    ml_ll.append(4)
    ml_ll.append(5)
    ml_ll.append_child(2, 6)
    ml_ll.append_child(4, 7)
    ml_ll.print_list()

Output:

Explanation:

1. class Node:: This defines a class named Node, which represents each element in the linked list. Each node has a data attribute to store the value and next and child attributes to point to the next node in the same level and the first node in the child level, respectively.
2. def __init__(self, data):: This is the constructor method for the Node class. It initializes a node with the given data value and sets next and child to None.
3. class MultiLevelLinkedList:: This defines a class named MultiLevelLinkedList, which represents the multi-level linked list. It has a head attribute to point to the first node in the top-level.
4. def __init__(self):: This is the constructor method for the MultiLevelLinkedList class. It initializes an empty linked list with head set to None.
5. def append(self, data):: This method appends a new node with the given data at the end of the top-level linked list.
6. def append_child(self, parent_data, child_data):: This method appends a new node with the child_data value as a child of the node with the parent_data value.
7. def find_node(self, data):: This method finds and returns the node with the given data value in the linked list. If the node is not found, it returns None.
8. def print_list(self):: This method prints the elements of the linked list. It iterates through the linked list, printing each node’s data value and, if it has a child, the child node’s data value.
9. if __name__ == "__main__":: This is a Python idiom that allows the code to be executed only if the script is run directly, not when it is imported as a module.
10. ml_ll = MultiLevelLinkedList(): This creates an instance of the MultiLevelLinkedList class named ml_ll.
11. ml_ll.append(1), ml_ll.append(2), etc.: These lines append nodes with the given data values to the top-level linked list.
12. ml_ll.append_child(2, 6), ml_ll.append_child(4, 7): These lines append child nodes to the nodes with data values 2 and 4, respectively.
13. ml_ll.print_list(): This prints the elements of the multi-level linked list. Each node is printed with its value, followed by an arrow (->), and if it has a child, the child’s value is also printed.

Java Single & Multi Linkedlist:

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    public LinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.append(1);
        list.append(2);
        list.append(3);
        list.printList();
    }
}

Multi Linkedlist Java

class Node {
    int data;
    Node next;
    Node child;

    public Node(int data) {
        this.data = data;
        this.next = null;
        this.child = null;
    }
}

class MultiLevelLinkedList {
    Node head;

    public MultiLevelLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    public void appendChild(int parentData, int childData) {
        Node parentNode = findNode(parentData);
        if (parentNode == null) {
            return;
        }
        Node childNode = new Node(childData);
        if (parentNode.child == null) {
            parentNode.child = childNode;
            return;
        }
        Node current = parentNode.child;
        while (current.next != null) {
            current = current.next;
        }
        current.next = childNode;
    }

    public Node findNode(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) {
                return current;
            }
            current = current.next;
        }
        return null;
    }

    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            Node child = current.child;
            while (child != null) {
                System.out.print(child.data + " ");
                child = child.next;
            }
            current = current.next;
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MultiLevelLinkedList list = new MultiLevelLinkedList();
        list.append(1);
        list.append(2);
        list.append(3);
        list.appendChild(2, 6);
        list.appendChild(2, 7);
        list.appendChild(3, 8);
        list.printList();
    }
}

In conclusion, a linked list is a fundamental data structure used in programming for organizing and managing data. It consists of nodes, where each node contains a data value and a reference (or pointer) to the next node in the sequence. Linked lists offer advantages such as dynamic size, efficient insertion and deletion operations, and flexibility in memory allocation.

The provided source code examples in Python and Java demonstrate the implementation of a single linked list, which connects nodes sequentially, and a multiple linked list, which allows nodes to have child nodes, creating a hierarchical structure. Understanding linked lists is crucial for developing a strong foundation in data structures and algorithms, as they are commonly used in various applications for managing and manipulating data efficiently.