A bağlantılı liste veri öğelerini depolamak için kullandığımız bir tür doğrusal dinamik veri yapısıdır. Diziler aynı zamanda veri öğelerinin sürekli bellek bloklarında saklandığı bir tür doğrusal veri yapısıdır.
Dizilerden farklı olarak bağlantılı listenin, veri öğelerini bitişik bellek bölgelerinde veya bloklarında saklaması gerekmez.
A bağlantılı liste 'Düğümler' olarak bilinen ve iki parçaya bölünmüş öğelerden oluşur. İlk bileşen asıl veriyi sakladığımız kısım, ikincisi ise bir sonraki düğüme ait işaretçiyi sakladığımız kısımdır. Bu tür bir yapıya '' denir. tek bağlantılı liste .'
C++'da Bağlantılı Liste
Bu eğitimde tek bağlantılı listeyi derinlemesine inceleyeceğiz.
java dize karşılaştırması
Tek bağlantılı listenin yapısı aşağıdaki şemada gösterilmektedir.
- Yukarıdaki bölümde gördüğümüz gibi bağlantılı listenin ilk düğümü 'baş', son düğümü ise 'kuyruk' olarak adlandırılıyor. Bunun nedeni, son düğümde hiçbir bellek adresinin belirtilmemesidir, bağlı listenin son düğümünün boş bir sonraki işaretçisi olacaktır.
- Her düğüm bir sonraki düğüme işaret eden bir işaretçi içerdiğinden bağlantılı listedeki veri öğelerinin bitişik konumlarda tutulmasına gerek yoktur. Düğümler hafıza boyunca dağılmış olabilir. Her düğüm kendisinden sonrakinin adresine sahip olduğundan, düğümlere istediğimiz zaman erişebiliriz.
- Veri öğelerini bağlı listeye hızlı bir şekilde ekleyebilir ve kaldırabiliriz. Sonuç olarak bağlantılı liste dinamik olarak artabilir veya daralabilir. Bağlantılı listenin içerebileceği maksimum miktarda veri öğesi yoktur. Sonuç olarak, RAM mevcut olduğu sürece bağlantılı listeye istediğimiz kadar veri öğesi ekleyebiliriz.
- Bağlantılı listede kaç öğeye ihtiyacımız olduğunu önceden belirtmemiz gerekmediği için bağlantılı liste, eklenmesi ve silinmesi kolay olmasının yanı sıra hafıza alanından da tasarruf sağlar. Bağlantılı bir liste tarafından kullanılan tek alan, işaretçiyi bir sonraki düğüme depolamaktır ve bu da bir miktar maliyet ekler.
Bunu takiben bağlantılı bir listede gerçekleştirilebilecek çeşitli işlemleri gözden geçireceğiz.
1) Ekleme
Bağlantılı liste, kendisine ekleme eylemiyle genişletilir. Bağlantılı listenin yapısı göz önüne alındığında basit gibi görünse de, her veri öğesi eklendiğinde eklediğimiz yeni öğenin önceki ve sonraki düğümlerinin sonraki işaretçilerini değiştirmemiz gerektiğini biliyoruz.
Yeni veri öğesinin nereye ekleneceği düşünülmesi gereken ikinci husustur.
Yasemin Davis'in çocukluğu
Bağlantılı listeye bir veri öğesinin eklenebileceği üç yer vardır.
A. Bağlantılı listeyle başlayarak
Aşağıda 2->4->6->8->10 sayılarının bağlantılı bir listesi bulunmaktadır. Listedeki ilk düğüm olarak yeni bir düğüm 1 eklersek, düğüm 2'yi işaret eden kafa artık düğüm 1'i işaret edecek ve düğüm 1'in bir sonraki işaretçisi aşağıdaki çizimde gösterildiği gibi düğüm 2'nin hafıza adresine sahip olacaktır. .
Sonuç olarak yeni bağlantılı liste 1->2->4->6->8->10 şeklindedir.
B. Verilen Düğümden sonra
Bu durumda bize bir düğüm veriliyor ve onun arkasına yeni bir düğüm eklemeliyiz. a->b->c->d->e bağlantılı listesine c düğümünden sonra f düğümü eklenirse bağlantılı liste aşağıdaki gibi görünecektir:
dize alt dizesi
Bu nedenle belirtilen düğümün yukarıdaki diyagramda mevcut olup olmadığını kontrol ediyoruz. Varsa, yeni bir f düğümü oluşturulur. Bundan sonra, c düğümünün bir sonraki işaretçisini yepyeni f düğümüne yönlendiririz. F düğümünün bir sonraki işaretçisi artık d düğümünü işaret eder.
C. Bağlantılı Liste'nin son öğesi
Üçüncü durumda bağlı listenin sonuna yeni bir düğüm eklenir. Aşağıdaki bağlantılı listeyi dikkate alın: a->b->c->d->e, sonuna f düğümü eklenerek. Düğümü ekledikten sonra bağlantılı liste bu şekilde görünecektir.
Sonuç olarak yeni bir f düğümü oluşturuyoruz. Null'a giden kuyruk işaretçisi daha sonra f'ye işaret eder ve f düğümünün bir sonraki işaretçisi null'a işaret eder. Aşağıdaki Programlama dilinde, üç tür ekleme fonksiyonunun tümünü oluşturduk.
Bağlantılı liste, C++'da bir yapı veya sınıf olarak bildirilebilir. Bir yapı olarak bildirilen bağlantılı liste, klasik bir C tarzı ifadedir. Bağlantılı liste, modern C++'da, özellikle standart şablon kitaplığı kullanıldığında bir sınıf olarak kullanılır.
Yapı, aşağıdaki uygulamada bağlantılı bir liste bildirmek ve oluşturmak için kullanıldı. Üyeleri veri ve aşağıdaki öğeye işaretçi olacaktır.
C++ Programı:
#include using namespace std; struct Node { int data; struct Node *next; }; void push ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; newNode1 -> data = nodeData; newNode1 -> next = (*head); (*head) = newNode1; } void insertAfter ( struct Node* prevNode, int nodeData ) { if ( prevNode == NULL ) { cout <data = nodedata; newnode1 -> next = prevNode -> next; prevNode -> next = newNode1; } void append ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; struct Node *last = *head; newNode1 -> data = nodeData; newNode1 -> next = NULL; if ( *head == NULL ) { *head = newNode1; return; } while ( last -> next != NULL ) last = last -> next; last -> next = newNode1; return; } void displayList ( struct Node *node ) { while ( node != NULL ) { cout <data <'; node="node" -> next; } if ( node== NULL) cout<next, 55 ); cout << 'final linked list: ' endl; displaylist (head); return 0; } < pre> <p> <strong>Output:</strong> </p> <pre> Final linked list: 35-->25-->55-->15-->45-->null </pre> <h3>2) Deletion</h3> <p>Similar to insertion, deleting a node from a linked list requires many points from which the node might be eliminated. We can remove the linked list's first, last, or kth node at random. We must correctly update the next pointer and all other linked list pointers in order to maintain the linked list after deletion.</p> <p>In the following C++ implementation, we have two deletion methods: deleting the list's initial node and deleting the list's last node. We begin by adding nodes to the head of the list. The list's contents are then shown following each addition and deletion.</p> <p> <strong>C++ Program:</strong> </p> <pre> #include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <'; if ( temp="=" null ) cout << 'null' endl; head="deletingFirstNode" (head); 'linked list after deleting node' < next <data cout<<'null'<<endl; last data 'null'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data></pre></next,></data></data> 2) Silme
Eklemeye benzer şekilde, bağlantılı bir listeden bir düğümün silinmesi, düğümün çıkarılabileceği birçok noktayı gerektirir. Bağlantılı listenin ilk, son veya k. düğümünü rastgele kaldırabiliriz. Bağlantılı listeyi silme işleminden sonra korumak için sonraki işaretçiyi ve diğer tüm bağlantılı liste işaretçilerini doğru şekilde güncellememiz gerekir.
Aşağıdaki C++ uygulamasında iki silme yöntemimiz vardır: listenin ilk düğümünü silmek ve listenin son düğümünü silmek. Listenin başına düğümleri ekleyerek başlıyoruz. Listenin içeriği her ekleme ve silme işleminden sonra gösterilir.
C++ Programı:
gezinilen css
#include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <\'; if ( temp="=" null ) cout << \'null\' endl; head="deletingFirstNode" (head); \'linked list after deleting node\' < next <data cout<<\'null\'<<endl; last data \'null\'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data> Düğüm Sayısı
Bağlantılı listede gezinirken düğüm sayısını sayma işlemi gerçekleştirilebilir. Önceki yaklaşımda, bir düğüm eklememiz/silmemiz veya bağlantılı listenin içeriğini görüntülememiz gerektiğinde, bağlantılı listeyi baştan baştan geçmemiz gerektiğini gördük.
Bir sayaç ayarlamak ve her bir düğümü geçerken artırmak bize bağlı listedeki düğüm sayısını verecektir.
java concat dizeleri
Dizi ve Bağlantılı liste arasındaki farklar:
| Sıralamak | Bağlantılı liste |
|---|---|
| Dizilerin tanımlanmış bir boyutu vardır. | Bağlantılı listenin boyutu değişkendir. |
| Yeni bir öğe eklemek zordur. | Ekleme ve silme daha basittir. |
| Erişime rastgele izin verilir. | Rastgele erişim mümkün değildir. |
| Öğeler nispeten yakın veya bitişiktir. | Elemanlar bitişik değildir. |
| Aşağıdaki işaretçi için ek alana gerek yoktur. | Aşağıdaki işaretçi ek bellek gerektirir. |
İşlevsellik
Bağlantılı listeler ve diziler, nesneleri tutan doğrusal veri yapıları olduğundan, uygulamaların çoğu için benzer şekillerde kullanılabilirler.
Aşağıda bağlantılı liste uygulamalarının bazı örnekleri verilmiştir:
- Yığınlar ve kuyruklar bağlantılı listeler kullanılarak uygulanabilir.
- Grafikleri bitişiklik listeleri olarak ifade etmemiz gerektiğinde, bunları uygulamak için bağlantılı bir liste kullanabiliriz.
- Matematiksel bir polinomu içermek için bağlantılı bir liste de kullanabiliriz.
- Karma durumunda, kovaları uygulamak için bağlantılı listeler kullanılır.
- Bir program dinamik bellek tahsisi gerektirdiğinde bağlantılı listelerden yararlanabiliriz çünkü bağlantılı listeler bu durumda daha verimlidir.
Çözüm
Bağlantılı listeler, veri öğelerini doğrusal fakat bitişik olmayan bir biçimde tutmak için kullanılan veri yapılarıdır. Bağlantılı liste, her biri iki bileşene sahip düğümlerden oluşur. İlk bileşen verilerden oluşurken, ikinci yarıda listenin bir sonraki üyesinin hafıza adresini saklayan bir işaretçi bulunur.
Bağlantılı listenin sona erdiğinin bir işareti olarak listedeki son öğenin sonraki işaretçisi NULL olarak ayarlanır. Baş, listedeki ilk öğedir. Bağlantılı liste, ekleme, silme, geçiş vb. gibi çeşitli eylemlere izin verir. Dinamik bellek tahsisi için bağlantılı listeler dizilere tercih edilir.
Bağlantılı listelerin yazdırılması veya üzerinden geçilmesi zordur çünkü öğelere diziler gibi rastgele erişemiyoruz. Dizilerle karşılaştırıldığında ekleme-silme işlemleri daha ucuzdur.
Bu derste doğrusal bağlantılı listeler hakkında bilinmesi gereken her şeyi öğrendik. Bağlantılı listeler ayrıca çift bağlantılı veya dairesel olabilir. Gelecek eğitimlerimizde bu listeleri detaylı olarak inceleyeceğiz.