INDSÆTTELSE I CIRKULÆR ENKELTFORBUNDET LISTE

I denne artikel vil vi lære, hvordan du indsætter en node i en cirkulær linket liste. Indsættelse er en grundlæggende operation i sammenkædede lister, der involverer tilføjelse af en ny node til listen. I en cirkulær sammenkædet liste forbinder den sidste node tilbage til den første node og skaber en loop.

Der er fire hovedmåder at tilføje elementer:

streng sammenlignet

Indsættelse i en tom liste
Indsættelse i begyndelsen af listen
Indsættelse i slutningen af listen
Indsættelse på en bestemt position på listen

Fordele ved at bruge en halepointer i stedet for en hovedpointer

Vi er nødt til at krydse hele listen for at indsætte en node i begyndelsen. Også for indsættelse i slutningen skal hele listen gennemgås. Hvis i stedet for starte pointer tager vi en pointer til den sidste node, så vil der i begge tilfælde ikke være behov for at krydse hele listen. Så indsættelse i begyndelsen eller slutningen tager konstant tid, uanset listens længde.

1. Indsættelse i en tom liste i den cirkulære sammenkædede liste

For at indsætte en node i en tom cirkulær sammenkædet liste oprettes en ny node med de givne datasæt dens næste pointer til at pege på sig selv og opdaterer sidst pointer til at henvise til dette ny node .

Indsættelse i en tom liste

Trin-for-trin tilgang:

Tjek evt sidst er ikke nullptr . Hvis ægte returnere sidst (listen er ikke tom).
Ellers opret en ny node med de oplyste data.
- Indstil nye knudepunkter næste pointer til at pege på sig selv (cirkulært link).
- Opdatering sidst at pege på ny node og returnere den.

For at læse mere om indsættelse i en tom liste Se: Indsættelse i en tom liste i den cirkulære linkede liste

2. Indsættelse i begyndelsen i cirkulært linket liste

For at indsætte en ny node i begyndelsen af en cirkulær sammenkædet liste
Vi opretter først ny node og alloker hukommelse til det.
Hvis listen er tom (angivet ved at den sidste markør er NULL ) laver vi ny node pege på sig selv.
Hvis listen allerede indeholder noder, sætter vi nye knudepunkter næste pointer til at pege på nuværende hoved af listen (som er sidste->næste )
Opdater derefter den sidste nodes næste pointer til at pege på ny node . Dette bevarer listens cirkulære struktur.

Indsættelse-ved-begyndelsen-af-cirkulær-linket-liste' loading='lazy' title=

Indsættelse i begyndelsen i cirkulært linket liste

For at læse mere om Indsættelse i begyndelsen Se: Indsættelse i begyndelsen i cirkulært linket liste

3. Indsættelse i slutningen i cirkulært linket liste

For at indsætte en ny node i slutningen af en cirkulær sammenkædet liste opretter vi først den nye node og allokerer hukommelse til den.
matematik pow java
Hvis listen er tom (gennemsnit sidst eller hale pointer væsen NULL ) initialiserer vi listen med ny node og få det til at pege på sig selv for at danne en cirkulær struktur.
Hvis listen allerede indeholder noder, sætter vi nye knudepunkter næste pointer til at pege på nuværende hoved (som er hale->næste )
Opdater derefter nuværende hale næste pointer til at pege på ny node .
Endelig opdaterer vi haleviser til ny node.
Dette vil sikre, at ny node er nu sidste knudepunkt på listen, samtidig med at den cirkulære kobling bevares.

Indsættelse-ved-slutningen-af-cirkulær-linket-liste' loading='lazy' title=

Indsættelse i slutningen i cirkulært linket liste

For at læse mere om indsættelse i slutningen henvises til: Indsættelse i slutningen i cirkulært linket liste

4. Indsættelse på specifik position i cirkulært linket liste

For at indsætte en ny node på en specifik position i en cirkulær linket liste kontrollerer vi først, om listen er tom.
Hvis det er og position er ikke 1 så udskriver vi en fejlmeddelelse, fordi positionen ikke findes på listen. jeg
f den position er 1 så skaber vi ny node
Hvis listen ikke er tom, opretter vi ny node og gennemse listen for at finde det korrekte indsættelsespunkt.
Hvis position er 1 vi indsætter ny node i begyndelsen ved at justere viserne i overensstemmelse hermed.
For andre positioner går vi gennem listen, indtil vi når den ønskede position og indsætter ny node ved at opdatere pointerne.
Hvis den nye node indsættes i slutningen, opdaterer vi også sidst markør til at henvise til den nye node, der opretholder listens cirkulære struktur.

Indsættelse-på-specifik-position-af-cirkulær-linket-liste' loading='lazy' title=

Indsættelse på specifik position i cirkulært linket liste

Trin-for-trin tilgang:

Hvis sidst er nullptr og pos er ikke 1 print ' Ugyldig stilling! '.
Ellers opret en ny node med givne data.
Indsæt i begyndelsen:
Traverse liste: Loop to find the insertion point; print 'Invalid position!' hvis det er uden for rammerne.
Indsæt node: Opdater pointere for at indsætte den nye node.
Sidste opdatering: Hvis det er indsat ved slutningen af opdateringen sidst .

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

Produktion

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

Tidskompleksitet: O(n) vi skal krydse listen for at finde den specifikke position.
Hjælpeplads: O(1)

Opret quiz