WSTAWIENIE DO CYKLICZNEJ LISTY POJEDYNCZO POŁĄCZONEJ

W tym artykule dowiemy się, jak wstawić węzeł do cyklicznej listy połączonej. Wstawianie to podstawowa operacja na listach połączonych, która polega na dodaniu nowego węzła do listy. Na liście połączonej cyklicznie ostatni węzeł łączy się z pierwszym węzłem, tworząc pętlę.

Istnieją cztery główne sposoby dodawania elementów:

Wstawienie na pustą listę
Wstawienie na początku listy
Wstawienie na końcu listy
Wstawienie na konkretną pozycję na liście

Zalety używania wskaźnika ogona zamiast wskaźnika głowy

Musimy przeszukać całą listę, żeby na początku wstawić węzeł. Również w celu wstawienia na końcu należy przejść całą listę. Jeżeli zamiast start pointer, przenosimy wskaźnik do ostatniego węzła, wtedy w obu przypadkach nie będzie potrzeby przeglądania całej listy. Zatem wstawienie na początku lub na końcu zajmuje stały czas, niezależnie od długości listy.

1. Wstawienie do pustej listy w okrągłej liście połączonej

Aby wstawić węzeł do pustej listy połączonej cyklicznie, tworzy się plik nowy węzeł z podanymi danymi ustawia swój następny wskaźnik tak, aby wskazywał na siebie i aktualizuje ostatni wskaźnik, aby się do tego odnieść nowy węzeł .

Wstawienie do pustej listy

Podejście krok po kroku:

Sprawdź, czy ostatni nie jest nullptr . Jeśli PRAWDA powrót ostatni (lista nie jest pusta).
W przeciwnym razie utwórz nowy węzeł z podanymi danymi.
- Ustaw nowy węzeł następny wskaźnik wskazujący na siebie (link cykliczny).
- Aktualizacja ostatni wskazać na nowy węzeł i zwróć to.

Aby przeczytać więcej na temat wstawiania na pustą listę, zobacz: Wstawienie do pustej listy w cyklicznej liście połączonej

2. Wstawienie na początku w cyklicznie połączonej liście

Aby wstawić nowy węzeł na początku listy połączonej cyklicznie
Najpierw tworzymy nowy węzeł i przydziel mu pamięć.
Jeśli lista jest pusta (na co wskazuje ostatni wskaźnik NIEWAŻNY ) robimy nowy węzeł wskazywać na siebie.
Jeśli lista zawiera już węzły, ustawiamy nowy węzeł następny wskaźnik wskazujący na obecna głowa z listy (tzn ostatni -> następny )
Następnie zaktualizuj następny wskaźnik ostatniego węzła, aby wskazywał na nowy węzeł . Zachowuje to cykliczną strukturę listy.

Wstawienie-na-początku-listy-połączonej-okrągle' loading='lazy' title=

Wstawienie na początku w cyklicznej liście połączonej

Aby przeczytać więcej o wstawianiu na początku, zobacz: Wstawienie na początku w cyklicznej liście połączonej
różnica między lwem a tygrysem

3. Wstawienie na końcu listy z linkami cyklicznymi

Aby wstawić nowy węzeł na końcu listy połączonej cyklicznie, najpierw tworzymy nowy węzeł i przydzielamy mu pamięć.
Jeśli lista jest pusta (tzn ostatni Lub ogon istota wskazująca NIEWAŻNY ) inicjujemy listę za pomocą nowy węzeł i skierowanie go na siebie, tworząc okrągłą strukturę.
Jeśli lista zawiera już węzły, ustawiamy nowy węzeł następny wskaźnik wskazujący na obecna głowa (czyli ogon->dalej )
Następnie zaktualizuj obecny ogon następny wskaźnik wskazujący na nowy węzeł .
Na koniec aktualizujemy wskaźnik ogona do nowy węzeł.
Zapewni to, że nowy węzeł jest teraz ostatni węzeł na liście, zachowując powiązanie cykliczne.

Wstawienie na końcu listy z linkami cyklicznymi' loading='lazy' title=

Wstawienie na końcu okrągłej listy połączonej

Aby przeczytać więcej o wstawianiu na końcu, zobacz: Wstawienie na końcu okrągłej listy połączonej

4. Wstawienie w określonej pozycji na liście połączonej cyklicznie

Aby wstawić nowy węzeł w określonej pozycji na liście połączonej cyklicznie, najpierw sprawdzamy, czy lista jest pusta.
Jeśli tak jest i pozycja nie jest 1 następnie wypisujemy komunikat o błędzie, ponieważ pozycja nie istnieje na liście. I
f pozycja Jest 1 następnie tworzymy nowy węzeł i sprawić, że będzie to wskazywało na siebie.
Jeżeli lista nie jest pusta tworzymy plik nowy węzeł i przejrzyj listę, aby znaleźć właściwy punkt wstawiania.
Jeśli pozycja Jest 1 wstawiamy nowy węzeł na początku, odpowiednio dostosowując wskazówki.
W przypadku innych pozycji przeglądamy listę, aż dotrzemy do żądanej pozycji i wstawiamy nowy węzeł poprzez aktualizację wskaźników.
Jeśli na końcu zostanie wstawiony nowy węzeł, aktualizujemy również plik ostatni wskaźnik odnoszący się do nowego węzła, zachowując cykliczną strukturę listy.

Wstawienie-w-określonej-pozycji-listy-połączonej-okrągle' loading='lazy' title=

Wstawienie w określonej pozycji na liście połączonej cyklicznie

Podejście krok po kroku:

Jeśli ostatni Jest nullptr I poz nie jest 1 drukuj ' Nieprawidłowa pozycja! '.
W przeciwnym razie Utwórz nowy węzeł z podanymi danymi.
Wstaw na początku: Jeśli poz ma wartość 1, zaktualizuj wskaźniki i wróć jako ostatni.
Lista trawersów: Pętla, aby znaleźć punkt wstawienia; print 'Nieprawidłowa pozycja!' jeśli poza granicami.
Wstaw węzeł: Zaktualizuj wskaźniki, aby wstawić nowy węzeł.
Aktualizacja ostatnia: Jeśli wstawiono na końcu aktualizacji ostatni .

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

Wyjście

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

Złożoność czasowa: O(n) musimy przeszukać listę, aby znaleźć konkretną pozycję.
Przestrzeń pomocnicza: O(1)

Utwórz quiz

TechCodeview