INSERTION DANS UNE LISTE CIRCULAIRE À LIEN UNIQUE

Dans cet article, nous apprendrons comment insérer un nœud dans une liste chaînée circulaire. L'insertion est une opération fondamentale dans les listes chaînées qui consiste à ajouter un nouveau nœud à la liste. Dans une liste chaînée circulaire, le dernier nœud se reconnecte au premier nœud créant une boucle.

Il existe quatre manières principales d'ajouter des éléments :

Insertion dans une liste vide
Insertion en début de liste
Insertion en fin de liste
Insertion à une position spécifique dans la liste

Avantages de l'utilisation d'un pointeur de queue au lieu d'un pointeur de tête

Nous devons parcourir toute la liste pour insérer un nœud au début. De plus, pour l'insertion à la fin, toute la liste doit être parcourue. Si au lieu du commencer pointeur nous prenons un pointeur vers le dernier nœud alors dans les deux cas il ne sera pas nécessaire de parcourir toute la liste. Ainsi, l'insertion au début ou à la fin prend un temps constant quelle que soit la longueur de la liste.

1. Insertion dans une liste vide dans la liste chaînée circulaire

Insérer un nœud dans une liste chaînée circulaire vide crée un nouveau nœud avec les données données, son prochain pointeur pointe vers lui-même et met à jour le dernier pointeur pour référencer ceci nouveau nœud .

Insertion dans une liste vide

Approche étape par étape :

Vérifiez si dernier n'est pas nullptr . Si vrai retour dernier (la liste n'est pas vide).
Sinon, créez un nouveau nœud avec les données fournies.
- Réglez le nouveaux nœuds pointeur suivant pour pointer vers lui-même (lien circulaire).
- Mise à jour dernier pointer vers le nouveau nœud et retournez-le.

Pour en savoir plus sur l'insertion dans une liste vide, reportez-vous : Insertion dans une liste vide dans la liste chaînée circulaire

2. Insertion au début dans une liste chaînée circulaire

Pour insérer un nouveau nœud au début d'une liste chaînée circulaire
Nous créons d'abord le nouveau nœud et allouez-lui de la mémoire.
Si la liste est vide (indiqué par le dernier pointeur étant NUL ) nous faisons le nouveau nœud pointer vers lui-même.
Si la liste contient déjà des nœuds, nous définissons le nouveaux nœuds pointeur suivant pour pointer vers le chef actuel de la liste (qui est dernier -> suivant )
Mettez ensuite à jour le pointeur suivant du dernier nœud pour qu'il pointe vers le nouveau nœud . Cela maintient la structure circulaire de la liste.

Insertion-au-début-d'une-liste-circulaire-liée' loading='lazy' title=

Insertion au début dans une liste chaînée circulaire

Pour en savoir plus sur l'insertion au début, reportez-vous : Insertion au début dans une liste chaînée circulaire
comment convertir un entier en chaîne Java

3. Insertion à la fin dans une liste chaînée circulaire

Pour insérer un nouveau nœud à la fin d'une liste chaînée circulaire, nous créons d'abord le nouveau nœud et lui allouons de la mémoire.
Si la liste est vide (c'est-à-dire dernier ou queue pointeur étant NUL ) on initialise la liste avec le nouveau nœud et en le faisant pointer vers lui-même pour former une structure circulaire.
Si la liste contient déjà des nœuds, nous définissons le nouveaux nœuds pointeur suivant pour pointer vers le chef actuel (ce qui est queue->suivant )
Mettez ensuite à jour le queue actuelle pointeur suivant pour pointer vers le nouveau nœud .
Enfin, nous mettons à jour le pointeur de queue au nouveau nœud.
Cela garantira que le nouveau nœud est maintenant le dernier nœud dans la liste tout en conservant le lien circulaire.

Insertion à la fin d'une liste liée à une circulaire' loading='lazy' title=

Insertion à la fin dans une liste chaînée circulaire

Pour en savoir plus sur l'insertion à la fin, reportez-vous : Insertion à la fin dans une liste chaînée circulaire

4. Insertion à une position spécifique dans la liste chaînée circulaire

Pour insérer un nouveau nœud à une position spécifique dans une liste chaînée circulaire, nous vérifions d'abord si la liste est vide.
Si c'est le cas et que position n'est pas 1 puis nous imprimons un message d'erreur car la position n'existe pas dans la liste. je
f le position est 1 puis nous créons le nouveau nœud et faites-le pointer vers lui-même.
Si la liste n'est pas vide nous créons le nouveau nœud et parcourez la liste pour trouver le point d’insertion correct.
Si le position est 1 nous insérons le nouveau nœud au début en ajustant les pointeurs en conséquence.
Pour les autres positions, nous parcourons la liste jusqu'à atteindre la position souhaitée et en insérant le nouveau nœud en mettant à jour les pointeurs.
Si le nouveau nœud est inséré à la fin, nous mettons également à jour le dernier pointeur pour référencer le nouveau nœud conservant la structure circulaire de la liste.

Insertion à une position spécifique d'une liste liée circulaire' loading='lazy' title=

Insertion à une position spécifique dans la liste chaînée circulaire

Approche étape par étape :

Si dernier est nullptr et position n'est pas 1 imprimer ' Position invalide ! '.
Sinon, créez un nouveau nœud avec les données données.
Insérer au début : Si pos est 1, mettez à jour les pointeurs et revenez en dernier.
Liste des parcours : Boucle pour trouver le point d'insertion ; print 'Position invalide !' si hors limites.
Insérer un nœud : Mettez à jour les pointeurs pour insérer le nouveau nœud.
Dernière mise à jour : Si inséré à la fin de la mise à jour dernier .

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

Sortir

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

Complexité temporelle : O(n) nous devons parcourir la liste pour trouver la position spécifique.
Espace auxiliaire : O(1)

Créer un quiz

TechCodeview