logo

TechCodeview

Introduktion til Circular Linked List

Hvad er cirkulært linket liste?

Det cirkulær linket liste er en sammenkædet liste, hvor alle noder er forbundet for at danne en cirkel. I en cirkulær sammenkædet liste er den første node og den sidste node forbundet med hinanden, som danner en cirkel. Der er ingen NULL i slutningen.

Cirkulær linket liste



java tilfældige tal generator

Der er generelt to typer cirkulære sammenkædede lister:

  • Cirkulær enkeltforbundet liste: I en cirkulær enkeltforbundet liste indeholder den sidste node på listen en pointer til den første node på listen. Vi krydser den cirkulære enkeltforbundne liste, indtil vi når den samme knude, hvor vi startede. Den cirkulære enkeltforbundne liste har ingen begyndelse eller slutning. Der er ingen nulværdi i den næste del af nogen af ​​noderne.

Repræsentation af cirkulære enkeltforbundet liste

  • Cirkulær Dobbeltlinket liste: Cirkulær dobbelt lænket liste har egenskaber for både dobbelt lænket liste og cirkulær lænket liste, hvor to på hinanden følgende elementer er forbundet eller forbundet med den forrige og næste pointer, og den sidste node peger på den første node ved den næste pointer og også den første node peger på den sidste node ved den forrige markør.

Repræsentation af cirkulær dobbeltforbundet liste



Bemærk: Vi vil bruge den enkelt cirkulære lænkede liste til at repræsentere arbejdet med den cirkulære lænkede liste.

Repræsentation af cirkulært linket liste:

Cirkulære lænkede lister ligner enkelte lænkede lister med undtagelse af at forbinde den sidste node med den første node.

Noderepræsentation af en cirkulær linket 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->next = null;  } }>
Python3 
# Class Node, similar to the linked list class Node: def __init__(self,data): self.data = data self.next = None>

Eksempel på cirkulært enkelt linket liste:

Eksempel på cirkulær linket liste

Ovenstående cirkulære enkeltforbundne liste kan repræsenteres 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æste = to; to->næste = tre; tre->næste = 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æste = $to; $two->next = $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>

Forklaring: I ovenstående program er et, to og tre noden med værdierne 3, 5 og 9, som er forbundet på en cirkulær måde som:

  • For Node One: Næste-markøren gemmer adressen på node to.
  • For node to: The Next gemmer adressen på Node tre
  • For node tre: Det Næste peger på node et.

Operationer på den cirkulære linkede liste:

Vi kan udføre nogle operationer på den cirkulære linkede liste svarende til den enkelt linkede liste, som er:

  1. Indskud
  2. Sletning

1. Indsættelse i den cirkulære linkede liste:

En node kan tilføjes på tre måder:

  1. Indsættelse i begyndelsen af ​​listen
  2. Indsættelse i slutningen af ​​listen
  3. Indsættelse mellem knudepunkterne

1) Indsættelse i begyndelsen af ​​listen: Følg disse trin for at indsætte en node i begyndelsen af ​​listen:

  • Opret en node, sig T.
  • Lav T -> næste = sidste -> næste.
  • sidste -> næste = T.

Cirkulær linket liste før indsættelse

Og så,

Cirkulær linket liste efter indsættelse

2) Indsættelse i slutningen af ​​listen: Følg disse trin for at indsætte en node i slutningen af ​​listen:

valg sort java
  • Opret en node, sig T.
  • Lav T -> næste = sidste -> næste;
  • sidste -> næste = T.
  • sidste = T.

Før indsættelse,

Cirkulær linket liste før indsættelse af node i slutningen

Efter indsættelse,

Cirkulær linket liste efter indsættelse af node i slutningen

3) Indsættelse mellem noderne: Følg disse trin for at indsætte en node mellem de to noder:

  • Opret en node, sig T.
  • Søg efter den node, hvorefter T skal indsættes, sig, at noden er P.
  • Lav T -> næste = P -> næste;
  • P -> næste = T.

Antag, at 12 skal indsættes, efter at noden har værdien 10,

Cirkulær linket liste før indsættelse

Efter søgning og indsættelse,

Cirkulær linket liste efter indsættelse

2. Sletning i en cirkulær linket liste:

1) Slet kun noden, hvis den er den eneste node i den cirkulære linkede liste:

returnerer arrays i java
  • Frigør nodens hukommelse
  • Den sidste værdi skal være NULL. En node peger altid på en anden node, så NULL-tildeling er ikke nødvendig.
    Enhver node kan indstilles som udgangspunkt.
    Noder krydses hurtigt fra den første til den sidste.

2) Sletning af den sidste node:

  • Find noden før den sidste node (lad det være temp)
  • Hold adressen på noden ved siden af ​​den sidste node i temp
  • Slet den sidste hukommelse
  • Sæt temp til sidst

3) Slet enhver node fra den cirkulære linkede liste: Vi får en node, og vores opgave er at slette den node fra den cirkulære linkede liste.

Algoritme:
Tilfælde 1 : Listen er tom.

  • Hvis listen er tom, vender vi bare tilbage.

Tilfælde 2 : Listen er ikke tom

  • Hvis listen ikke er tom, definerer vi to pointere curr og forrige og initialiser markøren curr med hoved node.
  • Gennemgå listen vha curr for at finde den node, der skal slettes, og før du flytter til curr til næste node, hver gang set prev = curr.
  • Hvis noden er fundet, skal du kontrollere, om den er den eneste node på listen. Hvis ja, sæt head = NULL og free(curr).
  • Hvis listen har mere end én node, skal du kontrollere, om det er den første node på listen. Betingelse for at kontrollere dette (curr == hoved). Hvis ja, så flyt prev indtil den når den sidste node. Efter at prev når den sidste node, sæt head = head -> next og prev -> next = head. Slet curr.
  • Hvis curr ikke er den første node, tjekker vi om det er den sidste node på listen. Betingelse for at kontrollere dette er (curr -> næste == hoved).
  • Hvis curr er den sidste node. Indstil prev -> next = head og slet noden curr ved free(curr).
  • Hvis noden, der skal slettes, hverken er den første node eller den sidste node, så sæt prev -> next = curr -> next og slet curr.
  • Hvis noden ikke er til stede i listen, returner hovedet og gør ikke noget.

Nedenfor er implementeringen af ​​ovenstående tilgang:

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;  // Hvis den linkede liste ikke er NULL, så // sæt den næste af sidste node if (*head_ref != NULL) { // Find noden før hovedet og // opdater den næste af den.  Node* temp = *head_ref;  while (temp->next != *head_ref) temp = temp->next;  temp->næste = ptr1;  } else // For den første node ptr1->next = ptr1;  *head_ref = ptr1; } // Funktion til at udskrive noder i en given // cirkulær linket liste void printList(Node* head) { Node* temp = head;  if (hoved != NULL) { gør { cout<< temp->data<< ' ';  temp = temp->Næste;  } while (temp != hoved);  } 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øgle && (*hoved)->næste == *hoved) { free(*hoved);  *hoved = NULL;  Vend tilbage;  } Node *sidste = *hoved, *d;  // Hvis hoved skal slettes, hvis ((*hoved)->data == nøgle) { // Find listens sidste knude, mens (last->next != *head) last = last->next;  // Peg sidste node til den næste af // hoved dvs. den anden node // på listen last->next = (*head)->next;  fri(*hoved);  *hoved = sidste->næste;  Vend tilbage;  } // Enten er noden, der skal slettes, // ikke fundet, eller slutningen af ​​listen // nås ikke mens (sidste->næste != *hoved && sidste->næste->data != nøgle) { last = last -> næste;  } // Hvis node, der skal slettes, blev fundet if (sidste->næste->data == nøgle) { d = sidste->næste;  sidste->næste = d->næste;  fri(d);  } else 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(&hoved, 5);  push(&hoved, 7);  push(&hoved, 8);  push(&hoved, 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;  // Hvis den linkede liste ikke er NULL, så // sæt den næste af sidste node if (*head_ref != NULL) { // Find noden før hovedet og // opdater den næste af den.  struct Node* temp = *head_ref;  while (temp->next != *head_ref) temp = temp->next;  temp->næste = ptr1;  } else // For den første node ptr1->next = ptr1;  *head_ref = ptr1; } // Funktion til at udskrive noder i en given // cirkulær linket liste void printList(struct Node* head) { struct Node* temp = head;  if (hoved != NULL) { do { printf('%d ', temp->data);  temp = temp->næste;  } while (temp != hoved);  } printf('
'); } // Funktion til at slette en given node // fra listen void deleteNode(struct Node** head, int key) { // Hvis den linkede liste er tom hvis (*head == NULL) returnerer;  // Hvis listen kun indeholder en // enkelt node hvis ((*head)->data == key && (*head)->next == *head) { free(*head);  *hoved = NULL;  Vend tilbage;  } struct Node *sidste = *hoved, *d;  // Hvis hoved skal slettes, hvis ((*hoved)->data == nøgle) { // Find listens sidste knude, mens (last->next != *head) last = last->next;  // Peg sidste node til den næste af // hoved dvs. den anden node // på listen last->next = (*head)->next;  fri(*hoved);  *hoved = sidste->næste;  Vend tilbage;  } // Enten er noden, der skal slettes, // ikke fundet, eller slutningen af ​​listen // er ikke nået mens (sidste->næste != *hoved && sidste->næste->data != nøgle) { sidste = sidste -> næste;  } // Hvis node, der skal slettes, blev fundet if (sidste->næste->data == nøgle) { d = sidste->næste;  sidste->næste = d->næste;  fri(d);  } else printf('Den givne node findes ikke på listen!!!
'); } // Driverkode int main() { // Initialiser lister som tomme struct Node* head = NULL;  // Oprettet linket liste vil være // 2->5->7->8->10 push(&head, 2);  push(&hoved, 5);  push(&hoved, 7);  push(&hoved, 8);  push(&hoved, 10);  printf('Liste før sletning: ');  printList(hoved);  deleteNode(&head, 7);  printf('Liste efter sletning: ');  printList(hoved);  retur 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 Skub(ref hoved, 2);  Skub (ref hoved, 5);  Skub (ref hoved, 7);  Skub (ref hoved, 8);  Skub (ref hoved, 10);  Console.Write('Liste før sletning: ');  PrintList(hoved);  DeleteNode(ref head, 7);  Console.Write('Liste efter sletning: ');  PrintList(hoved);  } }>
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 hoved = push(hoved, 2);  hoved = push(hoved, 5);  hoved = push(hoved, 7);  hoved = push(hoved, 8);  hoved = push(hoved, 10);  console.log('Liste før sletning: ');  printList(hoved);  deleteNode(hoved, 7);  console.log('Liste efter sletning: ');  printList(hoved);>
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 hoved = skub(hoved, 2) hoved = skub(hoved, 5) hoved = skub(hoved, 7) hoved = skub(hoved, 8) hoved = skub(hoved, 10) print('Liste før sletning: ') printList(hoved) sletNode(hoved, 7) print('Liste efter sletning: ') printList(hoved)>
Produktion 
List Before Deletion: 10 8 7 5 2 List After Deletion: 10 8 5 2>

Tidskompleksitet: O(N), Worst case opstår, når elementet, der skal slettes, er det sidste element, og vi skal bevæge os gennem hele listen.
Hjælpeplads: O(1), Som konstant bruges ekstra plads.

Fordele ved cirkulære linkede lister:

  • Enhver node kan være et udgangspunkt. Vi kan gennemgå hele listen ved at starte fra ethvert punkt. Vi skal bare stoppe, når den først besøgte node besøges igen.
  • Nyttig til implementering af en kø. I modsætning til det her implementering, behøver vi ikke at opretholde to pointere for og bag, hvis vi bruger en cirkulær linket liste. Vi kan opretholde en pointer til den sidst indsatte node, og fronten kan altid fås som den næstsidste.
  • Cirkulære lister er nyttige i applikationer til gentagne gange at gå rundt på listen. For eksempel, når flere applikationer kører på en pc, er det almindeligt, at operativsystemet sætter de kørende applikationer på en liste og derefter cykler gennem dem, hvilket giver hver af dem et stykke tid til at udføre, og derefter får dem til at vente, mens CPU'en gives til en anden applikation. Det er praktisk for operativsystemet at bruge en cirkulær liste, så når det når slutningen af ​​listen, kan det cykle rundt til forsiden af ​​listen.
  • Cirkulære dobbeltforbundne lister bruges til implementering af avancerede datastrukturer som f.eks Fibonacci-bunke .
  • Implementering af en cirkulær linket liste kan være relativt let sammenlignet med andre mere komplekse datastrukturer som træer eller grafer.

Ulemper ved cirkulær linket liste:

  • Sammenlignet med enkeltforbundne lister er cirkulære lister mere komplekse.
  • At vende en cirkulær liste er mere kompliceret end at vende en cirkulær liste enkeltvis eller dobbelt.
  • Det er muligt for koden at gå ind i en uendelig løkke, hvis den ikke håndteres forsigtigt.
  • Det er sværere at finde slutningen af ​​listen og kontrollere løkken.
  • Selvom cirkulære sammenkædede lister kan være effektive i visse applikationer, kan deres ydeevne være langsommere end andre datastrukturer i visse tilfælde, såsom når listen skal sorteres eller søges.
  • Cirkulære linkede lister giver ikke direkte adgang til individuelle noder

Anvendelser af cirkulære sammenkædede lister:

  • Multiplayer spil bruger dette til at give hver spiller en chance for at spille.
  • En cirkulær sammenkædet liste kan bruges til at organisere flere kørende applikationer på et operativsystem. Disse applikationer gentages af OS.
  • Cirkulære linkede lister kan bruges i ressourceallokeringsproblemer.
  • Cirkulære forbundne lister bruges almindeligvis til at implementere cirkulære buffere,
  • Cirkulære sammenkædede lister kan bruges i simulering og spil.

Hvorfor cirkulær linket liste?

  • En node peger altid på en anden node, så NULL-tildeling er ikke nødvendig.
  • Enhver node kan indstilles som udgangspunkt.
  • Noder krydses hurtigt fra den første til den sidste.

Næste indlæg: Cirkulær linket liste | Sæt 2 (Traversal) Cirkulær enkeltforbundet liste | Indskud Skriv venligst kommentarer, hvis du finder en fejl i ovenstående kode/algoritme, eller find andre måder at løse det samme problem på