logo

TechCodeview

Introduktion till Circular Linked List

Vad är cirkulär länkad lista?

De cirkulär länkad lista är en länkad lista där alla noder är sammankopplade för att bilda en cirkel. I en cirkulär länkad lista är den första noden och den sista noden kopplade till varandra som bildar en cirkel. Det finns ingen NULL i slutet.

Cirkulär länkad lista



Det finns i allmänhet två typer av cirkulärt länkade listor:

  • Cirkulär enkellänkad lista: I en cirkulär enkellänkad lista innehåller den sista noden i listan en pekare till listans första nod. Vi korsar den cirkulära enkellänkade listan tills vi når samma nod där vi började. Den cirkulära enkellänkade listan har ingen början eller slut. Inget nollvärde finns i nästa del av någon av noderna.

Representation av cirkulär enstaka länkad lista

  • Cirkulär dubbellänkad lista: Cirkulär dubbellänkad lista har egenskaper för både dubbellänkad lista och cirkulär länkad lista där två på varandra följande element är länkade eller sammankopplade av föregående och nästa pekare och den sista noden pekar på den första noden med nästa pekare och även den första noden pekar på den sista noden av föregående pekare.

Representation av cirkulär dubbelt länkad lista



Notera: Vi kommer att använda den cirkulärt länkade listan för att representera hur den cirkulärt länkade listan fungerar.

företag vs företag

Representation av cirkulär länkad lista:

Cirkulära länkade listor liknar enstaka länkade listor med undantag för att ansluta den sista noden till den första noden.

Nodrepresentation av en cirkulär länkad lista:



C++ 
// Class Node, similar to the linked list class Node{  int value; // Points to the next node.  Node next; }>
C 
struct Node {  int data;  struct Node *next; };>
Java 
public class Node {  int data;  Node next;    public Node(int data) {  this.data = data;  this.next = null;  } }>
C# 
public class Node {  public int data;  public Node next;    public Node(int data)  {  this.data = data;  this.next = null;  } }>
Javascript 
class Node {  constructor(data) {  this.data = data;  this.next = null;  } }>
PHP 
class Node {  public $data;  public $next;  function __construct($data) {  $this->data = $data;  $this->next = null;  } }>
Python3 
# Class Node, similar to the linked list class Node: def __init__(self,data): self.data = data self.next = None>

Exempel på cirkulär enkellänkad lista:

Exempel på cirkulär länkad lista

java-arrayer

Ovanstående cirkulära enkellänkade lista kan representeras som:

C++ 
// Initialize the Nodes. Node one = new Node(3); Node two = new Node(5); Node three = new Node(9); // Connect nodes one.next = two; two.next = three; three.next = one;>
C 
Node* one = createNode(3); Node* two = createNode(5); Node* three = createNode(9); // Connect nodes one->nästa = två; två->nästa = tre; tre->nästa = en;>
Java 
// Define the Node class class Node {  int value;  Node next;  public Node(int value) {  this.value = value;  } } // Initialize the Nodes. Node one = new Node(3); Node two = new Node(5); Node three = new Node(9); // Connect nodes one.next = two; two.next = three; three.next = one;>
C# 
Node one = new Node(3); Node two = new Node(5); Node three = new Node(9); // Connect nodes one.next = two; two.next = three; three.next = one;>
Javascript 
let one = new Node(3); let two = new Node(5); let three = new Node(9); // Connect nodes one.next = two; two.next = three; three.next = one;>
PHP 
$one = new Node(3); $two = new Node(5); $three = new Node(9); // Connect nodes $one->nästa = $två; $två->nästa = $tre; $three->next = $one;>
Python3 
# Initialize the Nodes. one = Node(3) two = Node(5) three = Node(9) # Connect nodes one.next = two two.next = three three.next = one>

Förklaring: I ovanstående program är ett, två och tre noden med värdena 3, 5 respektive 9 som är sammankopplade på ett cirkulärt sätt som:

  • För Nod One: Next-pekaren lagrar adressen till Nod två.
  • För nod två: The Next lagrar adressen till nod tre
  • För nod tre: De Nästa pekar på nod ett.

Operationer på den cirkulära länkade listan:

Vi kan göra några operationer på den cirkulära länkade listan som liknar den enkellänkade listan som är:

  1. Införande
  2. Radering

1. Infogning i den cirkulära länkade listan:

En nod kan läggas till på tre sätt:

  1. Infogning i början av listan
  2. Infogning i slutet av listan
  3. Insättning mellan noderna

1) Infoga i början av listan: För att infoga en nod i början av listan, följ dessa steg:

  • Skapa en nod, säg T.
  • Gör T -> nästa = sist -> nästa.
  • sista -> nästa = T.

Cirkulär länkad lista före insättning

Och då,

Cirkulär länkad lista efter insättning

2) Infoga i slutet av listan: För att infoga en nod i slutet av listan, följ dessa steg:

  • Skapa en nod, säg T.
  • Gör T -> nästa = sist -> nästa;
  • sista -> nästa = T.
  • sista = T.

Innan insättning,

Cirkulär länkad lista före infogning av nod i slutet

java öppna en fil

Efter införandet,

d flip flop

Cirkulär länkad lista efter infogning av nod i slutet

3) Infogning mellan noderna: För att infoga en nod mellan de två noderna, följ dessa steg:

  • Skapa en nod, säg T.
  • Sök efter noden efter vilken T behöver infogas, säg att noden är P.
  • Gör T -> nästa = P -> nästa;
  • P -> nästa = T.

Antag att 12 måste infogas efter att noden har värdet 10,

Cirkulär länkad lista före insättning

Efter sökning och infogning,

Cirkulär länkad lista efter insättning

2. Radering i en cirkulär länkad lista:

1) Ta bort noden endast om det är den enda noden i den cirkulärt länkade listan:

  • Frigör nodens minne
  • Det sista värdet ska vara NULL. En nod pekar alltid på en annan nod, så NULL-tilldelning är inte nödvändig.
    Vilken nod som helst kan ställas in som startpunkt.
    Noder korsas snabbt från den första till den sista.

2) Radering av den sista noden:

  • Lokalisera noden före den sista noden (låt det vara temp)
  • Håll adressen till noden bredvid den sista noden i temp
  • Radera det sista minnet
  • Sätt temp i slutet

3) Ta bort valfri nod från den cirkulärt länkade listan: Vi kommer att få en nod och vår uppgift är att ta bort den noden från den cirkulärt länkade listan.

Algoritm:
Fall 1 : Listan är tom.

  • Om listan är tom återkommer vi helt enkelt.

Fall 2 : Listan är inte tom

  • Om listan inte är tom definierar vi två pekare curr och föregående och initiera pekaren curr med huvud nod.
  • Gå igenom listan med curr för att hitta noden som ska raderas och innan du går till curr till nästa nod, varje gång set prev = curr.
  • Om noden hittas, kontrollera om det är den enda noden i listan. Om ja, ställ in head = NULL och free(curr).
  • Om listan har mer än en nod, kontrollera om det är den första noden i listan. Villkor för att kontrollera detta (curr == huvud). Om ja, flytta prev tills den når den sista noden. Efter att prev når den sista noden, ställ in head = head -> next och prev -> next = head. Ta bort curr.
  • Om curr inte är den första noden kontrollerar vi om det är den sista noden i listan. Villkor för att kontrollera detta är (curr -> nästa == huvud).
  • Om curr är den sista noden. Ställ in prev -> next = head och ta bort noden curr med free(curr).
  • Om noden som ska raderas varken är den första noden eller den sista noden, ställ in prev -> next = curr -> next och ta bort curr.
  • Om noden inte finns i listan returnera huvudet och gör ingenting.

Nedan är implementeringen av ovanstående tillvägagångssätt:

java till json-objekt
C++ 
// C++ program to delete a given key from // linked list. #include  using namespace std; // Structure for a node class Node { public:  int data;  Node* next; }; // Function to insert a node at the // beginning of a Circular linked list void push(Node** head_ref, int data) {  // Create a new node and make head  // as next of it.  Node* ptr1 = new Node();  ptr1->data = data;  ptr1->next = *head_ref;  // Om den länkade listan inte är NULL så // ställ in nästa av sista nod if (*head_ref != NULL) { // Hitta noden före head och // uppdatera nästa av den.  Nod* temp = *head_ref;  while (temp->next != *head_ref) temp = temp->next;  temp->nästa = ptr1;  } else // För den första noden ptr1->next = ptr1;  *huvud_ref = ptr1; } // Funktion för att skriva ut noder i en given // cirkulär länkad lista void printList(Node* head) { Node* temp = head;  if (huvud != NULL) { gör { cout<< temp->data<< ' ';  temp = temp->Nästa;  } while (temp != huvud);  } cout<< endl; } // Function to delete a given node // from the list void deleteNode(Node** head, int key) {  // If linked list is empty  if (*head == NULL)  return;  // If the list contains only a  // single node  if ((*head)->data == nyckel && (*huvud)->nästa == *huvud) { free(*huvud);  *huvud = NULL;  lämna tillbaka;  } Nod *last = *huvud, *d;  // Om huvud ska raderas om ((*huvud)->data == nyckel) { // Hitta den sista noden i listan medan (last->next != *head) last = last->next;  // Peka sista noden till nästa av // huvud dvs. den andra noden // i listan last->next = (*head)->next;  free(*huvud);  *huvud = sista->nästa;  lämna tillbaka;  } // Antingen hittas den nod som ska tas bort // inte eller slutet av listan // nås inte medan (last->next != *head && last->next->data != key) { last = last ->nästa;  } // Om nod som ska raderas hittades if (last->next->data == key) { d = last->next;  sista->nästa = d->nästa;  befriad);  } annat cout<< 'Given node is not found in the list!!!
'; } // Driver code int main() {  // Initialize lists as empty  Node* head = NULL;  // Created linked list will be  // 2->5->7->8->10 push(&head, 2);  push(&huvud, 5);  push(&head, 7);  push(&head, 8);  push(&head, 10);  cout<< 'List Before Deletion: ';  printList(head);  deleteNode(&head, 7);  cout << 'List After Deletion: ';  printList(head);  return 0; }>
C 
#include  #include  // Structure for a node struct Node {  int data;  struct Node* next; }; // Function to insert a node at the // beginning of a Circular linked list void push(struct Node** head_ref, int data) {  // Create a new node and make head  // as next of it.  struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));  ptr1->data = data;  ptr1->next = *head_ref;  // Om den länkade listan inte är NULL så // ställ in nästa av sista nod if (*head_ref != NULL) { // Hitta noden före head och // uppdatera nästa av den.  struct Node* temp = *head_ref;  while (temp->next != *head_ref) temp = temp->next;  temp->nästa = ptr1;  } else // För den första noden ptr1->next = ptr1;  *huvud_ref = ptr1; } // Funktion för att skriva ut noder i en given // cirkulär länkad lista void printList(struct Node* head) { struct Node* temp = head;  if (huvud != NULL) { gör { printf('%d ', temp->data);  temp = temp->nästa;  } while (temp != huvud);  } printf('
'); } // Funktion för att ta bort en given nod // från listan void deleteNode(struct Node** head, int key) { // Om den länkade listan är tom om (*head == NULL) returnerar;  // Om listan endast innehåller en // enkel nod om ((*huvud)->data == nyckel && (*huvud)->nästa == *huvud) { free(*huvud);  *huvud = NULL;  lämna tillbaka;  } struct Node *last = *huvud, *d;  // Om huvud ska raderas om ((*huvud)->data == nyckel) { // Hitta den sista noden i listan medan (last->next != *head) last = last->next;  // Peka sista noden till nästa av // huvud dvs. den andra noden // i listan last->next = (*head)->next;  free(*huvud);  *huvud = sista->nästa;  lämna tillbaka;  } // Antingen hittas den nod som ska tas bort // inte eller slutet av listan // nås inte medan (last->next != *head && last->next->data != key) { last = last ->nästa;  } // Om nod som ska raderas hittades if (last->next->data == key) { d = last->next;  sista->nästa = d->nästa;  befriad);  } else printf('Given nod finns inte i listan!!!
'); } // Drivrutinskod int main() { // Initiera listor som tom struct Node* head = NULL;  // Skapat länkad lista kommer att vara // 2->5->7->8->10 push(&head, 2);  push(&huvud, 5);  push(&huvud, 7);  push(&huvud, 8);  push(&head, 10);  printf('Lista före radering: ');  printList(huvud);  deleteNode(&head, 7);  printf('Lista efter radering: ');  printList(huvud);  returnera 0; }>
Java 
// Java program to delete a given key from // linked list. import java.io.*; import java.util.*; public class GFG {  /* structure for a node */  static class Node {  int data;  Node next;  };  /* Function to insert a node at the beginning of a Circular linked list */  static Node push(Node head_ref, int data)  {  // Create a new node and make head as next  // of it.  Node ptr1 = new Node();  ptr1.data = data;  ptr1.next = head_ref;  /* If linked list is not null then set the next of last node */  if (head_ref != null) {  // Find the node before head and update  // next of it.  Node temp = head_ref;  while (temp.next != head_ref)  temp = temp.next;  temp.next = ptr1;  }  else  ptr1.next = ptr1; /*For the first node */  head_ref = ptr1;  return head_ref;  }  /* Function to print nodes in a given circular linked list */  static void printList(Node head)  {  Node temp = head;  if (head != null) {  do {  System.out.printf('%d ', temp.data);  temp = temp.next;  } while (temp != head);  }  System.out.printf('
');  }  /* Function to delete a given node from the list */  static Node deleteNode(Node head, int key)  {  if (head == null)  return null;  int flag = 0;  // Find the required node  Node curr = head, prev = new Node();  while (curr.data != key) {  if (curr.next == head) {  System.out.printf(  'Given node is not found in the list!!!
');  flag = 1;  break;  }  prev = curr;  curr = curr.next;  }  // Check if the element is not present in the list  if (flag == 1)  return head;  // Check if node is only node  if (curr == head && curr.next == head) {  head = null;  return head;  }  // If more than one node, check if  // it is first node  if (curr == head) {  prev = head;  while (prev.next != head)  prev = prev.next;  head = curr.next;  prev.next = head;  }  // check if node is last node  else if (curr.next == head) {  prev.next = head;  }  else {  prev.next = curr.next;  }  return head;  }  /* Driver code */  public static void main(String args[])  {  /* Initialize lists as empty */  Node head = null;  /* Created linked list will be 2.5.7.8.10 */  head = push(head, 2);  head = push(head, 5);  head = push(head, 7);  head = push(head, 8);  head = push(head, 10);  System.out.printf('List Before Deletion: ');  printList(head);  head = deleteNode(head, 7);  System.out.printf('List After Deletion: ');  printList(head);  } } // This code is contributed by Susobhan Akhuli>
C# 
using System; // Structure for a node public class Node {  public int data;  public Node next; } // Class for Circular Linked List public class CircularLinkedList {  // Function to insert a node at the  // beginning of a Circular linked list  public static void Push(ref Node head_ref, int data)  {  // Create a new node and make head  // as next of it.  Node ptr1 = new Node();  ptr1.data = data;  ptr1.next = head_ref;  // If linked list is not NULL then  // set the next of last node  if (head_ref != null) {  // Find the node before head and  // update next of it.  Node temp = head_ref;  while (temp.next != head_ref)  temp = temp.next;  temp.next = ptr1;  }  else  // For the first node  ptr1.next = ptr1;  head_ref = ptr1;  }  // Function to print nodes in a given  // circular linked list  public static void PrintList(Node head)  {  Node temp = head;  if (head != null) {  do {  Console.Write(temp.data + ' ');  temp = temp.next;  } while (temp != head);  }  Console.WriteLine();  }  // Function to delete a given node  // from the list  public static void DeleteNode(ref Node head, int key)  {  // If linked list is empty  if (head == null)  return;  // If the list contains only a  // single node  if (head.data == key && head.next == head) {  head = null;  return;  }  Node last = head, d;  // If head is to be deleted  if (head.data == key) {  // Find the last node of the list  while (last.next != head)  last = last.next;  // Point last node to the next of  // head i.e. the second node  // of the list  last.next = head.next;  head = last.next;  return;  }  // Either the node to be deleted is  // not found or the end of list  // is not reached  while (last.next != head && last.next.data != key) {  last = last.next;  }  // If node to be deleted was found  if (last.next.data == key) {  d = last.next;  last.next = d.next;  }  else  Console.WriteLine(  'Given node is not found in the list!!!');  }  // Driver code  public static void Main()  {  // Initialize lists as empty  Node head = null;  // Created linked list will be  // 2->5->7->8->10 Push(ref head, 2);  Push (ref huvud, 5);  Push(ref huvud, 7);  Push(ref head, 8);  Push(ref huvud, 10);  Console.Write('Lista före radering: ');  PrintList(huvud);  DeleteNode(ref head, 7);  Console.Write('Lista efter radering: ');  PrintList(huvud);  } }>
Javascript 
 // Javascript program to delete a given key from linked list.  // Structure for a node  class Node {  constructor() {  this.data;  this.next;  }  }  // Function to insert a node at the  // beginning of a Circular linked list  function push(head, data) {  // Create a new node and make head  // as next of it.  var ptr1 = new Node();  ptr1.data = data;  ptr1.next = head;  // If linked list is not NULL then  // set the next of last node  if (head != null) {  // Find the node before head and  // update next of it.  let temp = head;  while (temp.next != head) temp = temp.next;  temp.next = ptr1;  }  // For the first node  else ptr1.next = ptr1;  head = ptr1;  return head;  }  // Function to print nodes in a given  // circular linked list  function printList(head) {  let tempp = head;  if (head != null) {  do {  console.log(tempp.data);  tempp = tempp.next;  } while (tempp != head);  }  }  // Function to delete a given node  // from the list  function deleteNode(head, key) {  // If linked list is empty  if (head == null) return;  // If the list contains only a  // single node  if (head.data == key && head.next == head) {  head = null;  return;  }  let last = head;  // If head is to be deleted  if (head.data == key) {  // Find the last node of the list  while (last.next != head) last = last.next;  // Point last node to the next of  // head i.e. the second node  // of the list  last.next = head.next;  head = last.next;  return;  }  // Either the node to be deleted is  // not found or the end of list  // is not reached  while (last.next != head && last.next.data != key) {  last = last.next;  }  // If node to be deleted was found  if (last.next.data == key) {  d = last.next;  last.next = d.next;  d = null;  } else console.log('Given node is not found in the list!!!');  }  // Driver code  // Initialize lists as empty  head = null;  // Created linked list will be  // 2->5->7->8->10 huvud = push(huvud, 2);  huvud = push(huvud, 5);  huvud = push(huvud, 7);  huvud = push(huvud, 8);  huvud = push(huvud, 10);  console.log('Lista före radering: ');  printList(huvud);  deleteNode(huvud, 7);  console.log('Lista efter radering: ');  printList(huvud);>
Python3 
# Python program to delete a given key from linked list class Node: def __init__(self, data): self.data = data self.next = None # Function to insert a node at the # beginning of a Circular linked list def push(head, data): # Create a new node and make head as next of it. newP = Node(data) newP.next = head # If linked list is not NULL then # set the next of last node if head != None: # Find the node before head and # update next of it. temp = head while (temp.next != head): temp = temp.next temp.next = newP else: newP.next = newP head = newP return head # Function to print nodes in a given circular linked list def printList(head): if head == None: print('List is Empty') return temp = head.next print(head.data, end=' ') if (head != None): while (temp != head): print(temp.data, end=' ') temp = temp.next print() # Function to delete a given node # from the list def deleteNode(head, key): # If linked list is empty if (head == None): return # If the list contains only a # single node if (head.data == key and head.next == head): head = None return last = head # If head is to be deleted if (head.data == key): # Find the last node of the list while (last.next != head): last = last.next # Point last node to the next of # head i.e. the second node # of the list last.next = head.next head = last.next return # Either the node to be deleted is # not found or the end of list # is not reached while (last.next != head and last.next.data != key): last = last.next # If node to be deleted was found if (last.next.data == key): d = last.next last.next = d.next d = None else: print('Given node is not found in the list!!!') # Driver code # Initialize lists as empty head = None # Created linked list will be # 2->5->7->8->10 huvud = tryck(huvud, 2) huvud = tryck(huvud, 5) huvud = tryck(huvud, 7) huvud = tryck(huvud, 8) huvud = tryck(huvud, 10) print('Lista före radering: ') printList(head) deleteNode(head, 7) print('Lista efter radering: ') printList(head)>
Produktion 
List Before Deletion: 10 8 7 5 2 List After Deletion: 10 8 5 2>

Tidskomplexitet: O(N), värsta fall inträffar när elementet som ska raderas är det sista elementet och vi behöver gå igenom hela listan.
Hjälputrymme: O(1), Som konstant används extra utrymme.

Fördelar med cirkulära länkade listor:

  • Vilken nod som helst kan vara en utgångspunkt. Vi kan gå igenom hela listan genom att börja från vilken punkt som helst. Vi behöver bara sluta när den första besökta noden besöks igen.
  • Användbar för implementering av en kö. Till skillnad från detta implementering behöver vi inte behålla två pekare för fram och bak om vi använder en cirkulär länkad lista. Vi kan behålla en pekare till den senast infogade noden och fronten kan alltid erhållas som näst efter sist.
  • Cirkulära listor är användbara i applikationer för att upprepade gånger gå runt listan. Till exempel, när flera applikationer körs på en PC, är det vanligt att operativsystemet sätter de körande applikationerna på en lista och sedan bläddrar igenom dem, vilket ger var och en av dem en bit av tid att köra och sedan får dem att vänta medan CPU:n ges till en annan applikation. Det är bekvämt för operativsystemet att använda en cirkulär lista så att när det når slutet av listan kan det cykla runt till framsidan av listan.
  • Cirkulära dubbellänkade listor används för implementering av avancerade datastrukturer som Fibonacci Heap .
  • Att implementera en cirkulär länkad lista kan vara relativt enkelt jämfört med andra mer komplexa datastrukturer som träd eller grafer.

Nackdelar med cirkulär länkad lista:

  • Jämfört med enkellänkade listor är cirkulära listor mer komplexa.
  • Att vända på en cirkulär lista är mer komplicerat än att vända en cirkulär lista enskilt eller dubbelt.
  • Det är möjligt för koden att gå in i en oändlig loop om den inte hanteras varsamt.
  • Det är svårare att hitta slutet av listan och kontrollera loopen.
  • Även om cirkulärt länkade listor kan vara effektiva i vissa applikationer, kan deras prestanda vara långsammare än andra datastrukturer i vissa fall, till exempel när listan behöver sorteras eller sökas.
  • Cirkulärt länkade listor ger inte direkt åtkomst till enskilda noder

Tillämpningar av cirkulärt länkade listor:

  • Multiplayer-spel använder detta för att ge varje spelare en chans att spela.
  • En cirkulär länkad lista kan användas för att organisera flera applikationer som körs på ett operativsystem. Dessa applikationer itereras över av OS.
  • Cirkulärt länkade listor kan användas i resursallokeringsproblem.
  • Cirkulärt länkade listor används vanligtvis för att implementera cirkulära buffertar,
  • Cirkulärt länkade listor kan användas i simulering och spel.

Varför cirkulär länkad lista?

  • En nod pekar alltid på en annan nod, så NULL-tilldelning är inte nödvändig.
  • Vilken nod som helst kan ställas in som startpunkt.
  • Noder korsas snabbt från den första till den sista.

Nästa inlägg: Cirkulär länkad lista | Set 2 (Traversal) Cirkulär enkellänkad lista | Införande Vänligen skriv kommentarer om du hittar någon bugg i ovanstående kod/algoritm, eller hitta andra sätt att lösa samma problem