Insert node at beginning of linked list

The given problem is about inserting a new node at the beginning of a singly linked list. A linked list is a data structure where each element, called a node, is composed of data and a reference (or link) to the next node in the sequence. In this case, we are dealing with a singly linked list, where each node points to the next node, but not the previous one.

Problem Statement

We need to design a program that inserts a new node with a given data value at the beginning of the linked list. The goal is to maintain the sequence of nodes while adding the new node to the front.

Solution Idea

To solve this problem, we can follow these steps:

1. Create a class LinkNode to define the structure of a linked list node. Each node should have data and a reference to the next node.

2. Create a class SingleLL to represent the singly linked list. This class should have a reference to the head (the first node) of the list.

3. Implement a method addNode(int data) in the SingleLL class. This method will create a new node with the provided data and insert it at the beginning of the linked list.

4. Implement a method display() in the SingleLL class to print the elements of the linked list in order.

5. In the main method, create an instance of the SingleLL class, add elements to it using the addNode method, and then display the resulting linked list using the display method.

Pseudocode

Here's the pseudocode for the algorithm:

class LinkNode
        data
        next
    
    class SingleLL
        head
    
        SingleLL()
            head = null
    
        addNode(data)
            node = new LinkNode(data)
            node.next = head
            head = node
    
        display()
            temp = head
            while temp != null
                print temp.data
                temp = temp.next
    
    main()
        sll = new SingleLL()
        sll.addNode(8)
        sll.addNode(7)
        ...
        sll.display()

Algorithm Explanation

1. The LinkNode class defines the structure of a linked list node with a data field and a reference to the next node.

2. The SingleLL class represents the singly linked list. It contains a reference to the head of the list.

3. The addNode method creates a new node with the given data and inserts it at the beginning of the list by setting the new node's next reference to the current head and updating the head to point to the new node.

4. The display method iterates through the linked list, starting from the head, and prints the data of each node.

5. In the main method, an instance of SingleLL is created. Nodes with data values 8, 7, 6, ..., 1 are added to the linked list using the addNode method. Finally, the display method is called to print the linked list.

Implementation code

1) Insert node at beginning of linked list in java 2) Insert node at beginning of linked list in c# 3) Insert node at beginning of linked list in Python 4) Insert node at beginning of linked list in ruby 5) Insert node at beginning of linked list in node js 6) Insert node at beginning of linked list in c++ 7) Insert node at beginning of linked list in c 8) Insert node at beginning of linked list in go 9) Insert node at beginning of linked list in scala 10) Insert node at beginning of linked list in swift 11) Insert node at beginning of linked list in kotlin 12) Insert node at beginning of linked list in php 13) Insert node at beginning of linked list in vb.net 14) Insert node at beginning of linked list in typescript

Time Complexity

The time complexity of inserting a node at the beginning of the linked list is O(1) because the operation involves updating only a constant number of references (head and the new node's next reference).