INVOEGING IN CIRCULAIRE ENKELVOUDIG GEKOPPELDE LIJST

In dit artikel zullen we leren hoe u een knooppunt in een circulair gekoppelde lijst kunt invoegen. Invoegen is een fundamentele handeling in gekoppelde lijsten, waarbij een nieuw knooppunt aan de lijst wordt toegevoegd. In een circulair gekoppelde lijst is het laatste knooppunt weer verbonden met het eerste knooppunt, waardoor een lus ontstaat.

Er zijn vier manieren om items toe te voegen:

Invoeging in een lege lijst
Invoeging aan het begin van de lijst
Invoeging aan het einde van de lijst
Invoeging op een specifieke positie in de lijst

Voordelen van het gebruik van een staartwijzer in plaats van een hoofdwijzer

We moeten de hele lijst doorkruisen om aan het begin een knooppunt in te voegen. Ook voor invoeging aan het einde moet de hele lijst worden doorlopen. Als in plaats van de begin pointer nemen we een pointer naar het laatste knooppunt, dan is het in beide gevallen niet nodig om de hele lijst te doorlopen. Het invoegen aan het begin of het einde kost dus een constante tijd, ongeacht de lengte van de lijst.

1. Invoeging in een lege lijst in de circulair gekoppelde lijst

Om een knooppunt in een lege cirkelvormige gekoppelde lijst in te voegen, wordt een nieuw knooppunt met de gegeven gegevens wordt de volgende pointer ingesteld om naar zichzelf te wijzen en wordt de laatst pointer om hiernaar te verwijzen nieuw knooppunt .

Invoeging in een lege lijst

Stapsgewijze aanpak:

Controleer of laatst niet nulptr . Als WAAR opbrengst laatst (de lijst is niet leeg).
Maak anders een nieuw knooppunt met de verstrekte gegevens.
- Stel de nieuwe knooppunten volgende aanwijzer die naar zichzelf wijst (cirkelvormige link).
- Update laatst te wijzen op de nieuw knooppunt en retourneer het.

Om meer te lezen over het invoegen in een lege lijst Raadpleeg: Invoeging in een lege lijst in de circulair gekoppelde lijst

2. Invoeging aan het begin van een circulair gekoppelde lijst

Om een nieuw knooppunt in te voegen aan het begin van een circulair gekoppelde lijst
Wij maken eerst de nieuw knooppunt en wijs er geheugen voor toe.
Als de lijst leeg is (aangegeven door de laatste aanwijzer NUL ) wij maken de nieuw knooppunt wijzen naar zichzelf.
Als de lijst al knooppunten bevat, stellen we de nieuwe knooppunten volgende aanwijzer om naar de huidige hoofd van de lijst (dat is laatste->volgende )
Werk vervolgens de volgende aanwijzer van het laatste knooppunt bij, zodat deze naar de verwijst nieuw knooppunt . Hierdoor blijft de cirkelvormige structuur van de lijst behouden.

Invoeging-aan-het-begin-van-circulair-gekoppelde-lijst' loading='lazy' title=

Invoeging aan het begin van een cirkelvormige gekoppelde lijst

Om meer te lezen over het inbrengen in het begin Raadpleeg: Invoeging aan het begin van een cirkelvormige gekoppelde lijst

3. Invoeging aan het einde van de cirkelvormige gekoppelde lijst

Om een nieuw knooppunt aan het einde van een circulair gekoppelde lijst in te voegen, maken we eerst het nieuwe knooppunt en wijzen we er geheugen voor toe.
Als de lijst leeg is (mee laatst of staart wijzer wezen NUL ) initialiseren we de lijst met de nieuw knooppunt en het naar zichzelf laten wijzen om een cirkelvormige structuur te vormen.
Als de lijst al knooppunten bevat, stellen we de nieuwe knooppunten volgende aanwijzer om naar de huidige hoofd (dat is staart->volgende )
Werk vervolgens de huidige staart volgende aanwijzer om naar de nieuw knooppunt .
Ten slotte updaten we de staartwijzer naar de nieuw knooppunt.
Dit zal ervoor zorgen dat de nieuw knooppunt is nu de laatste knooppunt in de lijst met behoud van de circulaire koppeling.

Invoeging-aan-het-einde-van-circulair-gekoppelde-lijst' loading='lazy' title=

Invoeging aan het einde van de cirkelvormige gekoppelde lijst

Om meer te lezen over het inbrengen aan het einde. Raadpleeg: Invoeging aan het einde van de cirkelvormige gekoppelde lijst

4. Invoeging op specifieke positie in circulair gekoppelde lijst

Om een nieuw knooppunt op een specifieke positie in een circulair gekoppelde lijst in te voegen, controleren we eerst of de lijst leeg is.
Als dat zo is en de positie niet 1 dan drukken we een foutmelding af omdat de positie niet in de lijst voorkomt. I
f de positie is 1 dan maken wij de nieuw knooppunt en laat het naar zichzelf verwijzen.
Als de lijst niet leeg is, maken we de nieuw knooppunt en doorloop de lijst om het juiste invoegpunt te vinden.
Als de positie is 1 wij plaatsen de nieuw knooppunt aan het begin door de wijzers dienovereenkomstig aan te passen.
Voor andere posities doorkruisen we de lijst totdat we de gewenste positie bereiken en de nieuw knooppunt door de wijzers bij te werken.
Als het nieuwe knooppunt aan het einde wordt ingevoegd, werken we ook de laatst pointer om naar het nieuwe knooppunt te verwijzen, waarbij de cirkelvormige structuur van de lijst behouden blijft.

Invoeging-op-specifieke-positie-van-circulair-gekoppelde-lijst' loading='lazy' title=

Invoeging op specifieke positie in circulair gekoppelde lijst

Stapsgewijze aanpak:

Als laatst is nulptr En pos niet 1 afdrukken ' Ongeldige positie! '.
Maak anders een nieuw knooppunt met de opgegeven gegevens.
Invoegen aan het begin: Als pos 1 is, worden de pointers bijgewerkt en als laatste geretourneerd.
Traverse Lijst: Loop om het invoegpunt te vinden; print 'Ongeldige positie!' indien buiten de grenzen.
Knooppunt invoegen: Update pointers om het nieuwe knooppunt in te voegen.
Laatste update: Indien ingevoegd bij de eindupdate laatst .

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);

Uitvoer

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

Tijdcomplexiteit: O(n) we moeten de lijst doorlopen om de specifieke positie te vinden.
Hulpruimte: O(1)

Quiz maken

TechCodeview