Search

Circular Linked List And Algorithm(Data structure)

Circular Linked List



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




Advantage of Circular Linked List:
  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 visitited again.
  2. useful for implementation of queue. we can maintain a pointer to the last inserted node and front can always ne obtained as next of last.
  3. circular linked list are useful inapplication to repeatally go aroung the list. 
  4. circular doubly linked list are used for implementation of advanced data structure likes Fibonacci heap.
  • Insertion in an Empty List

Initially when the list is empty last pointer will be null, After Inserting node at T. After insertion, T is the no, so pointer last pointer to the node T and node T is first and last node. so T is pointing ti itself.

  • Function To insert node in an Empty List:
Struct Node*AddToEmpty(StructNode*Last, int data)
{
//This Function is Only For empty List.
If(last!=Null)
return last;

//Creating a node dyanmically
struct node*last=(struct Node*)malloc(sizeof(struct Node));

// assigning the data
last _> data= data;

//Note: List was Empty.
we link single node.
// To itself.
Last_>Next=Last;
return Last;
}
Run on IDE.

  • Insertion at the begging of the lsit:

To insert at the begining to the list these step are follows:

  1. create a Node T.
  2. Make T_>next = last_>next;
  3. Last_>Next=T
After Insertion

Function to insert node in 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));

//Assinging the Data
temp _>data=data;

//Adjust the Links 
temp _>next = last _>next;
last _>next = Temp;
return last;
}

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

After Insertion:-


Function to insert  node in the end of the List.

struct node* AndEnd(struct node* last, int data);
{
if(last == Null)
returnAddToEmpty(last, data);

// Creating Node dynamically

struct node*temp =(struct node*)malloc(sizeof(struct node));

//Assinging the Data

temp _>data = data;

// Adjust the Links

temp _> Next = last _>next;
last = temp;
return last;
}

Insert in Between the nodes:

To insert a node at the end of the list, follow these steps:
1. Create a node say T.
2. search the node after which T need to be insert, say that node be P.
3. Make T_> next = P _> Next;
4. P _> Next =T
Suppose 12 need to be after Node having value 10.


After Searching & Insertion:

Function to insert node in 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;

// Search the item

do 
{
if (P _>data == item)

{
 temp =(struct node*)malloc (sizeof(struct node));

//Assinging the data 

temp _>data =Data;

//Adjust 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;
}




Post a Comment

0 Comments