Introduction to Linked List – Data Structure and Algorithm Tutorials
Linked List is basically chains of nodes where each node contains information such as data and a pointer to the next node in the chain. It is a popular data structure with a wide range of real-world applications. In this article, we will provide a complete introduction of Linked List, which will help you tackle any problem based on Linked List.
What is a Linked List?
Linked List is a linear data structure which looks like a series of nodes, where each node has two parts: data and next pointer. Unlike Arrays, Linked List elements are not stored at a contiguous location. In the linked list there is a head pointer, which points to the first element of the linked list, and if the list is empty then it simply points to null or nothing.
Basic Terminologies of Linked List:
- Head: The Head of a linked list is a pointer to the first node or reference of the first node of linked list. This pointer marks the beginning of the linked list.
- Node: Linked List consists of a series of nodes where each node has two parts: data and next pointer.
- Data: Data is the part of node which stores the information in the linked list.
- Next pointer: Next pointer is the part of the node which points to the next node of the linked list.
Importance of Linked List:
Here are a few advantages of a linked list that is listed below, it will help you understand why it is necessary to know.
- Dynamic Data structure: The size of memory can be allocated or de-allocated at run time based on the operation insertion or deletion.
- Ease of Insertion/Deletion: The insertion and deletion of elements are simpler than arrays since no elements need to be shifted after insertion and deletion, Just the address needed to be updated.
- Efficient Memory Utilization: As we know Linked List is a dynamic data structure the size increases or decreases as per the requirement so this avoids the wastage of memory.
- Implementation: Various advanced data structures can be implemented using a linked list like a stack, queue, graph, hash maps, etc.
There are mainly three types of linked lists:
- Singly linked list
- Doubly linked list
- Circular linked list
Singly Linked List is a type of linked list where each node has two parts: data and next pointer. The data part stores the information and the next pointer points to the next node of the linked list. The next pointer of the last node stores null as it is the last node of the linked list and there is no next node. Traversal of items can be done in the forward direction only due to the linking of every node to its next node.
Node Definition of Singly linked list:
// Singly linked list node
class Node {
public:
int data;
Node* next;
};
// Singly Linked List Class
class LinkedList {
Node head; // head of list
/* Node Class */
class Node {
int data;
Node next;
// Constructor to create a new node
Node(int d)
{
data = d;
next = null;
}
}
}
Operations on Singly Linked List:
The following operations are performed on a Single Linked List
- Insertion: The insertion operation can be performed in three ways. They are as follows…
- Deletion: The deletion operation can be performed in three ways. They are as follows…
- Search: It is a process of determining and retrieving a specific node either from the front, the end or anywhere in the list.
- Display: This process displays the elements of a Single-linked list.
Doubly Linked List is a type of linked list where each node has three parts: data, next pointer and previous pointer. The data part stores the information, the next pointer points to the next node of the linked list and the previous pointer points to the previous node of the linked list. The next pointer of the last node and the previous pointer of the first node stores null. Traversal of items can be done in the forward direction as well as backward direction due to the linking of every node to its next node as well as the previous node.
Node Definition of Doubly Linked List:
/* Node of a doubly linked list */
class Node {
public:
int data;
Node* next; // Pointer to next node in DLL
Node* prev; // Pointer to previous node in DLL
};
// Class for Doubly Linked List
public class DLL {
Node head; // head of list
/* Doubly Linked list Node*/
class Node {
int data;
Node prev;
Node next;
// Constructor to create a new node
// next and prev is by default initialized as null
Node(int d) { data = d; }
}
}
Operations on Doubly Linked List:
In a doubly linked list, we perform the following operations…
- Insertion: The insertion operation can be performed in three ways as follows:
- Deletion: The deletion operation can be performed in three ways as follows…
- Display: This process displays the elements of a double-linked list.
A circular linked list is a type of linked list in which the first and the last nodes are also connected to each other to form a circle, there is no NULL at the end.
Commonly used operations on Circular Linked List:
The following operations are performed on a Circular Linked List
- Insertion: The insertion operation can be performed in three ways:
- Deletion: The deletion operation can be performed in three ways:
- Display: This process displays the elements of a Circular linked list.
Implementation of Linked List:
Below is the implementation of Linked List in different languages:
// C++ program to show inserting a node
// at front of given Linked List
#include <bits/stdc++.h>
using namespace std;
// A linked list node
class Node {
public:
int data;
Node* next;
};
// Given a reference (pointer to pointer)
// to the head of a list and an int, inserts
// a new node on the front of the list.
void insertAtFront(Node** head_ref, int new_data)
{
// 1. allocate node
Node* new_node = new Node();
// 2. put in the data
new_node->data = new_data;
// 3. Make next of new node as head
new_node->next = (*head_ref);
// 4. move the head to point
// to the new node
(*head_ref) = new_node;
}
/* Function to remove the first node
of the linked list */
Node* removeFirstNode(Node* head)
{
if (head == NULL)
return NULL;
// Move the head pointer to the next node
Node* temp = head;
head = head->next;
delete temp;
return head;
}
// This function prints contents of
// linked list starting from head
void printList(Node* node)
{
while (node != NULL) {
cout << " " << node->data;
node = node->next;
}
cout << "\n";
}
// Driver code
int main()
{
// Start with the empty list
Node* head = NULL;
// Insert 1 at the beginning.
insertAtFront(&head, 6);
insertAtFront(&head, 5);
insertAtFront(&head, 4);
insertAtFront(&head, 3);
insertAtFront(&head, 2);
insertAtFront(&head, 1);
cout << "After inserting nodes at the front:";
printList(head);
head = removeFirstNode(head);
cout << "After removing first node:";
printList(head);
return 0;
}
// Java program to show inserting a node
// at front of given Linked List
import java.io.*;
// A linked list node
class Node {
int data;
Node next;
}
// Class to insert element in LL
class LinkedList {
Node head; // head of list
// Given a reference (pointer to pointer)
// to the head of a list and an int, inserts
// a new node on the front of the list.
void insertAtFront(int new_data)
{
// 1. allocate node
Node new_node = new Node();
// 2. put in the data
new_node.data = new_data;
// 3. Make next of new node as head
new_node.next = head;
// 4. move the head to point
// to the new node
head = new_node;
}
// Function to remove the first node
// of the linked list /
void removeFirstNode()
{
if (head == null)
return;
// Move the head pointer to the next node
Node temp = head;
head = head.next;
}
// This function prints contents of
// linked list starting from head
void printList()
{
Node node = head;
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
System.out.println();
}
// Driver code
public static void main(String[] args)
{
// Start with the empty list
LinkedList list = new LinkedList();
list.insertAtFront(6);
list.insertAtFront(5);
list.insertAtFront(4);
list.insertAtFront(3);
list.insertAtFront(2);
list.insertAtFront(1);
System.out.print("After inserting nodes at the front: ");
list.printList();
list.removeFirstNode();
System.out.print("After removing first node: ");
list.printList();
}
}
OutputAfter inserting nodes at the front: 1 2 3 4 5 6
After removing first node: 2 3 4 5 6
Array
| Linked List
|
|---|
Arrays are stored in contiguous location.
| Linked Lists are not stored in contiguous location.
|
Fixed size.
| Dynamic Size
|
Memory is allocated at compile time.
| Memory is allocated at run time.
|
Uses less memory than Linked Lists.
| Uses more memory than Arrays as it stores both data and address of next node.
|
Elements can be accessed easily in O(1) time.
| Elements can be access by traversing through all the nodes till we reach the required node.
|
Insertion and deletion operation is slower than Linked List.
| Insertion and deletion operation is faster than Linked List.
|
Time Complexity Analysis of Linked List and Array:
| Operation | Linked list | Array |
|---|
| Random Access | O(N) | O(1) |
| Insertion and deletion at beginning | O(1) | O(N) |
| Insertion and deletion at end | O(N) | O(1) |
| Insertion and deletion at a random position | O(N) | O(N) |
- Dynamic nature: Linked lists are used for dynamic memory allocation.
- Memory efficient: Memory consumption of a linked list is efficient as its size can grow or shrink dynamically according to our requirements, which means effective memory utilization hence, no memory wastage.
- Ease of Insertion and Deletion: Insertion and deletion of nodes are easily implemented in a linked list at any position.
- Implementation: For the implementation of stacks and queues and for the representation of trees and graphs.
- The linked list can be expanded in constant time.
- Memory usage: The use of pointers is more in linked lists hence, complex and requires more memory.
- Accessing a node: Random access is not possible due to dynamic memory allocation.
- Search operation costly: Searching for an element is costly and requires O(n) time complexity.
- Traversing in reverse order: Traversing is more time-consuming and reverse traversing is not possible in singly linked lists.
Here are some of the applications of a linked list:
- Linear data structures such as stack, queue, and non-linear data structures such as hash maps, and graphs can be implemented using linked lists.
- Dynamic memory allocation: We use a linked list of free blocks.
- Implementation of graphs: Adjacency list representation of graphs is the most popular in that it uses linked lists to store adjacent vertices.
- In web browsers and editors, doubly linked lists can be used to build a forwards and backward navigation button.
- A circular doubly linked list can also be used for implementing data structures like Fibonacci heaps.
Frequently Asked Questions (FAQs) about Linked List:
1. What is linked list data structure?
Linked list are most commonly used to handle dynamic data elements. Linked list consists of nodes and a node consists of two fields one for storing data and other for keeping the reference of next node.
2. What is linked list example?
A linked list can be assumed as a garland that is made up of flowers. Similarly, a linked list is made up of nodes. Every flower in this particular garland is referred to as a node. In addition, each node points to the next node in this list, and it contains data (in this case, the type of flower).
3. Why do we need linked list data structure??
There are some important advantages to using linked lists over other linear data structures. This is unlike arrays, as they are resizable at runtime. Additionally, they can be easily inserted and deleted.
4. What are linked lists used for?
The linked list is a linear data structure that stores data in nodes. these nodes hold both the data and a reference to the next node in the list. Linked are very efficient at adding and removing nodes because of their simple structure.
5. What is the difference between array and linked list?
There are some following differences between them:
- Arrays are data structures containing similar data elements, whereas linked lists are non-primitive data structures containing unordered linked elements.
- In an array, elements are indexed, but in a linked list nodes are not indexed.
- Accessing an element array is fast if we know the position of an element in the array, while in the Linked list it takes linear time so, the Linked list is quite bit slower.
- Operations like insertion and deletion in arrays take a lot of time. Whereas, the performance of these operations is faster in Linked lists.
- Arrays are of fixed size and their size is static but Linked lists are dynamic and flexible and can expand and shrink their size.
6. Why is a linked list preferred over an array?
Following are the reason that linked lists are preferred over array
- Nodes in a linked array, insertions, and deletions can be done at any point in the list at a constant time.
- Arrays are of fixed size and their size is static but Linked lists are dynamic and flexible and can expand and shrink their size.
- Linked lists provide an efficient way of storing related data and performing basic operations such as insertion, deletion, and updating of information at the cost of extra space required for storing the address.
- Insertion and deletion operations in the linked list are faster as compared to the array.
7. Which is the best array or linked list?
There are some advantages and disadvantages to both arrays and linked lists when it comes to storing linear data of similar types.
Advantages of linked list over arrays:
- Dynamic size: Linked lists are dynamic and flexible and can expand and shrink their size
- Ease of Insertion/Deletion: Insertion and deletion operations in linked list are faster as compared to the array
Disadvantages of linked list over arrays:
- If the array is sorted we can apply binary search to search any element which takes O(log(n)) time. But even if the linked list is sorted we cannot apply binary search and the complexity of searching elements in the linked list is O(n).
- A linked list takes more memory as compared to the array because extra memory space is required for the pointer with each element in the linked list.
8. What are the limitations of linked list?
Following are some limitations of the linked list:
- The use of pointers is more in linked lists hence, complex and requires more memory.
- Random access is not possible due to dynamic memory allocation.
- Traversing is more time-consuming and reverse traversing is not possible in singly linked lists.
- Searching for an element is costly and requires O(n) time complexity.
9. Why insertion/deletion are faster in a linked list?
If any element is inserted/ deleted from the array, all the other elements after it will be shifted in memory this takes a lot of time whereas manipulation in Linked List is faster because we just need to manipulate the addresses of nodes, so no bit shifting is required in memory, and it will not take that much of time.
10. What is the difference between a singly and doubly linked list?
Following are some difference between single and double linked list.
| Singly-linked list (SLL) | Doubly linked list (DLL) |
|---|
| SLL nodes contains 2 field data field and next link field. | DLL nodes contains 3 fields data field, a previous link field and a next link field. |
| In SLL, the traversal can be done using the next node link only. Thus traversal is possible in one direction only. | In DLL, the traversal can be done using the previous node link or the next node link. Thus traversal is possible in both directions (forward and backward). |
| The SLL occupies less memory than DLL as it has only 2 fields. | The DLL occupies more memory than SLL as it has 3 fields. |
| The Complexity of insertion and deletion at a given position is O(n). | The Complexity of insertion and deletion at a given position is O(n / 2) = O(n) because traversal can be made from start or from the end. |
| Complexity of deletion with a given node is O(n), because the previous node needs to be known, and traversal takes O(n) | Complexity of deletion with a given node is O(1) because the previous node can be accessed easily |
| A singly linked list consumes less memory as compared to the doubly linked list. | The doubly linked list consumes more memory as compared to the singly linked list. |
Conclusion:
There are many advantages of the linked list compared to array, despite the fact that they solve the similar problem to arrays, we have also discussed the advantage, disadvantages, and its application, and we concluded the fact that we can use a linked list if we need the dynamic size of storage and list are good for adding and removing items quickly or for tasks that require sequence but are not suitable for querying or search elements in a large collection of data.
So, it becomes important that we should always keep in mind the positive and negative aspects of a data structure and how they relate to the problem you are trying to solve.
Related articles:
------
Insertion in Linked List
Given a Linked List, the task is to insert a new node in this given Linked List at the following positions:
- At the front of the linked list
- After a given node.
- At the end of the linked list.
Approach:
To insert a node at the start/beginning/front of a Linked List, we need to:
- Make the first node of Linked List linked to the new node
- Remove the head from the original first node of Linked List
- Make the new node as the Head of the Linked List.
Below is the implementation of the approach:
C++
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
|
C
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
|
Java
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
|
Python3
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
|
C#
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
|
Javascript
<script>
function push(new_data)
{
var new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
</script>
|
Complexity Analysis:
- Time Complexity: O(1), We have a pointer to the head and we can directly attach a node and change the pointer. So the Time complexity of inserting a node at the head position is O(1) as it does a constant amount of work.
- Auxiliary Space: O(1)
Refer this post for detailed implementation of the above approach.
Approach:
To insert a node after a given node in a Linked List, we need to:
- Check if the given node exists or not.
- If it do not exists,
- If the given node exists,
- Make the element to be inserted as a new node
- Change the next pointer of given node to the new node
- Now shift the original next pointer of given node to the next pointer of new node
Below is the implementation of the approach:
C++
void insertAfter(Node* prev_node, int new_data)
{
if (prev_node == NULL) {
cout << "The given previous node cannot be NULL";
return;
}
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
|
C
void insertAfter(struct Node* prev_node, int new_data)
{
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
|
Java
public void insertAfter(Node prev_node, int new_data)
{
if (prev_node == null) {
System.out.println(
"The given previous node cannot be null");
return;
}
Node new_node = new Node(new_data);
new_node.next = prev_node.next;
prev_node.next = new_node;
}
|
Python3
def insertAfter(self, prev_node, new_data):
if prev_node is None:
print("The given previous node must inLinkedList.")
return
new_node = Node(new_data)
new_node.next = prev_node.next
prev_node.next = new_node
|
C#
public void insertAfter(Node prev_node, int new_data)
{
if (prev_node == null) {
Console.WriteLine("The given previous node"
+ " cannot be null");
return;
}
Node new_node = new Node(new_data);
new_node.next = prev_node.next;
prev_node.next = new_node;
}
|
Javascript
<script>
function insertAfter(prev_node, new_data)
{
if (prev_node == null)
{
document.write("The given previous node cannot be null");
return;
}
var new_node = new Node(new_data);
new_node.next = prev_node.next;
prev_node.next = new_node;
}
</script>
|
Complexity Analysis:
- Time complexity: O(1), since prev_node is already given as argument in a method, no need to iterate over list to find prev_node
- Auxiliary Space: O(1) since using constant space to modify pointers
Refer this post for detailed implementation of the above approach.
Approach:
To insert a node at the end of a Linked List, we need to:
- Go to the last node of the Linked List
- Change the next pointer of last node from NULL to the new node
- Make the next pointer of new node as NULL to show the end of Linked List
Below is the implementation of the approach:
C++
void append(Node** head_ref, int new_data)
{
Node* new_node = new Node();
Node* last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
return;
}
|
C
void append(struct Node** head_ref, int new_data)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
return;
}
|
Java
public void append(int new_data)
{
Node new_node = new Node(new_data);
if (head == null) {
head = new Node(new_data);
return;
}
new_node.next = null;
Node last = head;
while (last.next != null)
last = last.next;
last.next = new_node;
return;
}
|
Python3
def append(self, new_data):
new_node = Node(new_data)
if self.head is None:
self.head = new_node
return
last = self.head
while (last.next):
last = last.next
last.next = new_node
|
C#
public void append(int new_data)
{
Node new_node = new Node(new_data);
if (head == null) {
head = new Node(new_data);
return;
}
new_node.next = null;
Node last = head;
while (last.next != null)
last = last.next;
last.next = new_node;
return;
}
|
Javascript
<script>
function append(new_data)
{
var new_node = new Node(new_data);
if (head == null)
{
head = new Node(new_data);
return;
}
new_node.next = null;
var last = head;
while (last.next != null)
last = last.next;
last.next = new_node;
return;
}
</script>
|
Complexity Analysis:
- Time complexity: O(N), where N is the number of nodes in the linked list. Since there is a loop from head to end, the function does O(n) work.
- This method can also be optimized to work in O(1) by keeping an extra pointer to the tail of the linked list/
- Auxiliary Space: O(1)
Refer this post for detailed implementation of the above approach.
------
Deletion in Linked List
We have discussed Linked List Introduction and Linked List Insertion in previous posts on a singly linked list.
Let us formulate the problem statement to understand the deletion process.
Delete from a Linked List:-
You can delete an element in a list from:
1) Delete from Beginning:
Point head to the next node i.e. second node
temp = head
head = head->next
Make sure to free unused memory
free(temp); or delete temp;
2) Delete from End:
Point head to the previous element i.e. last second element
Change next pointer to null
struct node *end = head;
struct node *prev = NULL;
while(end->next)
{
prev = end;
end = end->next;
}
prev->next = NULL;
Make sure to free unused memory
free(end); or delete end;
3) Delete from Middle:
Keeps track of pointer before node to delete and pointer to node to delete
temp = head;
prev = head;
for(int i = 0; i < position; i++)
{
if(i == 0 && position == 1)
head = head->next;
free(temp)
else
{
if (i == position - 1 && temp)
{
prev->next = temp->next;
free(temp);
}
else
{
prev = temp;
if(prev == NULL) // position was greater than number of nodes in the list
break;
temp = temp->next;
}
}
}
Iterative Method to delete an element from the linked list:
To delete a node from the linked list, we need to do the following steps:
- Find the previous node of the node to be deleted.
- Change the next of the previous node.
- Free memory for the node to be deleted.
Below is the implementation to delete a node from the list at some position:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int number;
Node* next;
};
void Push(Node** head, int A)
{
Node* n = (Node*)malloc(sizeof(Node));
n->number = A;
n->next = *head;
*head = n;
}
void deleteN(Node** head, int position)
{
Node* temp;
Node* prev;
temp = *head;
prev = *head;
for (int i = 0; i < position; i++) {
if (i == 0 && position == 1) {
*head = (*head)->next;
free(temp);
}
else {
if (i == position - 1 && temp) {
prev->next = temp->next;
free(temp);
}
else {
prev = temp;
if (prev == NULL)
break;
temp = temp->next;
}
}
}
}
void printList(Node* head)
{
while (head) {
if (head->next == NULL)
cout << "[" << head->number << "] "
<< "[" << head << "]->"
<< "(nil)" << endl;
else
cout << "[" << head->number << "] "
<< "[" << head << "]->" << head->next
<< endl;
head = head->next;
}
cout << endl << endl;
}
int main()
{
Node* list = (Node*)malloc(sizeof(Node));
list->next = NULL;
Push(&list, 1);
Push(&list, 2);
Push(&list, 3);
printList(list);
deleteN(&list, 1);
printList(list);
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int number;
struct Node* next;
} Node;
void Push(Node** head, int A)
{
Node* n = malloc(sizeof(Node));
n->number = A;
n->next = *head;
*head = n;
}
void deleteN(Node** head, int position)
{
Node* temp;
Node* prev;
temp = *head;
prev = *head;
for (int i = 0; i < position; i++) {
if (i == 0 && position == 1) {
*head = (*head)->next;
free(temp);
}
else {
if (i == position - 1 && temp) {
prev->next = temp->next;
free(temp);
}
else {
prev = temp;
if (prev == NULL)
break;
temp = temp->next;
}
}
}
}
void printList(Node* head)
{
while (head) {
printf("[%i] [%p]->%p\n", head->number, head,
head->next);
head = head->next;
}
printf("\n\n");
}
int main()
{
Node* list = malloc(sizeof(Node));
list->next = NULL;
Push(&list, 1);
Push(&list, 2);
Push(&list, 3);
printList(list);
deleteN(&list, 1);
printList(list);
return 0;
}
|
Java
class Node {
int number;
Node next;
}
class Main {
public static Node push(Node head, int A) {
Node n = new Node();
n.number = A;
n.next = head;
head = n;
return head;
}
public static Node deleteN(Node head, int position) {
Node temp = head;
Node prev = head;
for (int i = 0; i < position; i++) {
if (i == 0 && position == 1) {
head = head.next;
} else {
if (i == position - 1 && temp != null) {
prev.next = temp.next;
} else {
prev = temp;
if (prev == null)
break;
temp = temp.next;
}
}
}
return head;
}
public static void printList(Node head) {
while (head != null) {
if (head.next == null) {
System.out.println("[" + head.number + "] [" + head + "]->" + "(null)");
} else {
System.out.println("[" + head.number + "] [" + head + "]->" + head.next);
}
head = head.next;
}
System.out.println();
System.out.println();
}
public static void main(String[] args) {
Node list = new Node();
list.next = null;
list = push(list, 1);
list = push(list, 2);
list = push(list, 3);
printList(list);
list = deleteN(list, 1);
printList(list);
}
}
|
Python3
class Node:
def __init__(self, data):
self.number = data
self.next = None
def push(head, A):
n = Node(A)
n.number = A
n.next = head
head = n
return head
def deleteN(head, position):
temp = head
prev = head
for i in range(0, position):
if i == 0 and position == 1:
head = head.next
else:
if i == position-1 and temp is not None:
prev.next = temp.next
else:
prev = temp
if prev is None:
break
temp = temp.next
return head
def printList(head):
while(head):
if head.next == None:
print("[", head.number, "] ", "[", hex(id(head)), "]->", "nil")
else:
print("[", head.number, "] ", "[", hex(
id(head)), "]->", hex(id(head.next)))
head = head.next
print("")
print("")
head = Node(0)
head = push(head, 1)
head = push(head, 2)
head = push(head, 3)
printList(head)
head = deleteN(head, 1)
printList(head)
|
Javascript
class Node {
constructor(number) {
this.number = number;
this.next = null;
}
}
function push(head, number) {
const node = new Node(number);
node.next = head;
head = node;
return head;
}
function deleteN(head, position) {
let temp = head;
let prev = head;
for (let i = 0; i < position; i++) {
if (i === 0 && position === 1) {
head = head.next;
temp = null;
} else {
if (i === position - 1 && temp) {
prev.next = temp.next;
temp = null;
} else {
prev = temp;
if (prev === null) break;
temp = temp.next;
}
}
}
return head;
}
function printList(head) {
while (head) {
if (head.next === null)
console.log(`[${head.number}] [${head}]->(nil)`);
else console.log(`[${head.number}] [${head}]->${head.next}`);
head = head.next;
}
console.log('\n');
}
let list = new Node(0);
list.next = null;
list = push(list, 1);
list = push(list, 2);
list = push(list, 3);
printList(list);
list = deleteN(list, 1);
printList(list);
|
C#
using System;
public class Node {
public int number;
public Node next;
}
public class Program {
public static void Push(ref Node head, int A)
{
Node n = new Node();
n.number = A;
n.next = head;
head = n;
}
public static void deleteN(ref Node head, int position)
{
Node temp = head;
Node prev = head;
for (int i = 0; i < position; i++) {
if (i == 0 && position == 1) {
head = head.next;
temp = null;
}
else {
if (i == position - 1 && temp != null) {
prev.next = temp.next;
temp = null;
}
else {
prev = temp;
if (prev == null) {
break;
}
temp = temp.next;
}
}
}
}
public static void printList(Node head)
{
while (head != null) {
if (head.next == null) {
Console.WriteLine("[" + head.number + "] "
+ "[" + head + "]->"
+ "(nil)");
}
else {
Console.WriteLine("[" + head.number + "] "
+ "[" + head + "]->"
+ head.next);
}
head = head.next;
}
Console.WriteLine("\n");
}
public static void Main()
{
Node list = new Node();
list.next = null;
Push(ref list, 1);
Push(ref list, 2);
Push(ref list, 3);
printList(list);
deleteN(ref list, 1);
printList(list);
}
}
|
Output
[3] [0x1b212c0]->0x1b212a0
[2] [0x1b212a0]->0x1b21280
[1] [0x1b21280]->0x1b21260
[0] [0x1b21260]->(nil)
[2] [0x1b212a0]->0x1b21280
[1] [0x1b21280]->0x1b21260
[0] [0x1b21260]->(nil)
Time Complexity: O(n)
Auxiliary Space: O(1)
Recursive Method to delete a node from linked list:
To delete a node of a linked list recursively we need to do the following steps:
- We pass node* (node pointer) as a reference to the function (as in node* &head)
- Now since the current node pointer is derived from the previous node’s next (which is passed by reference) so now if the value of the current node pointer is changed, the previous next node’s value also gets changed which is the required operation while deleting a node (i.e points previous node’s next to current node’s (containing key) next).
- Find the node containing the given value.
- Store this node to deallocate it later using the free() function.
- Change this node pointer so that it points to its next and by performing this previous node’s next also gets properly linked.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h>
using namespace std;
struct node {
int info;
node* link = NULL;
node() {}
node(int a)
: info(a)
{
}
};
void deleteNode(node*& head, int val)
{
if (head == NULL) {
cout << "Element not present in the list\n";
return;
}
if (head->info == val) {
node* t = head;
head = head->link;
delete (t);
return;
}
deleteNode(head->link, val);
}
void push(node*& head, int data)
{
node* newNode = new node(data);
newNode->link = head;
head = newNode;
}
void print(node* head)
{
if (head == NULL and cout << endl)
return;
cout << head->info << ' ';
print(head->link);
}
int main()
{
node* head = NULL;
push(head, 10);
push(head, 12);
push(head, 14);
push(head, 15);
print(head);
deleteNode(head, 20);
print(head);
deleteNode(head, 10);
print(head);
deleteNode(head, 14);
print(head);
return 0;
}
|
Python3
class Node:
def __init__(self,data):
self.data = data
self.next = None
def deleteNode(head, val):
if (head == None):
print("Element not present in the list")
return -1
if (head.data == val):
if head.next:
head.data = head.next.data
head.next = head.next.next
return 1
else: return 0
if deleteNode(head.next, val) == 0:
head.next = None
return 1
def push(head, data):
newNode = Node(data)
newNode.next = head
head = newNode
return head
def printLL(head):
if (head == None):
return
temp = head
while temp:
print(temp.data,end=' ')
temp = temp.next
print()
head = None
head = push(head, 10)
head = push(head, 12)
head = push(head, 14)
head = push(head, 15)
printLL(head)
deleteNode(head, 20)
printLL(head)
deleteNode(head, 10)
printLL(head)
deleteNode(head, 14)
printLL(head)
|
C#
using System;
class LinkedList
{
public class Node
{
public int info;
public Node link;
public Node(int a)
{
info = a;
link = null;
}
}
public static void deleteNode(ref Node head, int val)
{
if (head == null)
{
Console.WriteLine("Element not present in the list");
return;
}
if (head.info == val)
{
Node t = head;
head = head.link;
t = null;
return;
}
deleteNode(ref head.link, val);
}
public static void push(ref Node head, int data)
{
Node newNode = new Node(data);
newNode.link = head;
head = newNode;
}
public static void print(Node head)
{
if (head == null)
{
Console.WriteLine();
return;
}
Console.Write(head.info + " ");
print(head.link);
}
public static void Main(string[] args)
{
Node head = null;
push(ref head, 10);
push(ref head, 12);
push(ref head, 14);
push(ref head, 15);
print(head);
deleteNode(ref head, 20);
print(head);
deleteNode(ref head, 10);
print(head);
deleteNode(ref head, 14);
print(head);
}
}
|
Javascript
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function deleteNode(head, val)
{
if (!head) {
console.log("Element not present in the list");
return -1;
}
if (head.data == val) {
if (head.next) {
head.data = head.next.data;
head.next = head.next.next;
return 1;
} else return 0;
}
if (deleteNode(head.next, val) == 0) {
head.next = null;
return 1;
}
}
function push(head, data) {
let newNode = new Node(data);
newNode.next = head;
head = newNode;
return head;
}
function printLL(head) {
if (!head) return;
let temp = head;
while (temp) {
console.log(temp.data, " ");
temp = temp.next;
}
console.log();
}
let head = null;
head = push(head, 10);
head = push(head, 12);
head = push(head, 14);
head = push(head, 15);
printLL(head);
deleteNode(head, 20);
printLL(head);
deleteNode(head, 10);
printLL(head);
deleteNode(head, 14);
printLL(head);
|
Java
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
public static int deleteNode(Node head, int val) {
if (head == null) {
System.out.println("Element not present in the list");
return -1;
}
if (head.data == val) {
if (head.next != null) {
head.data = head.next.data;
head.next = head.next.next;
return 1;
} else
return 0;
}
if (deleteNode(head.next, val) == 0) {
head.next = null;
return 1;
}
return -1;
}
public static Node push(Node head, int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
return head;
}
public static void printLL(Node head) {
if (head == null)
return;
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = null;
head = push(head, 10);
head = push(head, 12);
head = push(head, 14);
head = push(head, 15);
printLL(head);
deleteNode(head, 20);
printLL(head);
deleteNode(head, 10);
printLL(head);
deleteNode(head, 14);
printLL(head);
}
}
|
Output
15 14 12 10
Element not present in the list
15 14 12 10
15 14 12
15 12
Time Complexity: O(n)
Auxiliary Space: O(n) (due to recursion call stack)
------
Insertion in a Doubly Linked List
Inserting a new node in a doubly linked list is very similar to inserting new node in linked list. There is a little extra work required to maintain the link of the previous node. A node can be inserted in a Doubly Linked List in four ways:
- At the front of the DLL.
- In between two nodes
- After a given node.
- Before a given node.
- At the end of the DLL.
Insertion at the Beginning in Doubly Linked List:
To insert a new node at the beginning of the doubly list, we can use the following steps:
- Allocate memory for a new node (say new_node) and assign the provided value to its data field.
- Set the previous pointer of the new_node to nullptr.
- If the list is empty:
- Set the next pointer of the new_node to nullptr.
- Update the head pointer to point to the new_node.
- If the list is not empty:
- Set the next pointer of the new_node to the current head.
- Update the previous pointer of the current head to point to the new_node.
- Update the head pointer to point to the new_node.
Below is the implementation of the 5 steps to insert a node at the front of the linked list:
// Given a reference (pointer to pointer) to the head
// of a list and an int, inserts a new node
// on the front of the list.
void push(Node** head_ref, int new_data)
{
// 1. allocate node
Node* new_node = new Node();
// 2. put in the data
new_node->data = new_data;
// 3. Make next of new node as head
// and previous as NULL
new_node->next = (*head_ref);
new_node->prev = NULL;
// 4. change prev of head node to new node
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
// 5. move the head to point to the new node
(*head_ref) = new_node;
}
// This code is contributed by shivanisinghss2110
// Adding a node at the front of the list
public void push(int new_data)
{
// 1. allocate node
// 2. put in the data */
Node new_Node = new Node(new_data);
// 3. Make next of new node as head and previous as NULL
new_Node.next = head;
new_Node.prev = null;
// 4. change prev of head node to new node
if (head != null)
head.prev = new_Node;
// 5. move the head to point to the new node
head = new_Node;
}
Time Complexity: O(1)
Auxiliary Space: O(1)
Insertion in between two nodes in Doubly Linked List:
1. Add a node after a given node in a Doubly Linked List:
We are given a pointer to a node as prev_node, and the new node is inserted after the given node. This can be done using the following steps:
- Firstly create a new node (say new_node).
- Now insert the data in the new node.
- Point the next of new_node to the next of prev_node.
- Point the next of prev_node to new_node.
- Point the previous of new_node to prev_node.
- Point the previous of next of new_node to new_node.
Below is the implementation of the steps to insert a node after a given node in the linked list:
// Given a node as prev_node, insert a new node
// after the given node
void insertAfter(Node* prev_node, int new_data)
{
// Check if the given prev_node is NULL
if (prev_node == NULL) {
cout << "the given previous node cannot be NULL";
return;
}
// 1. allocate new node
Node* new_node = new Node();
// 2. put in the data
new_node->data = new_data;
// 3. Make next of new node as next of prev_node
new_node->next = prev_node->next;
// 4. Make the next of prev_node as new_node
prev_node->next = new_node;
// 5. Make prev_node as previous of new_node
new_node->prev = prev_node;
// 6. Change previous of new_node's next node
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
// Given a node as prev_node, insert a new node
// after the given node
public void InsertAfter(Node prev_Node, int new_data)
{
// Check if the given prev_node is NULL
if (prev_Node == null) {
System.out.println(
"The given previous node cannot be NULL ");
return;
}
// 1. allocate node
// 2. put in the data
Node new_node = new Node(new_data);
// 3. Make next of new node as next of prev_node
new_node.next = prev_Node.next;
// 4. Make the next of prev_node as new_node
prev_Node.next = new_node;
// 5. Make prev_node as previous of new_node
new_node.prev = prev_Node;
// 6. Change previous of new_node's next node
if (new_node.next != null)
new_node.next.prev = new_node;
}
Time Complexity: O(1)
Auxiliary Space: O(1)
2. Add a node before a given node in a Doubly Linked List:
Let the pointer to this given node be next_node. This can be done using the following steps.
- Allocate memory for the new node, let it be called new_node.
- Put the data in new_node.
- Set the previous pointer of this new_node as the previous node of the next_node.
- Set the previous pointer of the next_node as the new_node.
- Set the next pointer of this new_node as the next_node.
- Set the next pointer of the previous of new_node to new_node.
Below is the implementation of the above approach.
// Given a node as prev_node, insert a new node
// after the given node
void insertBefore(Node* next_node, int new_data)
{
// Check if the given next_node is NULL
if (next_node == NULL) {
printf("the given next node cannot be NULL");
return;
}
// 1. Allocate new node
Node* new_node = new Node();
// 2. Put in the data
new_node->data = new_data;
// 3. Make previous of new node as previous of next_node
new_node->prev = next_node->prev;
// 4. Make the previous of next_node as new_node
next_node->prev = new_node;
// 5. Make next_node as next of new_node
new_node->next = next_node;
// 6. Change next of new_node's previous node
if (new_node->prev != NULL)
new_node->prev->next = new_node;
else
head = new_node;
}
// Given a node as prev_node, insert a new node
// after the given node
public void InsertBefore(Node next_Node, int new_data)
{
// Check if the given next_node is NULL
if (next_Node == null) {
System.out.println(
"The given next node cannot be NULL ");
return;
}
// 1. Allocate node
// 2. Put in the data
Node new_node = new Node(new_data);
// 3. Make previous of new node as previous of prev_node
new_node.prev = next_Node.prev;
// 4. Make the prev of next_node as new_node
next_Node.prev = new_node;
// 5. Make next_node as next of new_node
new_node.next = next_Node;
// 6. Change next of new_node's previous node
if (new_node.prev != null)
new_node.prev.next = new_node;
else
head = new_node;
}
Time Complexity: O(1)
Auxiliary Space: O(1)
Insertion at the End in Doubly Linked List:
The new node is always added after the last node of the given Linked List. This can be done using the following steps:
- Create a new node (say new_node).
- Put the value in the new node.
- Make the next pointer of new_node as null.
- If the list is empty, make new_node as the head.
- Otherwise, travel to the end of the linked list.
- Now make the next pointer of last node point to new_node.
- Change the previous pointer of new_node to the last node of the list.
Below is the implementation of the steps to insert a node at the end of the linked list:
// Given a reference (pointer to pointer) to the head
// of a DLL and an int, appends a new node at the end
void append(Node** head_ref, int new_data)
{
// 1. allocate node
Node* new_node = new Node();
Node* last = *head_ref; /* used in step 5*/
// 2. put in the data
new_node->data = new_data;
// 3. This new node is going to be the last node, so
// make next of it as NULL
new_node->next = NULL;
// 4. If the Linked List is empty, then make the new
// node as head
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
// 5. Else traverse till the last node
while (last->next != NULL)
last = last->next;
// 6. Change the next of last node
last->next = new_node;
// 7. Make last node as previous of new node
new_node->prev = last;
return;
}
// This code is contributed by shivanisinghss2110
// Add a node at the end of the list
void append(int new_data)
{
// 1. allocate node
// 2. put in the data
Node new_node = new Node(new_data);
Node last = head; /* used in step 5*/
// 3. This new node is going to be the last node, so
// make next of it as NULL
new_node.next = null;
// 4. If the Linked List is empty, then make the new
// node as head
if (head == null) {
new_node.prev = null;
head = new_node;
return;
}
// 5. Else traverse till the last node
while (last.next != null)
last = last.next;
// 6. Change the next of last node
last.next = new_node;
// 7. Make last node as previous of new node
new_node.prev = last;
}
Time Complexity: O(n)
Auxiliary Space: O(1)
Related Articles:
------
Delete a node in a Doubly Linked List
Write a function to delete a given node in a doubly-linked list.
Example:
Input: DLL = 2->45->3->1, Node = 45
Output: 2->3->1
Input: DLL = 2->45->3->1, Node = 1
Output: 2->45->3
Approach: The deletion of a node in a doubly-linked list can be divided into three main categories:
- After the deletion of the head node.
- After the deletion of the middle node.
- After the deletion of the last node.
All three mentioned cases can be handled in two steps if the pointer of the node to be deleted and the head pointer is known.
- If the node to be deleted is the head node then make the next node as head.
- If a node is deleted, connect the next and previous node of the deleted node.
Algorithm:
- Let the node to be deleted be del.
- If node to be deleted is head node, then change the head pointer to next current head.
if headnode == del then
headnode = del.nextNode
- Set prev of next to del, if next to del exists.
if del.nextNode != none
del.nextNode.previousNode = del.previousNode
- Set next of previous to del, if previous to del exists.
if del.previousNode != none
del.previousNode.nextNode = del.next
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node* next;
Node* prev;
};
void deleteNode(Node** head_ref, Node* del)
{
if (*head_ref == NULL || del == NULL)
return;
if (*head_ref == del)
*head_ref = del->next;
if (del->next != NULL)
del->next->prev = del->prev;
if (del->prev != NULL)
del->prev->next = del->next;
free(del);
return;
}
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->prev = NULL;
new_node->next = (*head_ref);
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}
void printList(Node* node)
{
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
int main()
{
Node* head = NULL;
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
cout << "Original Linked list ";
printList(head);
deleteNode(&head, head);
deleteNode(&head, head->next);
deleteNode(&head, head->next);
cout << "\nModified Linked list ";
printList(head);
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void deleteNode(struct Node** head_ref, struct Node* del)
{
if (*head_ref == NULL || del == NULL)
return;
if (*head_ref == del)
*head_ref = del->next;
if (del->next != NULL)
del->next->prev = del->prev;
if (del->prev != NULL)
del->prev->next = del->next;
free(del);
return;
}
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->prev = NULL;
new_node->next = (*head_ref);
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
int main()
{
struct Node* head = NULL;
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
printf("\n Original Linked list ");
printList(head);
deleteNode(&head, head);
deleteNode(&head, head->next);
deleteNode(&head, head->next);
printf("\n Modified Linked list ");
printList(head);
getchar();
}
|
Java
public class DLL {
Node head;
class Node {
int data;
Node prev;
Node next;
Node(int d) { data = d; }
}
public void push(int new_data)
{
Node new_Node = new Node(new_data);
new_Node.next = head;
new_Node.prev = null;
if (head != null)
head.prev = new_Node;
head = new_Node;
}
public void printlist(Node node)
{
Node last = null;
while (node != null) {
System.out.print(node.data + " ");
last = node;
node = node.next;
}
System.out.println();
}
void deleteNode(Node del)
{
if (head == null || del == null) {
return;
}
if (head == del) {
head = del.next;
}
if (del.next != null) {
del.next.prev = del.prev;
}
if (del.prev != null) {
del.prev.next = del.next;
}
return;
}
public static void main(String[] args)
{
DLL dll = new DLL();
dll.push(2);
dll.push(4);
dll.push(8);
dll.push(10);
System.out.print("Original Linked list ");
dll.printlist(dll.head);
dll.deleteNode(dll.head);
dll.deleteNode(dll.head.next);
dll.deleteNode(dll.head.next);
System.out.print(
"\nModified Linked list ");
dll.printlist(dll.head);
}
}
|
Python3
import gc
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def deleteNode(self, dele):
if self.head is None or dele is None:
return
if self.head == dele:
self.head = dele.next
if dele.next is not None:
dele.next.prev = dele.prev
if dele.prev is not None:
dele.prev.next = dele.next
gc.collect()
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
self.head = new_node
def printList(self, node):
while(node is not None):
print(node.data,end=' ')
node = node.next
dll = DoublyLinkedList()
dll.push(2);
dll.push(4);
dll.push(8);
dll.push(10);
print ("\n Original Linked List",end=' ')
dll.printList(dll.head)
dll.deleteNode(dll.head)
dll.deleteNode(dll.head.next)
dll.deleteNode(dll.head.next)
print("\n Modified Linked List",end=' ')
dll.printList(dll.head)
|
C#
using System;
public class DLL
{
Node head;
public class Node
{
public int data;
public Node prev;
public Node next;
public Node(int d) { data = d; }
}
public void push(int new_data)
{
Node new_Node = new Node(new_data);
new_Node.next = head;
new_Node.prev = null;
if (head != null)
head.prev = new_Node;
head = new_Node;
}
public void printlist(Node node)
{
while (node != null)
{
Console.Write(node.data + " ");
node = node.next;
}
Console.WriteLine();
}
void deleteNode(Node del)
{
if (head == null || del == null)
{
return;
}
if (head == del)
{
head = del.next;
}
if (del.next != null)
{
del.next.prev = del.prev;
}
if (del.prev != null)
{
del.prev.next = del.next;
}
return;
}
public static void Main()
{
DLL dll = new DLL();
dll.push(2);
dll.push(4);
dll.push(8);
dll.push(10);
Console.Write("Original Linked list ");
dll.printlist(dll.head);
dll.deleteNode(dll.head);
dll.deleteNode(dll.head.next);
dll.deleteNode(dll.head.next);
Console.Write("Modified Linked list ");
dll.printlist(dll.head);
}
}
|
Javascript
<script>
var head;
class Node {
constructor(val) {
this.data = val;
this.prev = null;
this.next = null;
}
}
function push(new_data) {
new_Node = new Node(new_data);
new_Node.next = head;
new_Node.prev = null;
if (head != null)
head.prev = new_Node;
head = new_Node;
}
function printlist( node) {
last = null;
while (node != null) {
document.write(node.data + " ");
last = node;
node = node.next;
}
document.write("<br/>");
}
function deleteNode( del) {
if (head == null || del == null) {
return;
}
if (head == del) {
head = del.next;
}
if (del.next != null) {
del.next.prev = del.prev;
}
if (del.prev != null) {
del.prev.next = del.next;
}
return;
}
push(2);
push(4);
push(8);
push(10);
document.write("Created DLL is: ");
printlist(head);
deleteNode(head);
deleteNode(head.next);
deleteNode(head.next);
document.write("Modified Linked list: ");
printlist(head);
</script>
|
Output
Original Linked list 10 8 4 2
Modified Linked list 8
Complexity Analysis:
- Time Complexity: O(1).
Since traversal of the linked list is not required so the time complexity is constant.
- Auxiliary Space: O(1).
As no extra space is required, so the space complexity is constant.
------
Circular Singly Linked List | Insertion
We have discussed Singly and Circular Linked List in the following post:
Singly Linked List
Circular Linked List
Why Circular linked list?
In a singly linked list, for accessing any node of the linked list, we start traversing from the first node. If we are at any node in the middle of the list, then it is not possible to access nodes that precede the given node. This problem can be solved by slightly altering the structure of a singly linked list. In a singly linked list, the next part (pointer to the next node) of the last node is NULL. If we utilize this link to point to the first node, then we can reach the preceding nodes. Refer to this for more advantages of circular linked lists.
In this post, the implementation and insertion of a node in a Circular Linked List using a singly linked list are explained.
Implementation of circular linked list:
To implement a circular singly linked list, we take an external pointer that points to the last node of the list. If we have a pointer last pointing to the last node, then last -> next will point to the first node.
The pointer last points to node Z and last -> next points to node P.
Why have we taken a pointer that points to the last node instead of the first node?
For the insertion of a node at the beginning, we need to traverse the whole list. Also, for insertion at the end, the whole list has to be traversed. If instead of the start pointer, we take a pointer to the last node, then in both cases there won’t be any need to traverse the whole list. So insertion at the beginning or at the end takes constant time, irrespective of the length of the list.
Insertion in a circular linked list:
A node can be added in three ways:
- Insertion in an empty list
- Insertion at the beginning of the list
- Insertion at the end of the list
- Insertion in between the nodes
Insertion in an empty List:
Initially, when the list is empty, the last pointer will be NULL.
After inserting node T,
After insertion, T is the last node, so the pointer last points to node T. And Node T is the first and the last node, so T points to itself.
Below is the implementation of the above operation:
C++
struct Node* addToEmpty(struct Node* last, int data)
{
if (last != NULL)
return last;
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
last = temp;
temp->next = last;
return last;
}
|
Java
static Node addToEmpty(Node last, int data)
{
if (last != null)
return last;
Node temp = new Node();
temp.data = data;
last = temp;
temp.next = last;
return last;
}
|
Python3
def addToEmpty(self, data):
if (self.last != None):
return self.last
temp = Node(data)
self.last = temp
self.last.next = self.last
return self.last
|
C#
static Node addToEmpty(Node last, int data)
{
if (last != null)
return last;
Node temp = new Node();
temp.data = data;
last = temp;
temp.next = last;
return last;
}
|
Javascript
function addToEmpty(last , data)
{
if (last != null)
return last;
var temp = new Node();
temp.data = data;
last = temp;
temp.next = last;
return last;
}
|
Time Complexity: O(1), As we have to perform constant number of operations.
Auxiliary Space: O(1), As constant extra space is used.
Insertion at the beginning of the list
To insert a node at the beginning of the list, follow these steps:
- Create a node, say T
- Make T -> next = last -> next
- last -> next = T
After insertion,
Below is the implementation of the above operation:
C++
struct Node* addBegin(struct Node* last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = last->next;
last->next = temp;
return last;
}
|
Java
static Node addBegin(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
return last;
}
|
Python3
def addBegin(self, data):
if (self.last == None):
return self.addToEmpty(data)
temp = Node(data)
temp.next = self.last.next
self.last.next = temp
return self.last
|
C#
static Node addBegin(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
return last;
}
|
Javascript
function addBegin(last , data)
{
if (last == null)
return addToEmpty(last, data);
var temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
return last;
}
|
Time complexity: O(1)
Auxiliary Space: O(1)
Insertion at the end of the list
To insert a node at the end of the list, follow these steps:
- Create a node, say T
- Make T -> next = last -> next
- last -> next = T
- last = T
After insertion
Below is the implementation of the above operation:
C++
struct Node* addEnd(struct Node* last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = last->next;
last->next = temp;
last = temp;
return last;
}
|
Java
static Node addEnd(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
|
Python3
def addEnd(self, data):
if (self.last == None):
return self.addToEmpty(data)
temp = Node(data)
temp.next = self.last.next
self.last.next = temp
self.last = temp
return self.last
|
C#
static Node addEnd(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
|
Javascript
function addEnd(last, data) {
if (last == null) return addToEmpty(last, data);
var temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
|
Time Complexity: O(1)
Auxiliary Space: O(1)
Insertion in between the nodes
To insert a node in between the two nodes, follow these steps:
- Create a node, say T.
- Search for the node after which T needs to be inserted, say that node is P.
- Make T -> next = P -> next;
- P -> next = T.
Suppose 12 needs to be inserted after the node that has the value 8,
After searching and insertion,
Below is the implementation of the above operation:
C++
struct Node* addAfter(struct Node* last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *p;
p = last->next;
do {
if (p->data == item) {
temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = p->next;
p->next = temp;
if (p == last)
last = temp;
return last;
}
p = p->next;
} while (p != last->next);
cout << item << " not present in the list." << endl;
return last;
}
|
Java
static Node addAfter(Node last, int data, int item)
{
if (last == null)
return null;
Node temp, p;
p = last.next;
do {
if (p.data == item) {
temp = new Node();
temp.data = data;
temp.next = p.next;
p.next = temp;
if (p == last)
last = temp;
return last;
}
p = p.next;
} while (p != last.next);
System.out.println(item + " not present in the list.");
return last;
}
|
Python3
def addAfter(self, data, item):
if (self.last == None):
return None
temp = Node(data)
p = self.last.next
while p:
if (p.data == item):
temp.next = p.next
p.next = temp
if (p == self.last):
self.last = temp
return self.last
else:
return self.last
p = p.next
if (p == self.last.next):
print(item, "not present in the list")
break
|
C#
static Node addAfter(Node last, int data, int item)
{
if (last == null)
return null;
Node temp, p;
p = last.next;
do {
if (p.data == item) {
temp = new Node();
temp.data = data;
temp.next = p.next;
p.next = temp;
if (p == last)
last = temp;
return last;
}
p = p.next;
} while (p != last.next);
Console.WriteLine(item + " not present in the list.");
return last;
}
|
Javascript
function addAfter(last, data, item) {
if (last == null) return null;
var temp, p;
p = last.next;
do {
if (p.data == item) {
temp = new Node();
temp.data = data;
temp.next = p.next;
p.next = temp;
if (p == last) last = temp;
return last;
}
p = p.next;
} while (p != last.next);
document.write(item + " not present in the list. <br>");
return last;
}
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Below is a complete program that uses all of the above methods to create a circular singly linked list.
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
struct Node* addToEmpty(struct Node* last, int data)
{
if (last != NULL)
return last;
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
last = temp;
last->next = last;
return last;
}
struct Node* addBegin(struct Node* last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = last->next;
last->next = temp;
return last;
}
struct Node* addEnd(struct Node* last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = last->next;
last->next = temp;
last = temp;
return last;
}
struct Node* addAfter(struct Node* last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *p;
p = last->next;
do {
if (p->data == item) {
temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = p->next;
p->next = temp;
if (p == last)
last = temp;
return last;
}
p = p->next;
} while (p != last->next);
cout << item << " not present in the list." << endl;
return last;
}
void traverse(struct Node* last)
{
struct Node* p;
if (last == NULL) {
cout << "List is empty." << endl;
return;
}
p = last->next;
do {
cout << p->data << " ";
p = p->next;
} while (p != last->next);
}
int main()
{
struct Node* last = NULL;
last = addToEmpty(last, 6);
last = addBegin(last, 4);
last = addBegin(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addAfter(last, 10, 8);
traverse(last);
return 0;
}
|
Java
public class GFG {
static class Node {
int data;
Node next;
};
static Node addToEmpty(Node last, int data)
{
if (last != null)
return last;
Node temp = new Node();
temp.data = data;
last = temp;
last.next = last;
return last;
}
static Node addBegin(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
return last;
}
static Node addEnd(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
static Node addAfter(Node last, int data, int item)
{
if (last == null)
return null;
Node temp, p;
p = last.next;
do {
if (p.data == item) {
temp = new Node();
temp.data = data;
temp.next = p.next;
p.next = temp;
if (p == last)
last = temp;
return last;
}
p = p.next;
} while (p != last.next);
System.out.println(item
+ " not present in the list.");
return last;
}
static void traverse(Node last)
{
Node p;
if (last == null) {
System.out.println("List is empty.");
return;
}
p = last.next;
do {
System.out.print(p.data + " ");
p = p.next;
} while (p != last.next);
}
public static void main(String[] args)
{
Node last = null;
last = addToEmpty(last, 6);
last = addBegin(last, 4);
last = addBegin(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addAfter(last, 10, 8);
traverse(last);
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = 0
class CircularLinkedList:
def __init__(self):
self.last = None
def addToEmpty(self, data):
if (self.last != None):
return self.last
temp = Node(data)
self.last = temp
self.last.next = self.last
return self.last
def addBegin(self, data):
if (self.last == None):
return self.addToEmpty(data)
temp = Node(data)
temp.next = self.last.next
self.last.next = temp
return self.last
def addEnd(self, data):
if (self.last == None):
return self.addToEmpty(data)
temp = Node(data)
temp.next = self.last.next
self.last.next = temp
self.last = temp
return self.last
def addAfter(self, data, item):
if (self.last == None):
return None
temp = Node(data)
p = self.last.next
while p:
if (p.data == item):
temp.next = p.next
p.next = temp
if (p == self.last):
self.last = temp
return self.last
else:
return self.last
p = p.next
if (p == self.last.next):
print(item, "not present in the list")
break
def traverse(self):
if (self.last == None):
print("List is empty")
return
temp = self.last.next
while temp:
print(temp.data, end=" ")
temp = temp.next
if temp == self.last.next:
break
if __name__ == '__main__':
llist = CircularLinkedList()
last = llist.addToEmpty(6)
last = llist.addBegin(4)
last = llist.addBegin(2)
last = llist.addEnd(8)
last = llist.addEnd(12)
last = llist.addAfter(10, 8)
llist.traverse()
|
C#
using System;
public class GFG {
public class Node {
public int data;
public Node next;
};
static Node addToEmpty(Node last, int data)
{
if (last != null)
return last;
Node temp = new Node();
temp.data = data;
last = temp;
last.next = last;
return last;
}
static Node addBegin(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
return last;
}
static Node addEnd(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
static Node addAfter(Node last, int data, int item)
{
if (last == null)
return null;
Node temp, p;
p = last.next;
do {
if (p.data == item) {
temp = new Node();
temp.data = data;
temp.next = p.next;
p.next = temp;
if (p == last)
last = temp;
return last;
}
p = p.next;
} while (p != last.next);
Console.WriteLine(item
+ " not present in the list.");
return last;
}
static void traverse(Node last)
{
Node p;
if (last == null) {
Console.WriteLine("List is empty.");
return;
}
p = last.next;
do {
Console.Write(p.data + " ");
p = p.next;
} while (p != last.next);
}
public static void Main(String[] args)
{
Node last = null;
last = addToEmpty(last, 6);
last = addBegin(last, 4);
last = addBegin(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addAfter(last, 10, 8);
traverse(last);
}
}
|
Javascript
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
function addToEmpty(last, data) {
if (last != null) return last;
var temp = new Node();
temp.data = data;
last = temp;
last.next = last;
return last;
}
function addBegin(last, data) {
if (last == null) return addToEmpty(last, data);
var temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
return last;
}
function addEnd(last, data) {
if (last == null) return addToEmpty(last, data);
var temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
function addAfter(last, data, item) {
if (last == null) return null;
var temp, p;
p = last.next;
do {
if (p.data == item) {
temp = new Node();
temp.data = data;
temp.next = p.next;
p.next = temp;
if (p == last) last = temp;
return last;
}
p = p.next;
} while (p != last.next);
document.write(item + " not present in the list. <br>");
return last;
}
function traverse(last) {
var p;
if (last == null) {
document.write("List is empty.<br>");
return;
}
p = last.next;
do {
document.write(p.data + " ");
p = p.next;
} while (p != last.next);
}
var last = null;
last = addToEmpty(last, 6);
last = addBegin(last, 4);
last = addBegin(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addAfter(last, 10, 8);
traverse(last);
|
Time Complexity: O(N)
Auxiliary Space: O(1), as we are not using any extra space.
------
Deletion at different positions in a Circular Linked List
tGiven a Circular Linked List. The task is to write programs to delete nodes from this list present at:
- First position.
- Last Position.
- At any given position
.
Deleting first node from Singly Circular Linked List
Examples:
Input : 99->11->22->33->44->55->66
Output : 11->22->33->44->55->66
Input : 11->22->33->44->55->66
Output : 22->33->44->55->66
Deleting First Node from Circular Linked List
Approach:
- Take two pointers current and previous and traverse the list.
- Keep the pointer current fixed pointing to the first node and move previous until it reaches the last node.
- Once, the pointer previous reaches the last node, do the following:
- previous->next = current-> next
- head = previous -> next;
Implementation: Function to delete first node from singly circular linked list.
C++
void DeleteFirst(struct Node** head)
{
struct Node *previous = *head, *firstNode = *head;
if (*head == NULL) {
printf("\nList is empty\n");
return;
}
if (previous->next == previous) {
*head = NULL;
return;
}
while (previous->next != *head) {
previous = previous->next;
}
previous->next = firstNode->next;
*head = previous->next;
free(firstNode);
return;
}
|
Java
static void DeleteFirst(Node head)
{
Node previous = head, firstNode = head;
if (head == null)
{
System.out.printf("\nList is empty\n");
return;
}
if (previous.next == previous)
{
head = null;
return;
}
while (previous.next != head)
{
previous = previous.next;
}
previous.next = firstNode.next;
head = previous.next;
System.gc();
return;
}
|
Python3
def DeleteFirst(head):
previous = head
next = head
if (head == None) :
print("\nList is empty")
return None
if (previous.next == previous) :
head = None
return None
while (previous.next != head):
previous = previous.next
next = previous.next
previous.next = next.next
head = previous.next
return head
|
C#
using System;
public class GFG{
static public
static Node DeleteFirst(Node head)
{
Node previous = head, next = head;
if (head == null)
{
Console.Write("\nList is empty\n");
return null;
}
if (previous.next == previous)
{
head = null;
return null;
}
while (previous.next != head)
{
previous = previous.next;
next = previous.next;
}
previous.next = next.next;
head = previous.next;
return head;
}
c void Main (){
}
|
Javascript
<script>
function DeleteFirst(head)
{
previous = head, firstNode = head;
if (head == null)
{
document.write("<br>List is empty<br>");
return;
}
if (previous.next == previous)
{
head = null;
return;
}
while (previous.next != head)
{
previous = previous.next;
}
previous.next = firstNode.next;
head = previous.next;
return;
}
</script>
|
Time Complexity: O(N), where N is the number of nodes in the Linked List.
Auxiliary Space: O(1)
Deleting the last node of the Circular Linked List
Examples:
Input : 99->11->22->33->44->55->66
Output : 99->11->22->33->44->55
Input : 99->11->22->33->44->55
Output : 99->11->22->33->44
Delete last node from Circular Linked List
Approach:
- Take two pointers current and previous and traverse the list.
- Move both pointers such that next of previous is always pointing to current. Keep moving the pointers current and previous until current reaches the last node and previous is at the second last node.
- Once, the pointer current reaches the last node, do the following:
- previous->next = current-> next
- head = previous -> next;
Function to delete last node from the list:
C++
void DeleteLast(struct Node** head)
{
struct Node *current = *head, *temp = *head, *previous;
if (*head == NULL) {
printf("\nList is empty\n");
return;
}
if (current->next == current) {
*head = NULL;
return;
}
while (current->next != *head) {
previous = current;
current = current->next;
}
previous->next = current->next;
*head = previous->next;
free(current);
return;
}
|
Java
static Node DeleteLast(Node head)
{
Node current = head, temp = head, previous = null;
if (head == null)
{
System.out.printf("\nList is empty\n");
return null;
}
if (current.next == current)
{
head = null;
return null;
}
while (current.next != head)
{
previous = current;
current = current.next;
}
previous.next = current.next;
head = previous.next;
return head;
}
|
Python3
def DeleteLast(head):
current = head
temp = head
previous = None
if (head == None):
print("\nList is empty")
return None
if (current.next == current):
head = None
return None
while (current.next != head):
previous = current
current = current.next
previous.next = current.next
head = previous.next
return head
|
C#
static Node DeleteLast(Node head)
{
Node current = head, temp = head, previous = null;
if (head == null)
{
Console.Write("\nList is empty\n");
return null;
}
if (current.next == current)
{
head = null;
return null;
}
while (current.next != head)
{
previous = current;
current = current.next;
}
previous.next = current.next;
head = previous.next;
return head;
}
|
Javascript
<script>
function DeleteLast(head)
{
let current = head, temp = head, previous = null;
if (head == null)
{
document.write("<br>List is empty<br>");
return null;
}
if (current.next == current)
{
head = null;
return null;
}
while (current.next != head)
{
previous = current;
current = current.next;
}
previous.next = current.next;
head = previous.next;
return head;
}
</script>
|
Time Complexity: O(N) where N is the number of nodes in given Linked List.
Auxiliary Space: O(1)
Deleting nodes at given index in the Circular linked list
Examples:
Input : 99->11->22->33->44->55->66
Index= 4
Output : 99->11->22->33->55->66
Input : 99->11->22->33->44->55->66
Index= 2
Output : 99->11->33->44->55->66
Note: 0-based indexing is considered for the list.
Approach:
- First, find the length of the list. That is, the number of nodes in the list.
- Take two pointers previous and current to traverse the list. Such that previous is one position behind the current node.
- Take a variable count initialized to 0 to keep track of the number of nodes traversed.
- Traverse the list until the given index is reached.
- Once the given index is reached, do previous->next = current->next.
Function to delete a node at given index or location from singly circular linked list:
C++
void DeleteAtPosition(Node* head, int index)
{
int len = Length(head);
int count = 1;
Node* previous = head;
Node* next = head;
if(head == NULL){
cout<<"Delete Last list is empty";
return;
}
if(index >= len || index<0){
cout<<"Index is not Found";
return;
}
if(index == 0){
DeleteFirst(head);
return;
}
while(len > 0){
if(index == count){
previous->next = next->next;
free(next);
return;
}
previous = previous->next;
next = previous->next;
len--;
count++;
}
return;
}
|
C
void DeleteAtPosition(struct Node** head, int index)
{
int len = Length(*head);
int count = 1;
struct Node *previous = *head, *next = *head;
if (*head == NULL) {
printf("\nDelete Last List is empty\n");
return;
}
if (index >= len || index < 0) {
printf("\nIndex is not Found\n");
return;
}
if (index == 0) {
DeleteFirst(head);
return;
}
while (len > 0) {
if (index == count) {
previous->next = next->next;
free(next);
return;
}
previous = previous->next;
next = previous->next;
len--;
count++;
}
return;
}
|
Java
static Node DeleteAtPosition( Node head, int index)
{
int len = Length(head);
int count = 1;
Node previous = head, next = head;
if (head == null)
{
System.out.printf("\nDelete Last List is empty\n");
return null;
}
if (index >= len || index < 0)
{
System.out.printf("\nIndex is not Found\n");
return null;
}
if (index == 0)
{
head = DeleteFirst(head);
return head;
}
while (len > 0)
{
if (index == count)
{
previous.next = next.next;
return head;
}
previous = previous.next;
next = previous.next;
len--;
count++;
}
return head;
}
|
Python3
def DeleteAtPosition(head, index):
len = Length(head)
count = 1
previous = head
next = head
if (head == None):
print("\nDelete Last List is empty")
return None
if (index >= len or index < 0) :
print("\nIndex is not Found")
return None
if (index == 0) :
head = DeleteFirst(head)
return head
while (len > 0):
if (index == count):
previous.next = next.next
return head
previous = previous.next
next = previous.next
len = len - 1
count = count + 1
return head
|
C#
static void DeleteAtPosition(Node head, int index)
{
int len = Length(head);
int count = 1;
Node previous = head;
Node next = head;
if (head == null) {
Console.Write("Delete Last list is empty");
return;
}
if (index >= len || index < 0) {
Console.Write("Index is not Found");
return;
}
if (index == 0) {
DeleteFirst(head);
return;
}
while (len > 0) {
if (index == count) {
previous.next = next.next;
return;
}
previous = previous.next;
next = previous.next;
len -= 1;
count++;
}
}
|
Javascript
<script>
function DeleteAtPosition(head, index){
let len = head.length
let count = 1
let previous = head
let next = head
if (head == null){
document.write("</br>","Delete Last List is empty")
return null
}
if (index >= len || index < 0){
document.write("</br>","Index is not Found")
return null
}
if (index == 0){
head = DeleteFirst(head)
return head
}
while (len > 0){
if (index == count){
previous.next = next.next
return head
}
previous = previous.next
next = previous.next
len = len - 1
count = count + 1
}
return head
}
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Program implementing all of the above three functions
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void Insert(struct Node** head, int data)
{
struct Node* current = *head;
struct Node* newNode = new Node;
if (!newNode) {
printf("\nMemory Error\n");
return;
}
newNode->data = data;
if (*head == NULL) {
newNode->next = newNode;
*head = newNode;
return;
}
else {
while (current->next != *head) {
current = current->next;
}
newNode->next = *head;
current->next = newNode;
}
}
void Display(struct Node* head)
{
struct Node* current = head;
if (head == NULL) {
printf("\nDisplay List is empty\n");
return;
}
else {
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
}
}
int Length(struct Node* head)
{
struct Node* current = head;
int count = 0;
if (head == NULL) {
return 0;
}
else {
do {
current = current->next;
count++;
} while (current != head);
}
return count;
}
void DeleteFirst(struct Node** head)
{
struct Node *previous = *head, *next = *head;
if (*head == NULL) {
printf("\nList is empty\n");
return;
}
if (previous->next == previous) {
*head = NULL;
return;
}
while (previous->next != *head) {
previous = previous->next;
next = previous->next;
}
previous->next = next->next;
*head = previous->next;
free(next);
return;
}
void DeleteLast(struct Node** head)
{
struct Node *current = *head, *temp = *head, *previous;
if (*head == NULL) {
printf("\nList is empty\n");
return;
}
if (current->next == current) {
*head = NULL;
return;
}
while (current->next != *head) {
previous = current;
current = current->next;
}
previous->next = current->next;
*head = previous->next;
free(current);
return;
}
void DeleteAtPosition(struct Node** head, int index)
{
int len = Length(*head);
int count = 1;
struct Node *previous = *head, *next = *head;
if (*head == NULL) {
printf("\nDelete Last List is empty\n");
return;
}
if (index >= len || index < 0) {
printf("\nIndex is not Found\n");
return;
}
if (index == 0) {
DeleteFirst(head);
return;
}
while (len > 0) {
if (index == count) {
previous->next = next->next;
free(next);
return;
}
previous = previous->next;
next = previous->next;
len--;
count++;
}
return;
}
int main()
{
struct Node* head = NULL;
Insert(&head, 99);
Insert(&head, 11);
Insert(&head, 22);
Insert(&head, 33);
Insert(&head, 44);
Insert(&head, 55);
Insert(&head, 66);
printf("Initial List: ");
Display(head);
printf("\nAfter Deleting node at index 4: ");
DeleteAtPosition(&head, 4);
Display(head);
printf("\n\nInitial List: ");
Display(head);
printf("\nAfter Deleting first node: ");
DeleteFirst(&head);
Display(head);
printf("\n\nInitial List: ");
Display(head);
printf("\nAfter Deleting last node: ");
DeleteLast(&head);
Display(head);
return 0;
}
|
Java
import java.util.*;
public class GFG {
static class Node {
int data;
Node next;
};
static Node Insert(Node head, int data){
Node current = head;
Node newNode = new Node();
if (newNode == null) {
System.out.printf("\nMemory Error\n");
return null;
}
newNode.data = data;
if (head == null) {
newNode.next = newNode;
head = newNode;
return head;
} else {
while (current.next != head) {
current = current.next;
}
newNode.next = head;
current.next = newNode;
}
return head;
}
static void Display(Node head){
Node current = head;
if (head == null) {
System.out.printf("\nDisplay List is empty\n");
return;
} else {
do {
System.out.printf("%d ", current.data);
current = current.next;
} while (current != head);
}
}
static int Length(Node head){
Node current = head;
int count = 0;
if (head == null)
return 0;
else {
do {
current = current.next;
count++;
} while (current != head);
}
return count;
}
static Node DeleteFirst(Node head){
Node previous = head, next = head;
if (head == null) {
System.out.printf("\nList is empty\n");
return null;
}
if (previous.next == previous) {
head = null;
return null;
}
while (previous.next != head) {
previous = previous.next;
next = previous.next;
}
previous.next = next.next;
head = previous.next;
return head;
}
static Node DeleteLast(Node head){
Node current = head, temp = head, previous = null;
if (head == null) {
System.out.printf("\nList is empty\n");
return null;
}
if (current.next == current) {
head = null;
return null;
}
while (current.next != head) {
previous = current;
current = current.next;
}
previous.next = current.next;
head = previous.next;
return head;
}
static Node DeleteAtPosition(Node head, int index){
int len = Length(head);
int count = 1;
Node previous = head, next = head;
if (head == null) {
System.out.printf(
"\nDelete Last List is empty\n");
return null;
}
if (index >= len || index < 0) {
System.out.printf("\nIndex is not Found\n");
return null;
}
if (index == 0) {
head = DeleteFirst(head);
return head;
}
while (len > 0) {
if (index == count) {
previous.next = next.next;
return head;
}
previous = previous.next;
next = previous.next;
len--;
count++;
}
return head;
}
public static void main(String args[])
{
Node head = null;
head = Insert(head, 99);
head = Insert(head, 11);
head = Insert(head, 22);
head = Insert(head, 33);
head = Insert(head, 44);
head = Insert(head, 55);
head = Insert(head, 66);
System.out.printf("Initial List: ");
Display(head);
System.out.printf(
"\nAfter Deleting node at index 4: ");
head = DeleteAtPosition(head, 4);
Display(head);
System.out.printf("\n\nInitial List: ");
Display(head);
System.out.printf("\nAfter Deleting first node: ");
head = DeleteFirst(head);
Display(head);
System.out.printf("\n\nInitial List: ");
Display(head);
System.out.printf("\nAfter Deleting last node: ");
head = DeleteLast(head);
Display(head);
}
}
|
Python3
class Node:
def __init__(self, new_data):
self.data = new_data
self.next = None
self.prev = None
def Insert(head, data):
current = head
newNode = Node(0)
if (newNode == None):
print("\nMemory Error\n")
return None
newNode.data = data
if (head == None) :
newNode.next = newNode
head = newNode
return head
else:
while (current.next != head):
current = current.next
newNode.next = head
current.next = newNode
return head
def Display(head):
current = head
if (head == None):
print("\nDisplay List is empty\n")
return
else:
while(True):
print( current.data,end=" ")
current = current.next
if (current == head):
break;
def Length(head):
current = head
count = 0
if (head == None):
return 0
else:
while(True):
current = current.next
count = count + 1
if (current == head):
break;
return count
def DeleteFirst(head):
previous = head
next = head
if (head == None) :
print("\nList is empty")
return None
if (previous.next == previous) :
head = None
return None
while (previous.next != head):
previous = previous.next
next = previous.next
previous.next = next.next
head = previous.next
return head
def DeleteLast(head):
current = head
temp = head
previous = None
if (head == None):
print("\nList is empty")
return None
if (current.next == current) :
head = None
return None
while (current.next != head):
previous = current
current = current.next
previous.next = current.next
head = previous.next
return head
def DeleteAtPosition(head, index):
len = Length(head)
count = 1
previous = head
next = head
if (head == None):
print("\nDelete Last List is empty")
return None
if (index >= len or index < 0) :
print("\nIndex is not Found")
return None
if (index == 0) :
head = DeleteFirst(head)
return head
while (len > 0):
if (index == count):
previous.next = next.next
return head
previous = previous.next
next = previous.next
len = len - 1
count = count + 1
return head
head = None
head = Insert(head, 99)
head = Insert(head, 11)
head = Insert(head, 22)
head = Insert(head, 33)
head = Insert(head, 44)
head = Insert(head, 55)
head = Insert(head, 66)
print("Initial List: ")
Display(head)
print("\nAfter Deleting node at index 4: ")
head = DeleteAtPosition(head, 4)
Display(head)
print("\n\nInitial List: ")
Display(head)
print("\nAfter Deleting first node: ")
head = DeleteFirst(head)
Display(head)
print("\n\nInitial List: ")
Display(head)
print("\nAfter Deleting last node: ")
head = DeleteLast(head)
Display(head)
|
C#
using System;
class GFG
{
class Node
{
public int data;
public Node next;
};
static Node Insert(Node head, int data)
{
Node current = head;
Node newNode = new Node();
if (newNode == null)
{
Console.Write("\nMemory Error\n");
return null;
}
newNode.data = data;
if (head == null)
{
newNode.next = newNode;
head = newNode;
return head;
}
else
{
while (current.next != head)
{
current = current.next;
}
newNode.next = head;
current.next = newNode;
}
return head;
}
static void Display( Node head)
{
Node current = head;
if (head == null)
{
Console.Write("\nDisplay List is empty\n");
return;
}
else
{
do
{
Console.Write("{0} ", current.data);
current = current.next;
} while (current != head);
}
}
static int Length(Node head)
{
Node current = head;
int count = 0;
if (head == null)
{
return 0;
}
else
{
do
{
current = current.next;
count++;
} while (current != head);
}
return count;
}
static Node DeleteFirst(Node head)
{
Node previous = head, next = head;
if (head == null)
{
Console.Write("\nList is empty\n");
return null;
}
if (previous.next == previous)
{
head = null;
return null;
}
while (previous.next != head)
{
previous = previous.next;
next = previous.next;
}
previous.next = next.next;
head = previous.next;
return head;
}
static Node DeleteLast(Node head)
{
Node current = head, temp = head, previous = null;
if (head == null)
{
Console.Write("\nList is empty\n");
return null;
}
if (current.next == current)
{
head = null;
return null;
}
while (current.next != head)
{
previous = current;
current = current.next;
}
previous.next = current.next;
head = previous.next;
return head;
}
static Node DeleteAtPosition( Node head, int index)
{
int len = Length(head);
int count = 1;
Node previous = head, next = head;
if (head == null)
{
Console.Write("\nDelete Last List is empty\n");
return null;
}
if (index >= len || index < 0)
{
Console.Write("\nIndex is not Found\n");
return null;
}
if (index == 0)
{
head = DeleteFirst(head);
return head;
}
while (len > 0)
{
if (index == count)
{
previous.next = next.next;
return head;
}
previous = previous.next;
next = previous.next;
len--;
count++;
}
return head;
}
public static void Main(String []args)
{
Node head = null;
head = Insert(head, 99);
head = Insert(head, 11);
head = Insert(head, 22);
head = Insert(head, 33);
head = Insert(head, 44);
head = Insert(head, 55);
head = Insert(head, 66);
Console.Write("Initial List: ");
Display(head);
Console.Write("\nAfter Deleting node at index 4: ");
head = DeleteAtPosition(head, 4);
Display(head);
Console.Write("\n\nInitial List: ");
Display(head);
Console.Write("\nAfter Deleting first node: ");
head = DeleteFirst(head);
Display(head);
Console.Write("\n\nInitial List: ");
Display(head);
Console.Write("\nAfter Deleting last node: ");
head = DeleteLast(head);
Display(head);
}
}
|
Javascript
<script>
class Node{
constructor(new_data){
this.data = new_data
this.next = null
this.prev = null
}
}
function Insert(head, data){
let current = head
let newNode = new Node(0)
if (newNode == null){
document.write("</br>","Memory Error","</br>")
return null
}
newNode.data = data
if (head == null){
newNode.next = newNode
head = newNode
return head
}
else{
while (current.next != head)
current = current.next
newNode.next = head
current.next = newNode
}
return head
}
function Display(head){
let current = head
if (head == null){
document.write("</br>","Display List is empty","</br>")
return
}
else{
while(true){
document.write( current.data," ")
current = current.next
if (current == head)
break;
}
}
}
function Length(head){
let current = head
let count = 0
if (head == null)
return 0
else{
while(true){
current = current.next
count = count + 1
if (current == head)
break;
}
}
return count
}
function DeleteFirst(head){
let previous = head
let next = head
if (head == null){
document.write("</br>","List is empty")
return null
}
if (previous.next == previous){
head = null
return null
}
while (previous.next != head){
previous = previous.next
next = previous.next
}
previous.next = next.next
head = previous.next
return head
}
function DeleteLast(head){
let current = head
let temp = head
let previous = null
if (head == null){
document.write("</br>","List is empty")
return null
}
if (current.next == current){
head = null
return null
}
while (current.next != head){
previous = current
current = current.next
}
previous.next = current.next
head = previous.next
return head
}
function DeleteAtPosition(head, index){
len = Length(head)
count = 1
previous = head
next = head
if (head == null){
document.write("</br>","Delete Last List is empty")
return null
}
if (index >= len || index < 0) {
document.write("</br>","Index is not Found")
return null
}
if (index == 0){
head = DeleteFirst(head)
return head
}
while (len > 0){
if (index == count){
previous.next = next.next
return head
}
previous = previous.next
next = previous.next
len = len - 1
count = count + 1
}
return head
}
let head = null
head = Insert(head, 99)
head = Insert(head, 11)
head = Insert(head, 22)
head = Insert(head, 33)
head = Insert(head, 44)
head = Insert(head, 55)
head = Insert(head, 66)
document.write("Initial List: ")
Display(head)
document.write("</br>","After Deleting node at index 4: ")
head = DeleteAtPosition(head, 4)
Display(head)
document.write("</br>","</br>","Initial List: ")
Display(head)
document.write("</br>","After Deleting first node: ")
head = DeleteFirst(head)
Display(head)
document.write("</br>","</br>","Initial List: ")
Display(head)
document.write("</br>","After Deleting last node: ")
head = DeleteLast(head)
Display(head)
</script>
|
OutputInitial List: 99 11 22 33 44 55 66
After Deleting node at index 4: 99 11 22 33 55 66
Initial List: 99 11 22 33 55 66
After Deleting first node: 11 22 33 55 66
Initial List: 11 22 33 55 66
After Deleting last node: 11 22 33 55
Time Complexity: O(N) where N is the number of nodes in given linked list.
Auxiliary Space: O(1)
------