insertion in linked list
There are several common scenarios that can occur when inserting a node into a linked list. Here are three frequently encountered situations:
- Inserting a node at the beginning of the list: This involves adding a new node to the front of the linked list, making the newly inserted node the new head of the list.
- Inserting a node after a specific node in the list: This scenario involves inserting a new node immediately after a given node in the linked list, adjusting the next pointers accordingly.
- Inserting a node at the end of the list: This situation occurs when adding a new node at the tail or the last position of the linked list, updating the next pointer of the current last node to point to the newly inserted node.
Node struct in C++ for a linked list:
struct Node
{
int data;
struct Node* next;
};Node class in Java for a linked list:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}Insert a node at the beginning:
To insert a node at the beginning of a linked list, follow these steps:
- Allocate memory for the new node.
- Store the desired data in the new node.
- Set the next pointer of the new node to point to the current head of the list.
- Update the head pointer to point to the newly created node, making it the new head of the list.
For example, consider a given linked list with elements 17->25->40->45. If we add item 12 at the front, the updated linked list will be 12->17->25->40->45.
Example of how to insert a node at the beginning of a linked list in Java:
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 insertAtBeginning(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; } else { newNode.next = head; head = newNode; } } public void display() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } } public class Main { public static void main(String[] args) { LinkedList list = new LinkedList(); // Inserting nodes at the beginning list.insertAtBeginning(1); list.insertAtBeginning(2); list.insertAtBeginning(3); list.insertAtBeginning(4); // Displaying the linked list list.display(); } }
In this example, we have a Node class representing each node in the linked list. The LinkedList class serves as a container for the nodes and provides methods for manipulating the list.
The insertAtBeginning method inserts a new node at the beginning of the linked list. It first creates a new node with the provided data value. If the list is empty (head is null), the new node becomes the head of the list. Otherwise, the new node's next reference is set to the current head, and the head is updated to point to the new node.
The display method is used to print the data values of all the nodes in the list by traversing the list from the head to the last node.
In the main method, we create an instance of the LinkedList class. Nodes with values 4, 3, 2 and 1 are inserted at the beginning of the list using the insertAtBeginning method. Finally, the contents of the linked list are displayed using the display method.
The output of this program will be:
4 3 2 1
This indicates that the linked list contains three nodes with values 25, 17, and 12, respectively, in reverse order of insertion. The newly inserted nodes are placed at the beginning of the list.
The time complexity of inserting a node at the start of the List is O(1).
Example of how to insert a node at the beginning of a linked list in C++:
#include <iostream> struct Node { int data; Node* next; Node(int data) { this->data = data; this->next = nullptr; } }; class LinkedList { private: Node* head; public: LinkedList() { this->head = nullptr; } void insertAtBeginning(int data) { Node* newNode = new Node(data); if (head == nullptr) { head = newNode; } else { newNode->next = head; head = newNode; } } void display() { Node* current = head; while (current != nullptr) { std::cout << current->data << " "; current = current->next; } std::cout << std::endl; } }; int main() { LinkedList list; // Inserting nodes at the beginning list.insertAtBeginning(1); list.insertAtBeginning(2); list.insertAtBeginning(3); list.insertAtBeginning(4); // Displaying the linked list list.display(); return 0; }
Inserting a Node at the End:
To insert a node at the end of a linked list, you can follow these steps:
- Allocate memory for the new node: This involves reserving memory space for the new node that will be inserted at the end of the linked list.
- Store data: Assign the desired data value to the newly created node.
- Traverse to the last node: Begin traversing the linked list starting from the head node and move to the next node until reaching the last node.
- Change the next pointer of the last node to point to the recently created node: Once the last node is reached, update its next pointer to point to the newly created node, effectively inserting it at the end of the linked list.
example of how to insert a node at the end of a linked list in Java:
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 insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
// Inserting nodes at the end
list.insertAtEnd(1);
list.insertAtEnd(2);
list.insertAtEnd(3);
list.insertAtEnd(4);
// Displaying the linked list
list.display();
}
In this example, we have a Node class representing each node in the linked list. The LinkedList class serves as a container for the nodes and provides methods for manipulating the list.
The insertAtEnd method inserts a new node at the end of the linked list. It first creates a new node with the provided data value. If the list is empty (head is null), the new node becomes the head of the list. Otherwise, it traverses the list starting from the head until the last node is reached. Then, it updates the next pointer of the last node to point to the newly created node.
The display method is used to print the data values of all the nodes in the list by traversing the list from the head to the last node.
In the main method, we create an instance of the LinkedList class. Nodes with values 1, 2, 3 and 4 are inserted at the end of the list using the insertAtEnd method. Finally, the contents of the linked list are displayed using the display method.
The output of this program will be:
1 2 3 4
This indicates that the linked list contains three nodes with values 1, 2, 3 and 4, respectively, in the order of insertion. The newly inserted nodes are placed at the end of the list.
The time complexity of this operation is O(N) where N is the number of nodes in the Linked List as one has to traverse the complete list in order to find the last node.
example of how to insert a node at the end of a linked list in C++:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() {
this->head = nullptr;
}
void insertAtEnd(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
void display() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
LinkedList list;
// Inserting nodes at the end
list.insertAtEnd(1);
list.insertAtEnd(2);
list.insertAtEnd(3);
list.insertAtEnd(4);
// Displaying the linked list
list.display();
return 0;
}
inserting a node after a given node:
To insert a node after a given node in a linked list, you can follow these steps:
- Allocate memory for the new node: This involves reserving memory space for the new node that will be inserted after the given node.
- Change the next pointer of the newly created node: Set the next pointer of the newly created node to point to the node that comes after the given node.
- Change the next pointer of the given node: Update the next pointer of the given node to point to the newly created node.
By performing these steps, the new node will be inserted after the given node in the linked list.
example of how to insert a node after a given node in a linked list in Java:
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 insertAfter(Node prevNode, int data) { if (prevNode == null) { System.out.println("Previous node cannot be null."); return; } Node newNode = new Node(data); newNode.next = prevNode.next; prevNode.next = newNode; } public void display() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } } public class Main { public static void main(String[] args) { LinkedList list = new LinkedList(); // Creating nodes Node node1 = new Node(4); Node node2 = new Node(3); Node node3 = new Node(2); Node node4 = new Node(1); Node node5 = new Node(0); // Constructing the linked list: 4 -> 3 -> 2 -> 1 -> 0 list.head = node1; node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; // Inserting a node with data 5 after the node with data 3 Node prevNode = node2; list.insertAfter(prevNode, 5); // Displaying the linked list: 4 -> 3 -> 5 -> 2 -> 1 -> 0 list.display(); } }
In this modified code, we first create nodes with values 4, 3, 2, 1, and 0. Then, we link these nodes together to form the linked list. After that, we insert a new node with a value of 5 after the node with a value of 3 using the insertAfter method.
The resulting linked list will be: 4 -> 3 -> 5 -> 2 -> 1 -> 0
4 3 5 2 1 0
The time complexity of inserting a node at start of the List is O(1).
example of how to insert a node after a given node in a linked list in C++:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() {
this->head = nullptr;
}
void insertAfter(Node* prevNode, int data) {
if (prevNode == nullptr) {
std::cout << "Previous node cannot be null." << std::endl;
return;
}
Node* newNode = new Node(data);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
void display() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
LinkedList list;
// Creating nodes
Node* node1 = new Node(4);
Node* node2 = new Node(3);
Node* node3 = new Node(2);
Node* node4 = new Node(1);
Node* node5 = new Node(0);
// Constructing the linked list: 4 -> 3 -> 2 -> 1 -> 0
list.head = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
// Inserting a node with data 5 after the node with data 3
Node* prevNode = node2;
list.insertAfter(prevNode, 5);
// Displaying the linked list: 4 -> 3 -> 5 -> 2 -> 1 -> 0
list.display();
return 0;
}
No comments