INNSETTING I SIRKULÆR ENKELTLENKET LISTE

I denne artikkelen vil vi lære hvordan du setter inn en node i en sirkulær koblet liste. Innsetting er en grunnleggende operasjon i koblede lister som innebærer å legge til en ny node i listen. I en sirkulær koblet liste kobles den siste noden tilbake til den første noden og skaper en løkke.

Det er fire hovedmåter å legge til elementer:

java matematikk tilfeldig

Innsetting i en tom liste
Innsetting i begynnelsen av listen
Innsetting på slutten av listen
Innsetting på en bestemt plassering i listen

Fordeler med å bruke en halepeker i stedet for en hodepeker

Vi må krysse hele listen for å sette inn en node i begynnelsen. Også for innsetting på slutten må hele listen krysses. Hvis i stedet for start peker tar vi en peker til den siste noden, så i begge tilfeller vil det ikke være behov for å krysse hele listen. Så innsetting i begynnelsen eller slutten tar konstant tid uavhengig av lengden på listen.

1. Sett inn i en tom liste i den sirkulære lenkede listen

For å sette inn en node i tom sirkulær lenket liste opprettes en ny node med de gitte datasettene sin neste peker til å peke på seg selv og oppdaterer siste peker for å referere til dette ny node .

Innsetting i en tom liste

Steg-for-steg tilnærming:

Sjekk om siste er ikke nullptr . Hvis ekte retur siste (listen er ikke tom).
Ellers opprette en ny node med de oppgitte dataene.
- Still inn nye noder neste peker for å peke på seg selv (sirkulær lenke).
- Oppdater siste å peke på ny node og returnere den.

For å lese mer om innsetting i en tom liste Se: Innsetting i en tom liste i den sirkulære lenkede listen

2. Innsetting i begynnelsen i sirkulær lenket liste

For å sette inn en ny node i begynnelsen av en sirkulær koblet liste
Vi lager først ny node og tildele minne til det.
Hvis listen er tom (indikert ved at den siste pekeren er NULL ) lager vi ny node peke på seg selv.
Hvis listen allerede inneholder noder, setter vi nye noder neste peker for å peke på nåværende hode av listen (som er siste->neste )
Deretter oppdaterer den siste nodens neste peker for å peke på ny node . Dette opprettholder den sirkulære strukturen til listen.

Innsetting-ved-begynnelsen-av-sirkulær-lenket-liste' loading='lazy' title=

Innsetting i begynnelsen i sirkulær lenket liste

For å lese mer om innsetting i begynnelsen, se: Innsetting i begynnelsen i sirkulær lenket liste

3. Innsetting på slutten i sirkulær lenket liste

For å sette inn en ny node på slutten av en sirkulær koblet liste, oppretter vi først den nye noden og tildeler minne for den.
mus og typer mus
Hvis listen er tom (gjennomsnittlig siste eller hale pekervesen NULL ) initialiserer vi listen med ny node og få den til å peke på seg selv for å danne en sirkulær struktur.
Hvis listen allerede inneholder noder, setter vi nye noder neste peker for å peke på nåværende hode (som er hale->neste )
Oppdater deretter nåværende hale neste peker for å peke på ny node .
Til slutt oppdaterer vi halepeker til ny node.
Dette vil sikre at ny node er nå siste node i listen samtidig som den sirkulære koblingen opprettholdes.

Insertion-at-the-end-of-circular-linked-list' loading='lazy' title=

Innsetting på slutten i sirkulær lenket liste

For å lese mer om innsetting på slutten, se: Innsetting på slutten i sirkulær lenket liste

4. Innsetting på spesifikk posisjon i sirkulært lenket liste

For å sette inn en ny node på en bestemt posisjon i en sirkulær lenket liste sjekker vi først om listen er tom.
Hvis det er og posisjon er ikke 1 så skriver vi ut en feilmelding fordi posisjonen ikke finnes i listen. jeg
f den posisjon er 1 så lager vi ny node og få det til å peke på seg selv.
Hvis listen ikke er tom, oppretter vi ny node og gå gjennom listen for å finne riktig innsettingspunkt.
Hvis posisjon er 1 vi setter inn ny node i begynnelsen ved å justere pekerne deretter.
For andre posisjoner går vi gjennom listen til vi når ønsket posisjon og setter inn ny node ved å oppdatere pekerne.
Hvis den nye noden settes inn på slutten, oppdaterer vi også siste peker for å referere til den nye noden som opprettholder den sirkulære strukturen til listen.

Insertion-at-specific-position-of-circular-linked-list' loading='lazy' title=

Innsetting på bestemt posisjon i sirkulært lenket liste

Steg-for-steg tilnærming:

Hvis siste er nullptr og pos er ikke 1 skriv ut ' Ugyldig stilling! '.
Ellers opprette en ny node med gitte data.
Sett inn i begynnelsen: Hvis pos er 1 oppdater pekere og returner sist.
Traversliste: Løkke for å finne innsettingspunktet; skriv ut 'Ugyldig posisjon!' hvis det er utenfor grensene.
Sett inn node: Oppdater pekere for å sette inn den nye noden.
Oppdatering sist: Hvis det er satt inn på slutten av oppdateringen siste .

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

Produksjon

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

Tidskompleksitet: O(n) må vi krysse listen for å finne den spesifikke posisjonen.
Hjelpeplass: O(1)

Lag quiz

TechCodeview