search

What is circular link list write an algorithm for insert a node at the front?

2 years ago
Komentar: 113818
Dibaca: 33

Insertion into circular singly linked list at beginning

There are two scenario in which a node can be inserted in circular singly linked list at beginning. Either the node will be inserted in an empty list or the node is to be inserted in an already filled list.

Show

Firstly, allocate the memory space for the new node by using the malloc method of C language.

In the first scenario, the condition head == NULL will be true. Since, the list in which, we are inserting the node is a circular singly linked list, therefore the only node of the list (which is just inserted into the list) will point to itself only. We also need to make the head pointer point to this node. This will be done by using the following statements.

In the second scenario, the condition head == NULL will become false which means that the list contains at least one node. In this case, we need to traverse the list in order to reach the last node of the list. This will be done by using the following statement.

At the end of the loop, the pointer temp would point to the last node of the list. Since, in a circular singly linked list, the last node of the list contains a pointer to the first node of the list. Therefore, we need to make the next pointer of the last node point to the head node of the list and the new node which is being inserted into the list will be the new head node of the list therefore the next pointer of temp will point to the new node ptr.

This will be done by using the following statements.

the next pointer of temp will point to the existing head node of the list.

Now, make the new node ptr, the new head node of the circular singly linked list.

in this way, the node ptr has been inserted into the circular singly linked list at beginning.

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? 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 next 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.
The structure thus formed is a circular singly linked list and looks like this:

What is circular link list write an algorithm for insert a node at the front?

In this post, the implementation and insertion of a node in a Circular Linked List using a singly linked list are explained.

Implementation
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.



What is circular link list write an algorithm for insert a node at the front?

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

What is circular link list write an algorithm for insert a node at the front?

After inserting node T,

What is circular link list write an algorithm for insert a node at the front?

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.
Function to insert a node into an empty list,




struct Node *addToEmpty(struct Node *last, int data)
{
// This function is only for empty list
if (last != NULL)
return last;
// Creating a node dynamically.
struct Node *temp =
(struct Node*)malloc(sizeof(struct Node));
// Assigning the data.
temp -> data = data;
last = temp;
// Note : list was empty. We link single node
// to itself.
temp -> next = last;
return last;
}




static Node addToEmpty(Node last, int data)
{
// This function is only for empty list
if (last != null)
return last;
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Note : list was empty. We link single node
// to itself.
temp.next = last;
return last;
}
// This code is contributed by gauravrajput1




# This function is only for empty list
def addToEmpty(self, data):
if (self.last != None):
return self.last
# Creating the newnode temp
temp = Node(data)
self.last = temp
# Creating the link
self.last.next = self.last
return self.last
# this code is contributed by shivanisinghss2110




static Node addToEmpty(Node last, int data)
{
// This function is only for empty list
if (last != null)
return last;
// Creating a node dynamically.
Node temp =
new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Note : list was empty. We link single node
// to itself.
temp.next = last;
return last;
}
// This code contributed by umadevi9616




<script>
function addToEmpty(last , data)
{
// This function is only for empty list
if (last != null)
return last;
// Creating a node dynamically.
var temp = new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Note : list was empty. We link single node
// to itself.
temp.next = last;
return last;
}
// This code contributed by umadevi9616
</script>


Insertion at the beginning of the list
To insert a node at the beginning of the list, follow these steps:
1. Create a node, say T.
2. Make T -> next = last -> next.
3. last -> next = T.

What is circular link list write an algorithm for insert a node at the front?

After insertion,

What is circular link list write an algorithm for insert a node at the front?

Function to insert nodes at the beginning of the list,




struct Node *addBegin(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
// Creating a node dynamically.
struct Node *temp
= (struct Node *)malloc(sizeof(struct Node));
// Assigning the data.
temp -> data = data;
// Adjusting the links.
temp -> next = last -> next;
last -> next = temp;
return last;
}




static Node addBegin(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
// Creating a node dynamically
Node temp = new Node();
// Assigning the data
temp.data = data;
// Adjusting the links
temp.next = last.next;
last.next = temp;
return last;
}
// This code is contributed by rutvik_56




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
# this code is contributed by shivanisinghss2110




static Node addBegin(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
// Creating a node dynamically
Node temp = new Node();
// Assigning the data
temp.data = data;
// Adjusting the links
temp.next = last.next;
last.next = temp;
return last;
}
// This code is contributed by Pratham76




<script>
function addBegin(last , data)
{
if (last == null)
return addToEmpty(last, data);
// Creating a node dynamically.
var temp = new Node();
// Assigning the data.
temp.data = data;
// Adjusting the links.
temp.next = last.next;
last.next = temp;
return last;
}
// This code contributed by Shivani
</script>


Insertion at the end of the list
To insert a node at the end of the list, follow these steps:
1. Create a node, say T.
2. Make T -> next = last -> next;
3. last -> next = T.
4. last = T.

What is circular link list write an algorithm for insert a node at the front?

After insertion,

What is circular link list write an algorithm for insert a node at the front?

Function to insert a node at the end of the List




struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
// Creating a node dynamically.
struct Node *temp =
(struct Node *)malloc(sizeof(struct Node));
// Assigning the data.
temp -> data = data;
// Adjusting the links.
temp -> next = last -> next;
last -> next = temp;
last = temp;
return last;
}




static Node addEnd(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
// Adjusting the links.
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
// This code is contributed by shivanisinghss2110




def addEnd(self, data):
if (self.last == None):
return self.addToEmpty(data)
# Assigning the data.
temp = Node(data)
# Adjusting the links.
temp.next = self.last.next
self.last.next = temp
self.last = temp
return self.last
# This code is contributed by shivanisinghss2110




static Node addEnd(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
// Adjusting the links.
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
// This code is contributed by shivanisinghss2110




<script>
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;
}
// this code is contributed by shivanisinghss2110
</script>


Insertion in between the nodes
To insert a node in between the two nodes, follow these steps:
1. Create a node, say T.
2. Search for the node after which T needs to be inserted, say that node is P.
3. Make T -> next = P -> next;
4. P -> next = T.
Suppose 12 needs to be inserted after the node has the value 10,

What is circular link list write an algorithm for insert a node at the front?

After searching and insertion,

What is circular link list write an algorithm for insert a node at the front?

Function to insert a node at the end of the List,




struct Node *addAfter(struct Node *last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *p;
p = last -> next;
// Searching the item.
do
{
if (p ->data == item)
{
// Creating a node dynamically.
temp = (struct Node *)malloc(sizeof(struct Node));
// Assigning the data.
temp -> data = data;
// Adjusting the links.
temp -> next = p -> next;
// Adding newly allocated node after p.
p -> next = temp;
// Checking for the last node.
if (p == last)
last = temp;
return last;
}
p = p -> next;
} while (p != last -> next);
cout << item << " not present in the list." << endl;
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;
}
// This code is contributed by shivanisinghss2110




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
# This code is contributed by shivanisinghss2110




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;
}
// This code is contributed by shivanisinghss2110




<script>
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;
}
// This code is contributed by shivanisinghss2110
</script>

The following is a complete program that uses all of the above methods to create a circular singly linked list.




#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node *next;
};
struct Node *addToEmpty(struct Node *last, int data)
{
// This function is only for empty list
if (last != NULL)
return last;
// Creating a node dynamically.
struct Node *temp =
(struct Node*)malloc(sizeof(struct Node));
// Assigning the data.
temp -> data = data;
last = temp;
// Creating the link.
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 list is empty, return.
if (last == NULL)
{
cout << "List is empty." << endl;
return;
}
// Pointing to first Node of the list.
p = last -> next;
// Traversing the list.
do
{
cout << p -> data << " ";
p = p -> next;
}
while(p != last->next);
}
// Driven Program
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;
}




class GFG
{
static class Node
{
int data;
Node next;
};
static Node addToEmpty(Node last, int data)
{
// This function is only for empty list
if (last != null)
return last;
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Creating the link.
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 list is empty, return.
if (last == null)
{
System.out.println("List is empty.");
return;
}
// Pointing to first Node of the list.
p = last.next;
// Traversing the list.
do
{
System.out.print(p.data + " ");
p = p.next;
}
while(p != last.next);
}
// Driven code
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);
}
}
/* This code contributed by PrinciRaj1992 */




class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.last = None
# This function is only for empty list
def addToEmpty(self, data):
if (self.last != None):
return self.last
# Creating the newnode temp
temp = Node(data)
self.last = temp
# Creating the link
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
# Driver Code
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()
# This code is contributed by
# Aditya Singh




using System;
public class GFG
{
public class Node
{
public int data;
public Node next;
};
static Node addToEmpty(Node last, int data)
{
// This function is only for empty list
if (last != null)
return last;
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Creating the link.
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 list is empty, return.
if (last == null)
{
Console.WriteLine("List is empty.");
return;
}
// Pointing to first Node of the list.
p = last.next;
// Traversing the list.
do
{
Console.Write(p.data + " ");
p = p.next;
}
while(p != last.next);
}
// Driven code
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);
}
}
// This code contributed by Rajput-Ji




<script>
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
function addToEmpty(last, data) {
// This function is only for empty list
if (last != null) return last;
// Creating a node dynamically.
var temp = new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Creating the link.
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 list is empty, return.
if (last == null) {
document.write("List is empty.<br>");
return;
}
// Pointing to first Node of the list.
p = last.next;
// Traversing the list.
do {
document.write(p.data + " ");
p = p.next;
} while (p != last.next);
}
// Driven code
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);
</script>

Output:

2 4 6 8 10 12

This article is contributed by Anuj Chauhan. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

What is circular link list write an algorithm for insert a node at the front?




Article Tags :
Linked List
circular linked list
Practice Tags :
Linked List
circular linked list
Read Full Article

Circular Linked List | Set 1 (Introduction and Applications)

We have discussed singly and doubly linked lists in the following posts.

Introduction to Linked List & Insertion
Doubly Linked List Introduction and Insertion

Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.

What is circular link list write an algorithm for insert a node at the front?

Advantages of Circular Linked Lists:
1) Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.



2) Useful for implementation of queue. Unlike this implementation, we don’t need to maintain two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted node and front can always be obtained as next of last.

3) Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.

4) Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.

Next Posts :
Circular Linked List | Set 2 (Traversal)
Circular Singly Linked List | Insertion

Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem

What is circular link list write an algorithm for insert a node at the front?

Article Tags :
Linked List
circular linked list
Practice Tags :
Linked List
circular linked list
Read Full Article

Insertion In Circular Linked List

There are three situation for inserting element in Circular linked list.
1.Insertion at the front of Circular linked list.
2.Insertion in the middle of the Circular linked list.
3.Insertion at the end of the Circular linked list.



Circular Linked List

In this article, you will learn what circular linked list is and its types with implementation.

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 are basically two types of circular linked list:

1. Circular Singly Linked List

Here, the address of the last node consists of the address of the first node.

What is circular link list write an algorithm for insert a node at the front?
Circular Linked List Representation

2. Circular Doubly Linked List

Here, in addition to the last node storing the address of the first node, the first node will also store the address of the last node.

What is circular link list write an algorithm for insert a node at the front?
Circular Doubly Linked List Representation

Note: We will be using the singly circular linked list to represent the working of circular linked list.

Circular Linked List

Circular Linked List is little more complicated linked data structure. In the circular linked list we can insert elements anywhere in the list whereas in the array we cannot insert element anywhere in the list because it is in the contiguous memory. In the circular linked list the previous element stores the address of the next element and the last element stores the address of the starting element. The elements points to each other in a circular way which forms a circular chain. The circular linked list has a dynamic size which means the memory can be allocated when it is required.

What is circular link list write an algorithm for insert a node at the front?

Application of Circular Linked List

  • The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed.
  • Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player's chance ends.
  • Circular Linked List can also be used to create Circular Queue. In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one pointer is required.

Implementing Circular Linked List

Implementing a circular linked list is very easy and almost similar to linear linked list implementation, with the only difference being that, in circular linked list the last Node will have it's next point to the Head of the List. In Linear linked list the last Node simply holds NULL in it's next pointer.

So this will be oue Node class, as we have already studied in the lesson, it will be used to form the List.

class Node { public: int data; //pointer to the next node node* next; node() { data = 0; next = NULL; } node(int x) { data = x; next = NULL; } }

Circular Linked List

Circular Linked List class will be almost same as the Linked List class that we studied in the previous lesson, with a few difference in the implementation of class methods.

class CircularLinkedList { public: node *head; //declaring the functions //function to add Node at front int addAtFront(node *n); //function to check whether Linked list is empty int isEmpty(); //function to add Node at the End of list int addAtEnd(node *n); //function to search a value node* search(int k); //function to delete any Node node* deleteNode(int x); CircularLinkedList() { head = NULL; } }

Insertion at the Beginning

Steps to insert a Node at beginning :

  1. The first Node is the Head for any Linked List.
  2. When a new Linked List is instantiated, it just has the Head, which is Null.
  3. Else, the Head holds the pointer to the fisrt Node of the List.
  4. When we want to add any Node at the front, we must make the head point to it.
  5. And the Next pointer of the newly added Node, must point to the previous Head, whether it be NULL(in case of new List) or the pointer to the first Node of the List.
  6. The previous Head Node is now the second Node of Linked List, because the new Node is added at the front.
int CircularLinkedList :: addAtFront(node *n) { int i = 0; /* If the list is empty */ if(head == NULL) { n->next = head; //making the new Node as Head head = n; i++; } else { n->next = head; //get the Last Node and make its next point to new Node Node* last = getLastNode(); last->next = n; //also make the head point to the new first Node head = n; i++; } //returning the position where Node is added return i; }

Insertion at the End

Steps to insert a Node at the end :

  1. If the Linked List is empty then we simply, add the new Node as the Head of the Linked List.
  2. If the Linked List is not empty then we find the last node, and make it' next to the new Node, and make the next of the Newly added Node point to the Head of the List.
int CircularLinkedList :: addAtEnd(node *n) { //If list is empty if(head == NULL) { //making the new Node as Head head = n; //making the next pointer of the new Node as Null n->next = NULL; } else { //getting the last node node *last = getLastNode(); last->next = n; //making the next pointer of new node point to head n->next = head; } }

Searching for an Element in the List

In searhing we do not have to do much, we just need to traverse like we did while getting the last node, in this case we will also compare the data of the Node. If we get the Node with the same data, we will return it, otherwise we will make our pointer point the next Node, and so on.

node* CircularLinkedList :: search(int x) { node *ptr = head; while(ptr != NULL && ptr->data != x) { //until we reach the end or we find a Node with data x, we keep moving ptr = ptr->next; } return ptr; }

Deleting a Node from the List

Deleting a node can be done in many ways, like we first search the Node with data which we want to delete and then we delete it. In our approach, we will define a method which will take the data to be deleted as argument, will use the search method to locate it and will then remove the Node from the List.

To remove any Node from the list, we need to do the following :

  • If the Node to be deleted is the first node, then simply set the Next pointer of the Head to point to the next element from the Node to be deleted. And update the next pointer of the Last Node as well.
  • If the Node is in the middle somewhere, then find the Node before it, and make the Node before it point to the Node next to it.
  • If the Node is at the end, then remove it and make the new last node point to the head.
node* CircularLinkedList :: deleteNode(int x) { //searching the Node with data x node *n = search(x); node *ptr = head; if(ptr == NULL) { cout << "List is empty"; return NULL; } else if(ptr == n) { ptr->next = n->next; return n; } else { while(ptr->next != n) { ptr = ptr->next; } ptr->next = n->next; return n; } }
  • ← Prev
  • Next →

Inserting a node at the beginning of a linked list

The new node will be added at the beginning of a linked list.


Example

Assume that the linked list has elements: 20 30 40 NULL

If we insert 100, it will be added at the beginning of a linked list.

After insertion, the new linked list will be

100 20 30 40 NULL



Top List List Công Nghệ Lg

Pos Terkait

Alat yang mengubah aliran angin menjadi energi listrik adalah
Alat yang mengubah aliran angin menjadi energi listrik adalah

Bagaimana tenaga angin dapat diubah menjadi energi listrik brainly?
Bagaimana tenaga angin dapat diubah menjadi energi listrik brainly?

Contoh interaksi antar muatan listrik dalam kehidupan sehari-hari
Contoh interaksi antar muatan listrik dalam kehidupan sehari-hari

Apa itu rangkaian kelistrikan?
Apa itu rangkaian kelistrikan?

State one similarity and one difference between list and tuples
State one similarity and one difference between list and tuples

Dimanakah kita dapat mengukur tegangan listrik pada tubuh kita mengapa demikian
Dimanakah kita dapat mengukur tegangan listrik pada tubuh kita mengapa demikian

Di bawah ini yang merupakan sumber arus listrik ac adalah
Di bawah ini yang merupakan sumber arus listrik ac adalah

Topologi jaringan nirkabel yang memungkinkan adanya lebih dari satu Access Point adalah
Topologi jaringan nirkabel yang memungkinkan adanya lebih dari satu Access Point adalah

Convert Binary search Tree to sorted Doubly Linked List geeksforgeeks
Convert Binary search Tree to sorted Doubly Linked List geeksforgeeks

Alat apa saja yang menggunakan rangkaian listrik paralel?
Alat apa saja yang menggunakan rangkaian listrik paralel?

Periklanan

BERITA TERKINI

Bisakah Anda mengaktifkan javascript di ponsel?
1 years ago . by AdorableMantra
Bagaimana Anda menghapus teks duplikat dengan python?
1 years ago . by DecreasingEmperor
Cara menghapus latar belakang video di CapCut
1 years ago . by SkepticalDugout
Apa itu rounddown dalam excel?
1 years ago . by JollyDollar
Dapatkan array multidimensi kunci php
1 years ago . by LuridRecognition
Cara mengeluarkan darah haid yang tidak keluar
1 years ago . by CuriousRedundancy
Dapatkan javascript bulan dengan 0
1 years ago . by NastyMedics
Python cetak daftar daftar secara vertikal
1 years ago . by DeviantColors
Cara membersihkan kacamata yang tergores
1 years ago . by Two-storyDealing
Cara menggunakan variable to dataframe python
1 years ago . by ThrobbingMetaphysics

Toplist Popular

#1
Top 10 berikut ini yang bukan merupakan penetapan tujuan visi perusahaan adalah 2022
1 years ago
#2
Top 10 sebuah bak air berbentuk balok dengan ukuran panjang 40 cm, lebar 30 cm, dan tinggi 35 cm 2022
1 years ago
#3
Top 9 banjir bukan sekadar bencana alam paragraf 3 gagasan utama 2022
1 years ago
#4
Top 10 diketahui himpunan himpunan sebagai berikut p bilangan ganjil yang kurang dari 15 2022
1 years ago
#5
Top 10 penyelesaian dari persamaan 3x 2 y 9 dan 2x y 3 adalah 2022
1 years ago
#6
Top 10 bagaimana cara memberi salam kepada orang tua dan guru yang benar brainly 2022
1 years ago
#7
Top 10 semakin tinggi nilai toleransi semakin tinggi nilai integrasi nasional 2022
1 years ago
#8
Top 10 benda kerajinan tidak boleh membahayakan pemakainya maka benda kerajinan memiliki prinsip 2022
1 years ago
#9
Top 9 bagian tutup sumbat termos biasanya terbuat dari benda berjenis brainly 2022
1 years ago
#10
Top 9 pernyataan yang sesuai dengan prinsipteori evolusi jb lamarck ditunjukkan oleh angka 2022
1 years ago

Periklanan

Terpopuler

Token Data

Periklanan

Tentang Kami

Legal

Dukungan

Social

homeenfritzhtrjako
Copyright © 2024 idkuu.com Inc.