INFOGNING I CIRKULÄR ENKELLÄNKAD LISTA

I den här artikeln kommer vi att lära oss hur man infogar en nod i en cirkulär länkad lista. Infogning är en grundläggande operation i länkade listor som innebär att en ny nod läggs till i listan. I en cirkulär länkad lista ansluter den sista noden tillbaka till den första noden och skapar en loop.

Det finns fyra huvudsakliga sätt att lägga till objekt:

Infoga i en tom lista
Infogning i början av listan
Infogning i slutet av listan
Infogning på en specifik plats i listan

Fördelar med att använda en svanspekare istället för en huvudpekare

Vi måste gå igenom hela listan för att infoga en nod i början. Också för att infogas i slutet måste hela listan passeras. Om istället för start pekare tar vi en pekare till den sista noden så i båda fallen kommer det inte att finnas något behov av att gå igenom hela listan. Så insättning i början eller slutet tar konstant tid oavsett längden på listan.

1. Infoga i en tom lista i den cirkulära länkade listan

För att infoga en nod i en tom cirkulär länkad lista skapas en ny nod med den givna datauppsättningen dess nästa pekare att peka på sig själv och uppdaterar sista pekare för att hänvisa till detta ny nod .

Infoga i en tom lista

Steg-för-steg tillvägagångssätt:

Kontrollera om sista är inte nullptr . Om sann återvända sista (listan är inte tom).
Skapa annars en ny nod med de angivna uppgifterna.
- Ställ in nya noder nästa pekare att peka på sig själv (cirkulär länk).
- Uppdatera sista att peka på ny nod och lämna tillbaka den.

För att läsa mer om infogning i en tom lista Se: Infoga i en tom lista i den cirkulära länkade listan

2. Infogning i början i cirkulär länkad lista

För att infoga en ny nod i början av en cirkulär länkad lista
Vi skapar först ny nod och tilldela minne för det.
Om listan är tom (indikeras av att den sista pekaren är NULL ) vi gör ny nod peka på sig själv.
Om listan redan innehåller noder ställer vi in nya noder nästa pekare att peka på nuvarande huvud på listan (som är sist->nästa )
Uppdatera sedan den sista nodens nästa pekare för att peka på ny nod . Detta bibehåller listans cirkulära struktur.

Insättning-i-början-av-cirkulär-länkad-lista' loading='lazy' title=

Infogning i början i cirkulär länkad lista

För att läsa mer om Insättning i början Se: Infogning i början i cirkulär länkad lista

3. Infogning i slutet i cirkulär länkad lista

För att infoga en ny nod i slutet av en cirkulär länkad lista skapar vi först den nya noden och allokerar minne för den.
Om listan är tom (medelvärde sista eller svans pekare varelse NULL ) initialiserar vi listan med ny nod och få den att peka på sig själv för att bilda en cirkulär struktur.
Om listan redan innehåller noder ställer vi in nya noder nästa pekare att peka på nuvarande huvud (vilket är svans->nästa )
Uppdatera sedan nuvarande svans nästa pekare att peka på ny nod .
Äntligen uppdaterar vi svanspekare till ny nod.
Detta kommer att säkerställa att ny nod är nu sista noden i listan samtidigt som den cirkulära kopplingen bibehålls.

Insättning-vid-slutet-av-cirkulär-länkad-lista' loading='lazy' title=

Infogning i slutet i cirkulär länkad lista

För att läsa mer om insättning i slutet, se: Infogning i slutet i cirkulär länkad lista

4. Infogning på specifik plats i cirkulär länkad lista

För att infoga en ny nod på en specifik position i en cirkulär länkad lista kontrollerar vi först om listan är tom.
Om det är och placera är inte 1 sedan skriver vi ut ett felmeddelande eftersom positionen inte finns i listan. jag
f den placera är 1 sedan skapar vi ny nod och få den att peka på sig själv.
Om listan inte är tom skapar vi ny nod och gå igenom listan för att hitta rätt insättningspunkt.
Om placera är 1 vi sätter in ny nod i början genom att justera pekarna därefter.
För andra positioner går vi igenom listan tills vi når önskad position och sätter in ny nod genom att uppdatera pekarna.
Om den nya noden infogas i slutet uppdaterar vi också sista pekare för att referera till den nya noden som bibehåller listans cirkulära struktur.

Insättning-vid-specifik-position-av-cirkulär-länkad-lista' loading='lazy' title=

Infogning på specifik plats i cirkulär länkad lista

Steg-för-steg tillvägagångssätt:

Om sista är nullptr och pos är inte 1 skriv ut ' Ogiltig position! '.
Skapa annars en ny nod med givna data.
Infoga i början: Om pos är 1 uppdatera pekarna och returnera sist.
Traverslista: Slinga för att hitta insättningspunkten; print 'Ogiltig position!' om utanför gränserna.
Infoga nod: Uppdatera pekare för att infoga den nya noden.
Uppdatering senast: Om det infogas i slutet av uppdateringen sista .

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

Tidskomplexitet: O(n) vi måste gå igenom listan för att hitta den specifika positionen.
Hjälputrymme: O(1)

Skapa frågesport

TechCodeview