Posted on by Kalkicode

# 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:

data
next

class SingleLL

SingleLL()

display()
while temp != null
print temp.data
temp = temp.next

main()
sll = new SingleLL()
...
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

## 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).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post