Açılmamış Bağlantılı Liste | Set 1 (Giriş)
Dizi ve bağlantılı liste gibi, çözülmüş Bağlantılı Liste de doğrusal bir veri yapısıdır ve bağlantılı listenin bir çeşididir.
Neden yayınlanmamış bağlantılı listeye ihtiyacımız var?
Bağlantılı listelerin dizilere göre en büyük avantajlarından biri, herhangi bir konuma öğe eklemenin yalnızca O(1) gerektirmesidir. Ancak buradaki önemli nokta, bağlantılı bir listedeki bir öğeyi aramak için O(n) alınmasıdır. Bu nedenle, arama sorununu çözmek, yani öğeyi arama süresini kısaltmak için, yuvarlanmamış bağlantılı listeler kavramı öne sürüldü. Açılmamış bağlantılı liste, her düğümde birden fazla öğe depolayarak basit bağlantılı listelere kıyasla bellek yükünü azalttığı için hem dizinin hem de bağlantılı listenin avantajlarını kapsar ve ayrıca bağlantılı listeninki gibi hızlı ekleme ve silme avantajına sahiptir.
Avantajları:
- Önbellek davranışı nedeniyle doğrusal arama, yuvarlanmamış bağlantılı listelerde çok daha hızlıdır.
- Sıradan bağlantılı listeyle karşılaştırıldığında işaretçiler/referanslar için daha az depolama alanı gerektirir.
- Ekleme silme ve geçiş gibi işlemleri sıradan bağlantılı listelerden daha hızlı gerçekleştirir (çünkü arama daha hızlıdır).
Dezavantajları:
- Düğüm başına ek yük, tek bağlantılı listelere kıyasla nispeten yüksektir. Aşağıdaki koddaki örnek bir düğüme bakın
Örnek: Diyelim ki 8 elementimiz var, yani sqrt(8)=2.82, bu da 3'e yuvarlanıyor. Yani her blok 3 element saklayacak. Dolayısıyla 8 elemanı depolamak için 3 blok oluşturulacak, bunlardan ilk iki blok 3 eleman depolayacak ve son blok 2 eleman depolayacaktır.
Açılmamış bağlantılı listelerde arama nasıl daha iyi hale gelir?
Yani yukarıdaki örneği ele alarak listedeki 7. elemanı aramak istersek blok listesini 7. elemanı içeren blok listesine geçiririz. sqrt(n) bloktan fazla gitmediğini bulduğumuz için yalnızca O(sqrt(n)) alır.
Basit Uygulama:
Aşağıdaki program, her birinde değişken sayıda öğe içeren 3 düğümden oluşan basit, açılmamış bağlantılı bir liste oluşturur. Ayrıca oluşturulan listeyi de dolaşır.
C++ // C++ program to implement unrolled linked list // and traversing it. #include using namespace std ; #define maxElements 4 // Unrolled Linked List Node class Node { public : int numElements ; int array [ maxElements ]; Node * next ; }; /* Function to traverse an unrolled linked list and print all the elements*/ void printUnrolledList ( Node * n ) { while ( n != NULL ) { // Print elements in current node for ( int i = 0 ; i < n -> numElements ; i ++ ) cout < < n -> array [ i ] < < ' ' ; // Move to next node n = n -> next ; } } // Program to create an unrolled linked list // with 3 Nodes int main () { Node * head = NULL ; Node * second = NULL ; Node * third = NULL ; // allocate 3 Nodes head = new Node (); second = new Node (); third = new Node (); // Let us put some values in second node (Number // of values must be less than or equal to // maxElement) head -> numElements = 3 ; head -> array [ 0 ] = 1 ; head -> array [ 1 ] = 2 ; head -> array [ 2 ] = 3 ; // Link first Node with the second Node head -> next = second ; // Let us put some values in second node (Number // of values must be less than or equal to // maxElement) second -> numElements = 3 ; second -> array [ 0 ] = 4 ; second -> array [ 1 ] = 5 ; second -> array [ 2 ] = 6 ; // Link second Node with the third Node second -> next = third ; // Let us put some values in third node (Number // of values must be less than or equal to // maxElement) third -> numElements = 3 ; third -> array [ 0 ] = 7 ; third -> array [ 1 ] = 8 ; third -> array [ 2 ] = 9 ; third -> next = NULL ; printUnrolledList ( head ); return 0 ; } // This is code is contributed by rathbhupendra
C // C program to implement unrolled linked list // and traversing it. #include #include #define maxElements 4 // Unrolled Linked List Node struct Node { int numElements ; int array [ maxElements ]; struct Node * next ; }; /* Function to traverse an unrolled linked list and print all the elements*/ void printUnrolledList ( struct Node * n ) { while ( n != NULL ) { // Print elements in current node for ( int i = 0 ; i < n -> numElements ; i ++ ) printf ( '%d ' n -> array [ i ]); // Move to next node n = n -> next ; } } // Program to create an unrolled linked list // with 3 Nodes int main () { struct Node * head = NULL ; struct Node * second = NULL ; struct Node * third = NULL ; // allocate 3 Nodes head = ( struct Node * ) malloc ( sizeof ( struct Node )); second = ( struct Node * ) malloc ( sizeof ( struct Node )); third = ( struct Node * ) malloc ( sizeof ( struct Node )); // Let us put some values in second node (Number // of values must be less than or equal to // maxElement) head -> numElements = 3 ; head -> array [ 0 ] = 1 ; head -> array [ 1 ] = 2 ; head -> array [ 2 ] = 3 ; // Link first Node with the second Node head -> next = second ; // Let us put some values in second node (Number // of values must be less than or equal to // maxElement) second -> numElements = 3 ; second -> array [ 0 ] = 4 ; second -> array [ 1 ] = 5 ; second -> array [ 2 ] = 6 ; // Link second Node with the third Node second -> next = third ; // Let us put some values in third node (Number // of values must be less than or equal to // maxElement) third -> numElements = 3 ; third -> array [ 0 ] = 7 ; third -> array [ 1 ] = 8 ; third -> array [ 2 ] = 9 ; third -> next = NULL ; printUnrolledList ( head ); return 0 ; }
Java // Java program to implement unrolled // linked list and traversing it. import java.util.* ; class GFG { static final int maxElements = 4 ; // Unrolled Linked List Node static class Node { int numElements ; int [] array = new int [ maxElements ] ; Node next ; }; // Function to traverse an unrolled // linked list and print all the elements static void printUnrolledList ( Node n ) { while ( n != null ) { // Print elements in current node for ( int i = 0 ; i < n . numElements ; i ++ ) System . out . print ( n . array [ i ] + ' ' ); // Move to next node n = n . next ; } } // Program to create an unrolled linked list // with 3 Nodes public static void main ( String [] args ) { Node head = null ; Node second = null ; Node third = null ; // Allocate 3 Nodes head = new Node (); second = new Node (); third = new Node (); // Let us put some values in second // node (Number of values must be // less than or equal to maxElement) head . numElements = 3 ; head . array [ 0 ] = 1 ; head . array [ 1 ] = 2 ; head . array [ 2 ] = 3 ; // Link first Node with the // second Node head . next = second ; // Let us put some values in // second node (Number of values // must be less than or equal to // maxElement) second . numElements = 3 ; second . array [ 0 ] = 4 ; second . array [ 1 ] = 5 ; second . array [ 2 ] = 6 ; // Link second Node with the third Node second . next = third ; // Let us put some values in third // node (Number of values must be // less than or equal to maxElement) third . numElements = 3 ; third . array [ 0 ] = 7 ; third . array [ 1 ] = 8 ; third . array [ 2 ] = 9 ; third . next = null ; printUnrolledList ( head ); } } // This code is contributed by amal kumar choubey
Python3 # Python3 program to implement unrolled # linked list and traversing it. maxElements = 4 # Unrolled Linked List Node class Node : def __init__ ( self ): self . numElements = 0 self . array = [ 0 for i in range ( maxElements )] self . next = None # Function to traverse an unrolled linked list # and print all the elements def printUnrolledList ( n ): while ( n != None ): # Print elements in current node for i in range ( n . numElements ): print ( n . array [ i ] end = ' ' ) # Move to next node n = n . next # Driver Code if __name__ == '__main__' : head = None second = None third = None # Allocate 3 Nodes head = Node () second = Node () third = Node () # Let us put some values in second # node (Number of values must be # less than or equal to # maxElement) head . numElements = 3 head . array [ 0 ] = 1 head . array [ 1 ] = 2 head . array [ 2 ] = 3 # Link first Node with the second Node head . next = second # Let us put some values in second node # (Number of values must be less than # or equal to maxElement) second . numElements = 3 second . array [ 0 ] = 4 second . array [ 1 ] = 5 second . array [ 2 ] = 6 # Link second Node with the third Node second . next = third # Let us put some values in third node # (Number of values must be less than # or equal to maxElement) third . numElements = 3 third . array [ 0 ] = 7 third . array [ 1 ] = 8 third . array [ 2 ] = 9 third . next = None printUnrolledList ( head ) # This code is contributed by rutvik_56
C# // C# program to implement unrolled // linked list and traversing it. using System ; class GFG { static readonly int maxElements = 4 ; // Unrolled Linked List Node class Node { public int numElements ; public int [] array = new int [ maxElements ]; public Node next ; }; // Function to traverse an unrolled // linked list and print all the elements static void printUnrolledList ( Node n ) { while ( n != null ) { // Print elements in current node for ( int i = 0 ; i < n . numElements ; i ++ ) Console . Write ( n . array [ i ] + ' ' ); // Move to next node n = n . next ; } } // Program to create an unrolled linked list // with 3 Nodes public static void Main ( String [] args ) { Node head = null ; Node second = null ; Node third = null ; // Allocate 3 Nodes head = new Node (); second = new Node (); third = new Node (); // Let us put some values in second // node (Number of values must be // less than or equal to maxElement) head . numElements = 3 ; head . array [ 0 ] = 1 ; head . array [ 1 ] = 2 ; head . array [ 2 ] = 3 ; // Link first Node with the // second Node head . next = second ; // Let us put some values in // second node (Number of values // must be less than or equal to // maxElement) second . numElements = 3 ; second . array [ 0 ] = 4 ; second . array [ 1 ] = 5 ; second . array [ 2 ] = 6 ; // Link second Node with the third Node second . next = third ; // Let us put some values in third // node (Number of values must be // less than or equal to maxElement) third . numElements = 3 ; third . array [ 0 ] = 7 ; third . array [ 1 ] = 8 ; third . array [ 2 ] = 9 ; third . next = null ; printUnrolledList ( head ); } } // This code is contributed by Rajput-Ji
JavaScript < script > // JavaScript program to implement unrolled // linked list and traversing it. const maxElements = 4 ; // Unrolled Linked List Node class Node { constructor () { this . numElements = 0 ; this . array = new Array ( maxElements ); this . next = null ; } } // Function to traverse an unrolled // linked list and print all the elements function printUnrolledList ( n ) { while ( n != null ) { // Print elements in current node for ( var i = 0 ; i < n . numElements ; i ++ ) document . write ( n . array [ i ] + ' ' ); // Move to next node n = n . next ; } } // Program to create an unrolled linked list // with 3 Nodes var head = null ; var second = null ; var third = null ; // Allocate 3 Nodes head = new Node (); second = new Node (); third = new Node (); // Let us put some values in second // node (Number of values must be // less than or equal to maxElement) head . numElements = 3 ; head . array [ 0 ] = 1 ; head . array [ 1 ] = 2 ; head . array [ 2 ] = 3 ; // Link first Node with the // second Node head . next = second ; // Let us put some values in // second node (Number of values // must be less than or equal to // maxElement) second . numElements = 3 ; second . array [ 0 ] = 4 ; second . array [ 1 ] = 5 ; second . array [ 2 ] = 6 ; // Link second Node with the third Node second . next = third ; // Let us put some values in third // node (Number of values must be // less than or equal to maxElement) third . numElements = 3 ; third . array [ 0 ] = 7 ; third . array [ 1 ] = 8 ; third . array [ 2 ] = 9 ; third . next = null ; printUnrolledList ( head ); < /script>
Çıkış
1 2 3 4 5 6 7 8 9
Karmaşıklık Analizi:
Bu yazımızda yayınlanmamış bir listeyi ve avantajlarını tanıttık. Ayrıca listede nasıl gezinileceğini de gösterdik. Bir sonraki makalede ekleme silme işlemini ve maxElements/numElements değerlerini detaylı olarak tartışacağız.
Açılmamış Bağlantılı Listeye Ekleme
Test Oluştur
Hoşunuza Gidebilir
En Makaleler
