INSERAREA ÎN LISTA CIRCULARĂ LEGATĂ INDIVIDUAL

În acest articol vom învăța cum să inserăm un nod într-o listă circulară legată. Inserarea este o operație fundamentală în listele legate care implică adăugarea unui nou nod la listă. Într-o listă circulară legată, ultimul nod se conectează înapoi la primul nod creând o buclă.

Există patru moduri principale de a adăuga elemente:

Inserarea într-o listă goală
Inserarea la începutul listei
Inserare la sfârșitul listei
Inserarea într-o anumită poziție din listă

Avantajele utilizării unui indicator de coadă în locul unui indicator de cap

Trebuie să parcurgem întreaga listă pentru a insera un nod la început. De asemenea, pentru inserarea la sfârșit trebuie parcursă întreaga listă. Dacă în loc de început pointer luăm un pointer către ultimul nod, apoi în ambele cazuri nu va fi nevoie să parcurgem întreaga listă. Deci inserarea la început sau la sfârșit durează timp constant, indiferent de lungimea listei.

1. Inserarea într-o Listă goală în lista circulară legată

Pentru a insera un nod într-o listă circulară goală, se creează un nod nou cu datele date își setează următorul indicator să indice spre sine și actualizează dura indicator pentru a face referire la aceasta nod nou .

Inserare-în-o-listă-vide-în-listă-circulară-legată' title=

Inserarea într-o Listă goală

Abordare pas cu pas:

Verifică dacă dura nu este nullptr . Dacă adevărat reveni dura (lista nu este goală).
În caz contrar, creează un nod nou cu datele furnizate.
- Setați nodurile noi următorul indicator pentru a indica spre sine (link circular).
- Actualizare dura pentru a indica nod nou si returneaza-l.

Pentru a citi mai multe despre inserarea într-o listă goală Consultați: Inserarea într-o Listă goală în lista circulară legată

2. Inserarea la inceput in lista circulara legata

Pentru a insera un nou nod la începutul unei liste circulare legate
Mai întâi creăm nod nou și alocați-i memorie.
Dacă lista este goală (indicată de ultimul indicator fiind NUL ) facem nod nou arata spre sine.
Dacă lista conține deja noduri, atunci setăm nodurile noi următorul indicator pentru a indica actualul cap a listei (care este ultimul->urmatorul )
Apoi actualizați următorul indicator al ultimului nod pentru a indica nod nou . Aceasta menține structura circulară a listei.

Inserarea-la-începutul-listei-legate-circulare' loading='lazy' title=

Inserarea la început în lista circulară legată

Pentru a citi mai multe despre Inserare la început Consultați: Inserarea la început în lista circulară legată

3. Inserarea la sfârșit în listă circulară legată

Pentru a insera un nou nod la sfârșitul unei liste circulare legate, mai întâi creăm noul nod și alocam memorie pentru acesta.
șir de caractere java conține
Dacă lista este goală (media dura sau coadă indicatorul fiind NUL ) inițializam lista cu nod nou și făcându-l să se îndrepte spre sine pentru a forma o structură circulară.
Dacă lista conține deja noduri, atunci setăm nodurile noi următorul indicator pentru a indica actualul cap (care este coada->n continuare )
Apoi actualizați cozile curente următorul indicator pentru a indica nod nou .
În cele din urmă, actualizăm indicatorul de coadă la nod nou.
Acest lucru va asigura că nod nou este acum ultimul nod în listă menținând în același timp legătura circulară.

Inserare-la-sfârșitul-listei-legate-circulare' loading='lazy' title=

Inserarea la sfârșit în listă circulară legată

Pentru a citi mai multe despre Inserarea la sfârșit Consultați: Inserarea la sfârșit în listă circulară legată

4. Inserarea la o anumită poziție în lista circulară legată

Pentru a insera un nou nod într-o anumită poziție într-o listă circulară legată, verificăm mai întâi dacă lista este goală.
Dacă este și poziţie nu este 1 apoi tipărim un mesaj de eroare deoarece poziția nu există în listă. eu
f poziţie este 1 apoi creăm nod nou și fă-l să se îndrepte spre sine.
Dacă lista nu este goală, creăm nod nou și parcurgeți lista pentru a găsi punctul de inserare corect.
Dacă poziţie este 1 introducem nod nou la început ajustând indicatoarele în mod corespunzător.
Pentru alte pozitii parcurgem lista pana ajungem la pozitia dorita si introducem nod nou prin actualizarea indicatoarelor.
Dacă noul nod este introdus la sfârșit, actualizăm și dura pointer pentru a face referire la noul nod menținând structura circulară a listei.

Inserție-la-poziția-specifică-listei-legate-circulare' loading='lazy' title=

Inserarea la o anumită poziție în lista circulară legată

Abordare pas cu pas:

Dacă dura este nullptr şi poz nu este 1 printeaza ' Poziție nevalidă! '.
În caz contrar, creați un nou Nod cu datele date.
Introduceți la început: Dacă pos este 1, actualizați pointerii și reveniți ultimul.
Lista transversală: Buclă pentru a găsi punctul de inserare; printează „Poziție invalidă!” dacă este în afara limitelor.
Inserați nodul: Actualizați pointerii pentru a insera noul nod.
Ultima actualizare: Dacă este introdus la sfârșitul actualizării dura .

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

Ieșire

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

Complexitatea timpului: O(n) trebuie să parcurgem lista pentru a găsi poziția specifică.
Spațiu auxiliar: O(1)

Creați un test

TechCodeview

Inserarea în lista circulară legată individual