DAIRESEL TEK BAĞLANTILI LISTEYE EKLEME

Bu yazıda dairesel bağlantılı listeye nasıl düğüm ekleneceğini öğreneceğiz. Ekleme, bağlantılı listelerde listeye yeni bir düğüm eklemeyi içeren temel bir işlemdir. Dairesel bağlantılı listede son düğüm ilk düğüme bağlanarak bir döngü oluşturur.

Öğe eklemenin dört ana yolu vardır:

csma ve csma cd'si

Boş bir listeye ekleme
Listenin başına ekleme
Listenin sonuna ekleme
Listede belirli bir konuma ekleme

Baş işaretçisi yerine kuyruk işaretçisi kullanmanın avantajları

Başa bir düğüm eklemek için listenin tamamını geçmemiz gerekiyor. Ayrıca sonuna eklemek için tüm listenin üzerinden geçilmesi gerekir. Eğer bunun yerine başlangıç işaretçiyi son düğüme yönlendirirsek, her iki durumda da tüm listeyi dolaşmaya gerek kalmaz. Dolayısıyla listenin uzunluğuna bakılmaksızın başına veya sonuna ekleme işlemi sabit zaman alır.

1. Dairesel bağlantılı listede boş bir Listeye ekleme

Boş dairesel bağlantılı listeye bir düğüm eklemek için bir yeni düğüm verilen verilerle bir sonraki işaretçiyi kendisine işaret edecek şekilde ayarlar ve son buna başvurmak için işaretçi yeni düğüm .

Boş bir Listeye ekleme

Adım adım yaklaşım:

olup olmadığını kontrol edin son değil nullptr . Eğer doğru geri dönmek son (liste boş değil).
Aksi halde Oluştur yeni düğüm sağlanan verilerle.
- Ayarla yeni düğüm sonraki işaretçinin kendisine işaret etmesini sağlar (dairesel bağlantı).
- Güncelleme son işaret etmek yeni düğüm ve geri ver.

Boş bir listeye ekleme hakkında daha fazla bilgi edinmek için Bakınız: Dairesel bağlantılı listede boş bir Listeye ekleme

2. Dairesel bağlantılı listenin başına ekleme

Dairesel bağlı listenin başına yeni bir düğüm eklemek için
İlk önce şunu oluşturuyoruz yeni düğüm ve bunun için hafıza ayırın.
Liste boşsa (son işaretçinin bulunmasıyla gösterilir) HÜKÜMSÜZ ) yapıyoruz yeni düğüm kendisine işaret eder.
Listede zaten düğümler varsa, o zaman yeni düğüm işaret edecek sonraki işaretçi mevcut kafa listenin (ki bu son->sonraki )
Ardından son düğümün bir sonraki işaretçisini işaret edecek şekilde güncelleyin. yeni düğüm . Bu, listenin dairesel yapısını korur.

Dairesel bağlantılı listenin başlangıcına ekleme' loading='lazy' title=

Dairesel bağlantılı listenin başına ekleme

Başlangıçta Ekleme hakkında daha fazla bilgi edinmek için bkz.: Dairesel bağlantılı listenin başına ekleme

3. Dairesel bağlantılı listenin sonuna ekleme

Dairesel bağlı listenin sonuna yeni bir düğüm eklemek için önce yeni düğümü oluştururuz ve ona bellek ayırırız.
json örneğinde json
Liste boşsa (ortalama son veya kuyruk işaretçi olmak HÜKÜMSÜZ ) listeyi şununla başlatıyoruz: yeni düğüm ve dairesel bir yapı oluşturacak şekilde kendisine işaret etmesini sağlıyor.
Listede zaten düğümler varsa, o zaman yeni düğüm işaret edecek sonraki işaretçi mevcut kafa (ki bu kuyruk->sonraki )
Daha sonra güncelleyin mevcut kuyruk işaret edecek sonraki işaretçi yeni düğüm .
Sonunda güncelliyoruz kuyruk işaretçisi -e yeni düğüm.
Bu, yeni düğüm şimdi son düğüm dairesel bağlantıyı korurken listede.

Dairesel bağlantılı listenin sonuna ekleme

Sonuna Ekleme hakkında daha fazla bilgi edinmek için bkz.: Dairesel bağlantılı listenin sonuna ekleme

4. Dairesel bağlantılı listede belirli bir konuma ekleme

Dairesel bağlı listede belirli bir konuma yeni bir düğüm eklemek için öncelikle listenin boş olup olmadığını kontrol ederiz.
Eğer öyleyse ve konum değil 1 daha sonra konum listede bulunmadığından bir hata mesajı yazdırırız. BEN
f konum öyle 1 sonra şunu yaratırız yeni düğüm ve kendisine işaret etmesini sağlayın.
Liste boş değilse oluştururuz yeni düğüm ve doğru ekleme noktasını bulmak için listeyi dolaşın.
Eğer konum öyle 1 şunu ekliyoruz yeni düğüm Başlangıçta işaretçileri buna göre ayarlayarak.
Diğer pozisyonlar için istenilen pozisyona ulaşana kadar listede dolaşıyoruz ve yeni düğüm işaretçileri güncelleyerek.
Eğer yeni düğüm sona eklenirse, aynı zamanda güncelleriz. son Listenin dairesel yapısını koruyarak yeni düğüme başvurmak için işaretçi.

Dairesel bağlantılı listenin belirli bir konumuna ekleme' loading='lazy' title=

Dairesel bağlantılı listede belirli bir konuma ekleme

Adım adım yaklaşım:

Eğer son öyle nullptr Ve poz değil 1 yazdır ' Geçersiz konum! '.
Aksi halde verilen verilerle yeni bir Düğüm oluşturun.
Başlangıçta Ekle: Pos 1 ise güncelleme işaretçileri ve en son geri dönün.
Geçiş Listesi: Ekleme noktasını bulmak için döngü yapın; print 'Geçersiz konum!' sınırların dışındaysa.
Düğüm Ekle: Yeni düğümü eklemek için işaretçileri güncelleyin.
Son Güncelleme: Güncellemenin sonuna eklenirse son .

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

Çıkış

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

Zaman Karmaşıklığı: O(n) belirli konumu bulmak için listeyi geçmemiz gerekiyor.
Yardımcı Alan: Ç(1)

Test Oluştur

TechCodeview