INSERCIÓ EN UNA LLISTA CIRCULAR ENLLAÇADA INDIVIDUALMENT

En aquest article aprendrem a inserir un node en una llista enllaçada circular. La inserció és una operació fonamental en llistes enllaçades que implica afegir un nou node a la llista. En una llista enllaçada circular, l'últim node es connecta de nou al primer node creant un bucle.

Hi ha quatre maneres principals d'afegir elements:

Inserció en una llista buida
Inserció al començament de la llista
Inserció al final de la llista
Inserció en una posició concreta de la llista

Avantatges d'utilitzar un punter de cua en lloc d'un punter de cap

Hem de recórrer tota la llista per inserir un node al principi. També per a la inserció al final s'ha de recórrer tota la llista. Si en comptes de la començar punter agafem un punter a l'últim node i, en ambdós casos, no caldrà recórrer tota la llista. Per tant, la inserció al principi o al final requereix un temps constant, independentment de la longitud de la llista.

1. Inserció en una llista buida a la llista enllaçada circular

Per inserir un node en una llista enllaçada circular buida es crea un nou node amb les dades proporcionades estableix el seu següent punter per apuntar-se a si mateix i actualitza el darrer punter per fer referència a això nou node .

Inserció en una llista buida

Enfocament pas a pas:

Comproveu si darrer no ho és nullptr . Si veritat tornar darrer (la llista no està buida).
En cas contrari, creeu un nou node amb les dades facilitades.
- Estableix el nou node següent punter per apuntar-se a si mateix (enllaç circular).
- Actualització darrer per assenyalar el nou node i retornar-lo.

Per obtenir més informació sobre la inserció en una llista buida, consulteu: Inserció en una llista buida a la llista enllaçada circular

2. Inserció al principi en llista enllaçada circular

Per inserir un nou node al principi d'una llista enllaçada circular
Primer creem el nou node i assignar-hi memòria.
Si la llista està buida (s'indica que l'últim punter és NULL ) fem el nou node apuntar a si mateix.
Si la llista ja conté nodes, establim el nou node següent punter per assenyalar cap actual de la llista (que és últim->següent )
A continuació, actualitzeu el següent punter de l'últim node per apuntar-hi nou node . Això manté l'estructura circular de la llista.

Inserció-al-inici-de-llista-enllaçada-circular' loading='lazy' title=

Inserció al principi en llista enllaçada circular

Per obtenir més informació sobre la inserció al principi, consulteu: Inserció al principi en llista enllaçada circular

3. Inserció al final en llista enllaçada circular

Per inserir un nou node al final d'una llista enllaçada circular, primer creem el nou node i hi assignem memòria.
Si la llista està buida (mean darrer o cua ésser punter NULL ) inicialitzem la llista amb el nou node i fent-lo apuntar cap a si mateix per formar una estructura circular.
Si la llista ja conté nodes, establim el nou node següent punter per assenyalar cap actual (que és cua->següent )
A continuació, actualitzeu el cua actual següent punter per assenyalar nou node .
Finalment actualitzem el punter de cua al nou node.
Això garantirà que el nou node ara és el últim node a la llista mantenint l'enllaç circular.

Inserció-al-final-de-llista-enllaçada-circular' loading='lazy' title=

Inserció al final en llista enllaçada circular

Per obtenir més informació sobre la inserció al final, consulteu: Inserció al final en llista enllaçada circular

4. Inserció en una posició específica en llista enllaçada circular

Per inserir un nou node en una posició específica en una llista enllaçada circular, primer comprovem si la llista està buida.
Si és i el posició no ho és 1 llavors imprimim un missatge d'error perquè la posició no existeix a la llista. jo
f la posició és 1 després creem el nou node i fer-ho apuntar a si mateix.
Si la llista no està buida, creem el nou node i recorreu la llista per trobar el punt d'inserció correcte.
Si el posició és 1 inserim el nou node al principi ajustant els punters en conseqüència.
Per a altres posicions recorrem la llista fins a arribar a la posició desitjada i inserint el nou node mitjançant l'actualització dels punters.
Si al final s'insereix el nou node, també actualitzem el darrer punter per fer referència al nou node mantenint l'estructura circular de la llista.

Inserció-a-posició-específica-de-llista-enllaçada-circular' loading='lazy' title=

Inserció en una posició específica en llista enllaçada circular

Enfocament pas a pas:

Si darrer és nullptr i pos no ho és 1 imprimir' Posició no vàlida! '.
En cas contrari, creeu un nou node amb les dades donades.
Insereix a l'inici: Si pos és 1 actualitza els punters i torna l'últim.
Llista transversal: Bucle per trobar el punt d'inserció; imprimir "Posició no vàlida!" si està fora dels límits.
Insereix node: Actualitza els punters per inserir el nou node.
Última actualització: Si s'insereix al final de l'actualització darrer .

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

Sortida

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

Complexitat temporal: O(n) hem de recórrer la llista per trobar la posició específica.
Espai auxiliar: O(1)

Crea un qüestionari

TechCodeview