logo

TechCodeview

Introduksjon til Circular Linked List

Hva er Circular linked list?

De sirkulær lenket liste er en koblet liste der alle noder er koblet sammen for å danne en sirkel. I en sirkulær koblet liste er den første noden og den siste noden koblet til hverandre som danner en sirkel. Det er ingen NULL på slutten.

Sirkulær lenket liste



java math.random

Det er generelt to typer sirkulære koblede lister:

  • Sirkulær enkeltlenket liste: I en sirkulær enkeltlenket liste inneholder den siste noden på listen en peker til den første noden på listen. Vi krysser den sirkulære enkeltlenkede listen til vi kommer til samme node der vi startet. Den sirkulære enkeltlenkede listen har ingen begynnelse eller slutt. Ingen nullverdi er tilstede i den neste delen av noen av nodene.

Representasjon av rundskriv enkeltlenket liste

  • Rundskriv Dobbeltlenket liste: Sirkulær dobbeltlenket liste har egenskaper for både dobbeltlenket liste og sirkulært lenket liste der to påfølgende elementer er koblet eller koblet sammen med forrige og neste peker og den siste noden peker til den første noden med neste peker og også den første noden peker til den siste noden ved forrige peker.

Representasjon av sirkulær dobbeltlenket liste



Merk: Vi vil bruke den enkelt sirkulære lenkede listen for å representere hvordan den sirkulære lenkede listen fungerer.

Representasjon av sirkulært koblet liste:

Sirkulære lenkede lister ligner på enkle lenkede lister med unntak av å koble den siste noden til den første noden.

Noderepresentasjon av en sirkulær lenket liste:



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->neste = null;  } }>
Python3 
# Class Node, similar to the linked list class Node: def __init__(self,data): self.data = data self.next = None>

Eksempel på sirkulær enkeltlenket liste:

Eksempel på sirkulær lenket liste

Den ovennevnte rundskrivet enkeltlenkede listen kan representeres 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->neste = to; to->neste = tre; tre->neste = 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->neste = $to; $two->neste = $tre; $three->neste = $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>

Forklaring: I programmet ovenfor er en, to og tre noden med henholdsvis verdiene 3, 5 og 9 som er forbundet på en sirkulær måte som:

  • For Node One: Neste-pekeren lagrer adressen til node to.
  • For node to: The Next lagrer adressen til node tre
  • For node tre: De Neste peker på node én.

Operasjoner på den sirkulære tilknyttede listen:

Vi kan gjøre noen operasjoner på den sirkulære lenkede listen som ligner på den enkeltlenkede listen, som er:

  1. Innsetting
  2. Sletting

1. Innsetting i den sirkulære lenkede listen:

En node kan legges til på tre måter:

  1. Innsetting i begynnelsen av listen
  2. Innsetting på slutten av listen
  3. Innsetting mellom nodene

1) Innsetting i begynnelsen av listen: Følg disse trinnene for å sette inn en node på begynnelsen av listen:

  • Lag en node, si T.
  • Lag T -> neste = siste -> neste.
  • siste -> neste = T.

Sirkulær lenket liste før innsetting

Og så,

Sirkulær lenket liste etter innsetting

2) Innsetting på slutten av listen: Følg disse trinnene for å sette inn en node på slutten av listen:

streng til heltall
  • Lag en node, si T.
  • Lag T -> neste = siste -> neste;
  • siste -> neste = T.
  • siste = T.

Før innsetting,

Sirkulær lenket liste før innsetting av node på slutten

Etter innsetting,

Sirkulær lenket liste etter innsetting av node på slutten

3) Innsetting mellom nodene: Følg disse trinnene for å sette inn en node mellom de to nodene:

  • Lag en node, si T.
  • Søk etter noden som T må settes inn etter, si at noden er P.
  • Lag T -> neste = P -> neste;
  • P -> neste = T.

Anta at 12 må settes inn etter at noden har verdien 10,

Sirkulær lenket liste før innsetting

Etter søk og innsetting,

Sirkulær lenket liste etter innsetting

2. Sletting i en sirkulær lenket liste:

1) Slett noden bare hvis den er den eneste noden i den sirkulære koblede listen:

datostreng java
  • Frigjør nodens minne
  • Den siste verdien skal være NULL En node peker alltid til en annen node, så NULL-tilordning er ikke nødvendig.
    Enhver node kan settes som utgangspunkt.
    Noder krysses raskt fra den første til den siste.

2) Sletting av siste node:

  • Finn noden før den siste noden (la det være temp)
  • Hold adressen til noden ved siden av den siste noden i temp
  • Slett det siste minnet
  • Sett temp på slutten

3) Slett enhver node fra den sirkulære lenkede listen: Vi vil få en node og vår oppgave er å slette den noden fra den sirkulære lenkede listen.

Algoritme:
Sak 1 : Listen er tom.

  • Hvis listen er tom, kommer vi bare tilbake.

Tilfelle 2 : Listen er ikke tom

  • Hvis listen ikke er tom, definerer vi to pekere curr og forrige og initialiser pekeren curr med hode node.
  • Gå gjennom listen ved å bruke curr for å finne noden som skal slettes og før du går til curr til neste node, hver gang sett prev = curr.
  • Hvis noden blir funnet, sjekk om den er den eneste noden i listen. Hvis ja, sett head = NULL og free(curr).
  • Hvis listen har mer enn én node, sjekk om det er den første noden på listen. Betingelse for å sjekke dette( curr == hode). Hvis ja, flytt forrige til den når den siste noden. Etter at prev når den siste noden, setter du head = head -> next og prev -> next = head. Slett curr.
  • Hvis curr ikke er den første noden, sjekker vi om det er den siste noden i listen. Betingelse for å sjekke dette er (curr -> next == head).
  • Hvis curr er den siste noden. Sett prev -> next = head og slett noden curr med free(curr).
  • Hvis noden som skal slettes verken er den første noden eller den siste noden, sett prev -> next = curr -> next og slett curr.
  • Hvis noden ikke er til stede i listen, returner hodet og ikke gjør noe.

Nedenfor er implementeringen for tilnærmingen ovenfor:

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->neste = *head_ref;  // Hvis lenket liste ikke er NULL så // sett den neste av siste node if (*head_ref != NULL) { // Finn noden før hodet og // oppdater neste av den.  Node* temp = *head_ref;  while (temp->neste != *head_ref) temp = temp->neste;  temp->neste = ptr1;  } else // For den første noden ptr1->neste = ptr1;  *head_ref = ptr1; } // Funksjon for å skrive ut noder i en gitt // sirkulær lenket liste void printList(Node* head) { Node* temp = head;  if (hode != NULL) { gjør { cout<< temp->data<< ' ';  temp = temp->neste;  } while (temp != hode);  } 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 == nøkkel && (*hode)->neste == *hode) { free(*hode);  *hode = NULL;  komme tilbake;  } Node *siste = *hode, *d;  // Hvis hode skal slettes hvis ((*hode)->data == nøkkel) { // Finn siste node på listen mens (siste->neste != *hode) siste = siste->neste;  // Pek siste node til neste av // head dvs. den andre noden // av listen last->next = (*head)->neste;  gratis(*hode);  *hode = siste->neste;  komme tilbake;  } // Enten er noden som skal slettes // ikke funnet eller slutten av listen // nås ikke mens (siste->neste != *hode && siste->neste->data != nøkkel) { siste = siste ->neste;  } // Hvis noden som skal slettes ble funnet if (siste->neste->data == nøkkel) { d = siste->neste;  siste->neste = d->neste;  fri(d);  } annet 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(&hode, 5);  push(&hode, 7);  push(&hode, 8);  push(&hode, 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->neste = *head_ref;  // Hvis lenket liste ikke er NULL så // sett den neste av siste node if (*head_ref != NULL) { // Finn noden før hodet og // oppdater neste av den.  struct Node* temp = *head_ref;  while (temp->neste != *head_ref) temp = temp->neste;  temp->neste = ptr1;  } else // For den første noden ptr1->neste = ptr1;  *head_ref = ptr1; } // Funksjon for å skrive ut noder i en gitt // sirkulær lenket liste void printList(struct Node* head) { struct Node* temp = head;  if (hode != NULL) { do { printf('%d ', temp->data);  temp = temp->neste;  } while (temp != hode);  } printf('
'); } // Funksjon for å slette en gitt node // fra listen void deleteNode(struct Node** head, int key) { // If linked list is tom if (*head == NULL) return;  // Hvis listen inneholder bare en // enkelt node if ((*head)->data == key && (*head)->neste == *head) { free(*head);  *hode = NULL;  komme tilbake;  } struct Node *siste = *hode, *d;  // Hvis hode skal slettes hvis ((*hode)->data == nøkkel) { // Finn siste node på listen mens (siste->neste != *hode) siste = siste->neste;  // Pek siste node til neste av // head dvs. den andre noden // av listen last->next = (*head)->neste;  gratis(*hode);  *hode = siste->neste;  komme tilbake;  } // Enten er noden som skal slettes // ikke funnet eller slutten av listen // nås ikke mens (siste->neste != *hode && siste->neste->data != nøkkel) { siste = siste ->neste;  } // Hvis noden som skal slettes ble funnet if (siste->neste->data == nøkkel) { d = siste->neste;  siste->neste = d->neste;  fri(d);  } else printf('Den gitte noden finnes ikke i listen!!!
'); } // Driverkode int main() { // Initialiser lister som tom struct Node* head = NULL;  // Opprettet koblet liste vil være // 2->5->7->8->10 push(&head, 2);  push(&hode, 5);  push(&hode, 7);  push(&hode, 8);  push(&hode, 10);  printf('Liste før sletting: ');  printList(hode);  deleteNode(&head, 7);  printf('Liste etter sletting: ');  printList(hode);  returner 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 hode, 2);  Push(ref hode, 5);  Push(ref hode, 7);  Push(ref hode, 8);  Push(ref hode, 10);  Console.Write('Liste før sletting: ');  PrintList(hode);  DeleteNode(ref head, 7);  Console.Write('Liste etter sletting: ');  PrintList(hode);  } }>
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 hode = push(hode, 2);  hode = push(hode, 5);  hode = push(hode, 7);  hode = push(hode, 8);  hode = push(hode, 10);  console.log('Liste før sletting: ');  printList(hode);  deleteNode(hode, 7);  console.log('Liste etter sletting: ');  printList(hode);>
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 hode = skyv(hode, 2) hode = skyv(hode, 5) hode = skyv(hode, 7) hode = skyv(hode, 8) hode = skyv(hode, 10) print('Liste før sletting: ') printList(head) deleteNode(head, 7) print('Liste etter sletting: ') printList(head)>
Produksjon 
List Before Deletion: 10 8 7 5 2 List After Deletion: 10 8 5 2>

Tidskompleksitet: O(N), Worst case oppstår når elementet som skal slettes er det siste elementet og vi må gå gjennom hele listen.
Hjelpeplass: O(1), Som konstant brukes ekstra plass.

Fordeler med sirkulære lenkede lister:

  • Enhver node kan være et utgangspunkt. Vi kan krysse hele listen ved å starte fra et hvilket som helst punkt. Vi trenger bare å stoppe når den første besøkte noden besøkes igjen.
  • Nyttig for implementering av en kø. I motsetning til dette implementering, trenger vi ikke å opprettholde to pekere for foran og bak hvis vi bruker en sirkulær koblet liste. Vi kan opprettholde en peker til den sist innsatte noden, og fronten kan alltid oppnås som neste av sist.
  • Sirkulære lister er nyttige i programmer for å gå rundt listen gjentatte ganger. For eksempel, når flere applikasjoner kjører på en PC, er det vanlig at operativsystemet setter de kjørende applikasjonene på en liste og deretter blar gjennom dem, gir hver av dem et stykke tid til å kjøre, og deretter får dem til å vente mens CPU er gitt til en annen applikasjon. Det er praktisk for operativsystemet å bruke en sirkulær liste slik at når den når slutten av listen kan den sykle rundt til forsiden av listen.
  • Sirkulære dobbeltlenkede lister brukes for implementering av avanserte datastrukturer som Fibonacci-haug .
  • Å implementere en sirkulær koblet liste kan være relativt enkelt sammenlignet med andre mer komplekse datastrukturer som trær eller grafer.

Ulemper med sirkulær koblet liste:

  • Sammenlignet med enkeltlenkede lister er sirkulære lister mer komplekse.
  • Å reversere en sirkulær liste er mer komplisert enn å reversere en sirkulær liste enkeltvis eller dobbelt.
  • Det er mulig for koden å gå inn i en uendelig sløyfe hvis den ikke håndteres forsiktig.
  • Det er vanskeligere å finne slutten av listen og kontrollere loopen.
  • Selv om sirkulære koblede lister kan være effektive i visse applikasjoner, kan ytelsen deres være tregere enn andre datastrukturer i visse tilfeller, for eksempel når listen må sorteres eller søkes.
  • Sirkulære koblede lister gir ikke direkte tilgang til individuelle noder

Anvendelser av sirkulære lenkede lister:

  • Flerspillerspill bruker dette for å gi hver spiller en sjanse til å spille.
  • En sirkulær koblet liste kan brukes til å organisere flere kjørende applikasjoner på et operativsystem. Disse applikasjonene itereres over av operativsystemet.
  • Sirkulære lenkede lister kan brukes i ressursallokeringsproblemer.
  • Sirkulære lenkede lister brukes ofte til å implementere sirkulære buffere,
  • Sirkulære lenkede lister kan brukes i simulering og spill.

Hvorfor sirkulær lenket liste?

  • En node peker alltid til en annen node, så NULL-tilordning er ikke nødvendig.
  • Enhver node kan settes som utgangspunkt.
  • Noder krysses raskt fra den første til den siste.

Neste innlegg: Sirkulær lenket liste | Sett 2 (Traversal) Sirkulær enkeltlenket liste | Innsetting Vennligst skriv kommentarer hvis du finner noen feil i koden/algoritmen ovenfor, eller finn andre måter å løse det samme problemet på