Dairesel Tek Bağlantılı 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:
- 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şı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.
- 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ı 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 .
#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 );
Çı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)
