logo

TechCodeview

Beillesztés a kör alakú, egyedileg összekapcsolt listába

Ebben a cikkben megtudjuk, hogyan lehet csomópontot beszúrni egy körkörös hivatkozásos listába. A beszúrás a csatolt listák alapvető művelete, amely magában foglalja egy új csomópont hozzáadását a listához. Egy kör alakú linkelt listában az utolsó csomópont visszacsatlakozik az első csomóponthoz, létrehozva egy hurkot.

Négy fő módja van az elemek hozzáadásának:

  1. Beillesztés egy üres listába
  2. Beszúrás a lista elejére
  3. Beillesztés a lista végére
  4. Beszúrás a lista egy adott helyére

A fejmutató helyett a farokmutató használatának előnyei

A teljes listát be kell járnunk, hogy az elejére beszúrjunk egy csomópontot. A végére történő beszúráshoz is a teljes listát kell végigjárni. Ha ahelyett a indul mutatót az utolsó csomópontra viszünk, akkor mindkét esetben nem kell a teljes listát bejárni. Tehát a beszúrás az elejére vagy a végére állandó időt vesz igénybe, függetlenül a lista hosszától.



1. Beszúrás egy üres listába a kör alakú linkelt listában

Csomópont beszúrásához üres körkörös hivatkozási listába létrejön a új csomópont a megadott adatokkal beállítja a következő mutatóját, amely önmagára mutat, és frissíti a utolsó mutató erre hivatkozva új csomópont .

gyorsítótár törlése npm
Beszúrás-üres-listába-kör-linked-listába' title=Beillesztés egy üres listába

Lépésről lépésre történő megközelítés:

  • Ellenőrizze, ha utolsó nem nullptr . Ha igaz visszatérés utolsó (a lista nem üres).
  • Ellenkező esetben hozzon létre a új csomópont a megadott adatokkal.
    • Állítsa be a új csomópontok következő mutató önmagára mutat (kör alakú hivatkozás).
    • Frissítés utolsó hogy rámutasson a új csomópont és adja vissza.

Ha többet szeretne megtudni az üres listába történő beillesztésről, olvassa el: Beszúrás egy üres listába a kör alakú linkelt listában

2. Beszúrás a kör alakú linkelt listába az elejére

Új csomópont beszúrása egy körkörös csatolt lista elejére

x vagy c++
  • Először létrehozzuk a új csomópont és foglaljon le neki memóriát.
  • Ha a lista üres (ezt az utolsó mutató jelzi NULL ) elkészítjük a új csomópont mutat magára.
  • Ha a lista már tartalmaz csomópontokat, akkor beállítjuk a új csomópontok következő mutató mutat a jelenlegi fej a listából (ami utolsó->következő )
  • Ezután frissítse az utolsó csomópont következő mutatóját, hogy az a új csomópont . Ez megőrzi a lista körkörös szerkezetét.
Beszúrás-a-kör-összekapcsolt-lista elején' loading='lazy' title=Beszúrás a kör alakú linkelt lista elején

Ha többet szeretne megtudni a beszúrásról az elején, tekintse meg: Beszúrás a kör alakú linkelt lista elején

3. Beszúrás a kör alakú linkelt lista végére

Új csomópont beszúrásához egy kör alakú linkelt lista végére először létrehozzuk az új csomópontot, és lefoglalunk számára memóriát.

  • Ha a lista üres (értsd utolsó vagy farok mutató lény NULL ) inicializáljuk a listát a új csomópont és önmagára mutogatva körkörös szerkezetet alkot.
  • Ha a lista már tartalmaz csomópontokat, akkor beállítjuk a új csomópontok következő mutató mutat a jelenlegi fej (ami farok->következő )
  • Ezután frissítse a jelenlegi farok következő mutató mutat a új csomópont .
  • Végül frissítjük a farokmutató a új csomópont.
  • Ez biztosítja, hogy a új csomópont most a utolsó csomópont a listában a körkörös kapcsolat megtartása mellett.
Beszúrás a körkörös-linked-lista végén' loading='lazy' title=Beszúrás a kör alakú linkelt lista végére

Ha többet szeretne megtudni a beillesztésről a végén, olvassa el: Beszúrás a kör alakú linkelt lista végére

java szeletelése

4. Beszúrás a kör alakú linkelt listában egy adott helyre

Ha új csomópontot szeretne beszúrni egy körkörös hivatkozású lista egy adott pozíciójába, először ellenőrizze, hogy a lista üres-e.

  • Ha igen és a pozíció nem 1 akkor hibaüzenetet nyomtatunk, mert a pozíció nem létezik a listában. én
  • f a pozíció van 1 majd létrehozzuk a új csomópont és önmagára mutassa.
  • Ha a lista nem üres, létrehozzuk a új csomópont és a listán áthaladva megtalálja a megfelelő beszúrási pontot.
  • Ha a pozíció van 1 beillesztjük a új csomópont elején a mutatók megfelelő beállításával.
  • A többi pozíciónál addig haladunk a listán, amíg el nem érjük a kívánt pozíciót és beillesztjük a új csomópont a mutatók frissítésével.
  • Ha az új csomópont a végére kerül beillesztésre, akkor frissítjük a utolsó mutató, amely az új csomópontra hivatkozik, megtartva a lista körkörös szerkezetét.
Beszúrás a körkörös-linked-lista adott pozíciójában' loading='lazy' title=Beszúrás a kör alakú linkelt listában egy adott pozícióba

Lépésről lépésre történő megközelítés:

  • Ha utolsó van nullptr és pozíció nem 1 nyomtat Érvénytelen pozíció! '.
  • Ellenkező esetben hozzon létre egy új csomópontot a megadott adatokkal.
  • Beszúrás az elején: Ha a poz 1 frissítési mutatók és visszatérés utolsó.
  • Bejárási lista: Hurok a beillesztési pont megkereséséhez; print 'Érvénytelen pozíció!' ha kívül esik a határokon.
  • Csomópont beszúrása: Frissítse a mutatókat az új csomópont beillesztéséhez.
  • Utolsó frissítés: Ha a frissítés végén beillesztik utolsó .
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; }
C 
#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);

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

Időbeli összetettség: O(n) a listát kell bejárnunk, hogy megtaláljuk a konkrét pozíciót.
Kiegészítő tér: O(1)


Kvíz létrehozása