EINFÜGEN IN EINE KREISFÖRMIGE EINFACH VERKNÜPFTE LISTE

In diesem Artikel erfahren Sie, wie Sie einen Knoten in eine zirkulär verknüpfte Liste einfügen. Das Einfügen ist eine grundlegende Operation in verknüpften Listen, bei der ein neuer Knoten zur Liste hinzugefügt wird. In einer zirkulär verknüpften Liste verbindet sich der letzte Knoten wieder mit dem ersten Knoten, wodurch eine Schleife entsteht.

Es gibt im Wesentlichen vier Möglichkeiten, Elemente hinzuzufügen:

Einfügen in eine leere Liste
Einfügung am Anfang der Liste
Einfügung am Ende der Liste
Einfügen an einer bestimmten Position in der Liste

Vorteile der Verwendung eines Schwanzzeigers anstelle eines Kopfzeigers

Wir müssen die gesamte Liste durchlaufen, um am Anfang einen Knoten einzufügen. Auch für das Einfügen am Ende muss die gesamte Liste durchlaufen werden. Wenn statt der Start Zeiger nehmen wir einen Zeiger auf den letzten Knoten, dann besteht in beiden Fällen keine Notwendigkeit, die gesamte Liste zu durchlaufen. Das Einfügen am Anfang oder Ende nimmt also unabhängig von der Länge der Liste eine konstante Zeit in Anspruch.

Java-Arraylist-Sortierung

1. Einfügen in eine leere Liste in der zirkulär verknüpften Liste

Durch Einfügen eines Knotens in eine leere kreisförmige verknüpfte Liste wird ein Knoten erstellt neuer Knoten Mit den angegebenen Daten setzt er seinen nächsten Zeiger auf sich selbst und aktualisiert den zuletzt Zeiger, um darauf zu verweisen neuer Knoten .

Einfügen in eine leere Liste

Schritt-für-Schritt-Ansatz:

Javascript-Druck

Überprüfen Sie, ob zuletzt ist nicht nullptr . Wenn WAHR zurückkehren zuletzt (Die Liste ist nicht leer).
Andernfalls erstellen Sie eine neuer Knoten mit den bereitgestellten Daten.
- Stellen Sie die ein neue Knoten Der nächste Zeiger zeigt auf sich selbst (kreisförmiger Link).
- Aktualisieren zuletzt auf das hinweisen neuer Knoten und gib es zurück.

Weitere Informationen zum Einfügen in eine leere Liste finden Sie unter: Einfügen in eine leere Liste in der zirkulär verknüpften Liste

2. Einfügen am Anfang in eine kreisförmige verknüpfte Liste

Zum Einfügen eines neuen Knotens am Anfang einer kreisförmig verknüpften Liste
Wir erstellen zunächst die neuer Knoten und Speicher dafür reservieren.
Wenn die Liste leer ist (angezeigt durch den letzten Zeiger). NULL ) Wir machen das neuer Knoten auf sich selbst hinweisen.
Wenn die Liste bereits Knoten enthält, legen wir fest neue Knoten nächster Zeiger, der auf die zeigt aktueller Kopf der Liste (das ist letztes->nächstes )
Aktualisieren Sie dann den nächsten Zeiger des letzten Knotens so, dass er auf den zeigt neuer Knoten . Dadurch bleibt die kreisförmige Struktur der Liste erhalten.

Einfügen am Anfang einer kreisförmig verknüpften Liste' loading='lazy' title=

Einfügen am Anfang in eine kreisförmige verknüpfte Liste

Weitere Informationen zum Einfügen am Anfang finden Sie unter: Einfügen am Anfang in eine kreisförmige verknüpfte Liste

3. Einfügen am Ende in eine kreisförmige verknüpfte Liste

Um einen neuen Knoten am Ende einer zirkulär verknüpften Liste einzufügen, erstellen wir zunächst den neuen Knoten und weisen ihm Speicher zu.
Wenn die Liste leer ist (mean zuletzt oder Schwanz Zeigerwesen NULL ) initialisieren wir die Liste mit dem neuer Knoten und es auf sich selbst zeigen zu lassen, um eine kreisförmige Struktur zu bilden.
Wenn die Liste bereits Knoten enthält, legen wir fest neue Knoten nächster Zeiger, der auf die zeigt aktueller Kopf (was ist tail->next )
Aktualisieren Sie dann die aktuelle Schwanz nächster Zeiger, der auf die zeigt neuer Knoten .
Schließlich aktualisieren wir die Schwanzzeiger zum neuer Knoten.
Dadurch wird sichergestellt, dass die neuer Knoten ist jetzt das letzter Knoten in der Liste unter Beibehaltung der zirkulären Verknüpfung.

Einfügen am Ende einer kreisförmig verknüpften Liste' loading='lazy' title=

Einfügen am Ende in eine kreisförmige verknüpfte Liste

Weitere Informationen zum Einfügen am Ende finden Sie unter: Einfügen am Ende in eine kreisförmige verknüpfte Liste
Android-Telefon-Einstellungsmenü

4. Einfügen an einer bestimmten Position in einer kreisförmigen verknüpften Liste

Um einen neuen Knoten an einer bestimmten Position in einer zirkulär verknüpften Liste einzufügen, prüfen wir zunächst, ob die Liste leer ist.
Wenn es so ist und das Position ist nicht 1 Dann geben wir eine Fehlermeldung aus, da die Position nicht in der Liste vorhanden ist. ICH
f die Position Ist 1 dann erstellen wir das neuer Knoten und lass es auf sich selbst zeigen.
Wenn die Liste nicht leer ist, erstellen wir die neuer Knoten und durchsuchen Sie die Liste, um den richtigen Einfügepunkt zu finden.
Wenn die Position Ist 1 wir fügen das ein neuer Knoten am Anfang, indem Sie die Zeiger entsprechend anpassen.
Für andere Positionen durchlaufen wir die Liste, bis wir die gewünschte Position erreichen und fügen die ein neuer Knoten durch Aktualisieren der Zeiger.
Wenn der neue Knoten am Ende eingefügt wird, aktualisieren wir auch den zuletzt Zeiger, der auf den neuen Knoten verweist und die kreisförmige Struktur der Liste beibehält.

Einfügen an einer bestimmten Position einer kreisförmig verknüpften Liste' loading='lazy' title=

Einfügen an einer bestimmten Position in einer kreisförmigen verknüpften Liste

Schritt-für-Schritt-Ansatz:

Wenn zuletzt Ist nullptr Und Pos ist nicht 1 drucken ' Ungültige Position! '.
Andernfalls erstellen Sie einen neuen Knoten mit den angegebenen Daten.
Am Anfang einfügen: Wenn pos 1 ist, aktualisieren Sie die Zeiger und geben Sie zuletzt zurück.
Traversenliste: Schleife, um den Einfügepunkt zu finden; print 'Ungültige Position!' wenn außerhalb der Grenzen.
Knoten einfügen: Aktualisieren Sie Zeiger, um den neuen Knoten einzufügen.
Zuletzt aktualisieren: Wenn am Ende des Updates eingefügt zuletzt .

C++

#include    using namespace std; struct Node{  int data;  Node *next;  Node(int value){  data = value;  next = nullptr;  } }; // Function to insert a node at a specific position in a circular linked list Node *insertAtPosition(Node *last int data int pos){  if (last == nullptr){  // If the list is empty  if (pos != 1){  cout << 'Invalid position!' << endl;  return last;  }  // Create a new node and make it point to itself  Node *newNode = new Node(data);  last = newNode;  last->next = last;  return last;  }  // Create a new node with the given data  Node *newNode = new Node(data);  // curr will point to head initially  Node *curr = last->next;  if (pos == 1){  // Insert at the beginning  newNode->next = curr;  last->next = newNode;  return last;  }  // Traverse the list to find the insertion point  for (int i = 1; i < pos - 1; ++i) {  curr = curr->next;    // If position is out of bounds  if (curr == last->next){  cout << 'Invalid position!' << endl;  return last;  }  }  // Insert the new node at the desired position  newNode->next = curr->next;  curr->next = newNode;  // Update last if the new node is inserted at the end  if (curr == last) last = newNode;  return last; } void printList(Node *last){  if (last == NULL) return;  Node *head = last->next;  while (true){  cout << head->data << ' ';  head = head->next;  if (head == last->next) break;  }  cout << endl; } int main(){  // Create circular linked list: 2 3 4  Node *first = new Node(2);  first->next = new Node(3);  first->next->next = new Node(4);  Node *last = first->next->next;  last->next = first;  cout << 'Original list: ';  printList(last);  // Insert elements at specific positions  int data = 5 pos = 2;  last = insertAtPosition(last data pos);  cout << 'List after insertions: ';  printList(last);  return 0; }

#include  #include  // Define the Node structure struct Node {  int data;  struct Node *next; }; struct Node* createNode(int value); // Function to insert a node at a specific position in a circular linked list struct Node* insertAtPosition(struct Node *last int data int pos) {  if (last == NULL) {  // If the list is empty  if (pos != 1) {  printf('Invalid position!n');  return last;  }  // Create a new node and make it point to itself  struct Node *newNode = createNode(data);  last = newNode;  last->next = last;  return last;  }  // Create a new node with the given data  struct Node *newNode = createNode(data);  // curr will point to head initially  struct Node *curr = last->next;  if (pos == 1) {  // Insert at the beginning  newNode->next = curr;  last->next = newNode;  return last;  }  // Traverse the list to find the insertion point  for (int i = 1; i < pos - 1; ++i) {  curr = curr->next;  // If position is out of bounds  if (curr == last->next) {  printf('Invalid position!n');  return last;  }  }  // Insert the new node at the desired position  newNode->next = curr->next;  curr->next = newNode;  // Update last if the new node is inserted at the end  if (curr == last) last = newNode;  return last; } // Function to print the circular linked list void printList(struct Node *last) {  if (last == NULL) return;  struct Node *head = last->next;  while (1) {  printf('%d ' head->data);  head = head->next;  if (head == last->next) break;  }  printf('n'); } // Function to create a new node struct Node* createNode(int value) {  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  newNode->data = value;  newNode->next = NULL;  return newNode; } int main() {  // Create circular linked list: 2 3 4  struct Node *first = createNode(2);  first->next = createNode(3);  first->next->next = createNode(4);  struct Node *last = first->next->next;  last->next = first;  printf('Original list: ');  printList(last);  // Insert elements at specific positions  int data = 5 pos = 2;  last = insertAtPosition(last data pos);  printf('List after insertions: ');  printList(last);  return 0; }

Java

class Node {  int data;  Node next;  Node(int value){  data = value;  next = null;  } } public class GFG {  // Function to insert a node at a specific position in a  // circular linked list  static Node insertAtPosition(Node last int data  int pos){  if (last == null) {  // If the list is empty  if (pos != 1) {  System.out.println('Invalid position!');  return last;  }  // Create a new node and make it point to itself  Node newNode = new Node(data);  last = newNode;  last.next = last;  return last;  }  // Create a new node with the given data  Node newNode = new Node(data);  // curr will point to head initially  Node curr = last.next;  if (pos == 1) {  // Insert at the beginning  newNode.next = curr;  last.next = newNode;  return last;  }  // Traverse the list to find the insertion point  for (int i = 1; i < pos - 1; ++i) {  curr = curr.next;  // If position is out of bounds  if (curr == last.next) {  System.out.println('Invalid position!');  return last;  }  }  // Insert the new node at the desired position  newNode.next = curr.next;  curr.next = newNode;  // Update last if the new node is inserted at the  // end  if (curr == last)  last = newNode;  return last;  }  static void printList(Node last){  if (last == null)  return;  Node head = last.next;  while (true) {  System.out.print(head.data + ' ');  head = head.next;  if (head == last.next)  break;  }  System.out.println();  }  public static void main(String[] args)  {  // Create circular linked list: 2 3 4  Node first = new Node(2);  first.next = new Node(3);  first.next.next = new Node(4);  Node last = first.next.next;  last.next = first;  System.out.print('Original list: ');  printList(last);  // Insert elements at specific positions  int data = 5 pos = 2;  last = insertAtPosition(last data pos);  System.out.print('List after insertions: ');  printList(last);  } }

Python

class Node: def __init__(self value): self.data = value self.next = None # Function to insert a node at a specific position in a circular linked list def insertAtPosition(last data pos): if last is None: # If the list is empty if pos != 1: print('Invalid position!') return last # Create a new node and make it point to itself new_node = Node(data) last = new_node last.next = last return last # Create a new node with the given data new_node = Node(data) # curr will point to head initially curr = last.next if pos == 1: # Insert at the beginning new_node.next = curr last.next = new_node return last # Traverse the list to find the insertion point for i in range(1 pos - 1): curr = curr.next # If position is out of bounds if curr == last.next: print('Invalid position!') return last # Insert the new node at the desired position new_node.next = curr.next curr.next = new_node # Update last if the new node is inserted at the end if curr == last: last = new_node return last # Function to print the circular linked list def print_list(last): if last is None: return head = last.next while True: print(head.data end=' ') head = head.next if head == last.next: break print() if __name__ == '__main__': # Create circular linked list: 2 3 4 first = Node(2) first.next = Node(3) first.next.next = Node(4) last = first.next.next last.next = first print('Original list: ' end='') print_list(last) # Insert elements at specific positions data = 5 pos = 2 last = insertAtPosition(last data pos) print('List after insertions: ' end='') print_list(last)

JavaScript

class Node {  constructor(value){  this.data = value;  this.next = null;  } } // Function to insert a node at a specific position in a // circular linked list function insertAtPosition(last data pos) {  if (last === null) {  // If the list is empty  if (pos !== 1) {  console.log('Invalid position!');  return last;  }  // Create a new node and make it point to itself  let newNode = new Node(data);  last = newNode;  last.next = last;  return last;  }  // Create a new node with the given data  let newNode = new Node(data);  // curr will point to head initially  let curr = last.next;  if (pos === 1) {  // Insert at the beginning  newNode.next = curr;  last.next = newNode;  return last;  }  // Traverse the list to find the insertion point  for (let i = 1; i < pos - 1; ++i) {  curr = curr.next;  // If position is out of bounds  if (curr === last.next) {  console.log('Invalid position!');  return last;  }  }  // Insert the new node at the desired position  newNode.next = curr.next;  curr.next = newNode;  // Update last if the new node is inserted at the end  if (curr === last)  last = newNode;  return last; } // Function to print the circular linked list function printList(last){  if (last === null)  return;  let head = last.next;  while (true) {  console.log(head.data + ' ');  head = head.next;  if (head === last.next)  break;  }  console.log(); } // Create circular linked list: 2 3 4 let first = new Node(2); first.next = new Node(3); first.next.next = new Node(4); let last = first.next.next; last.next = first; console.log('Original list: '); printList(last); // Insert elements at specific positions let data = 5; let pos = 2; last = insertAtPosition(last data pos); console.log('List after insertions: '); printList(last);

Ausgabe

Original list: 2 3 4 List after insertions: 2 5 3 4

Zeitkomplexität: O(n) müssen wir die Liste durchlaufen, um die spezifische Position zu finden.
Hilfsraum: O(1)

Quiz erstellen

TechCodeview

Einfügen in eine kreisförmige einfach verknüpfte Liste