Menü

Resimli C ++ 'da Bağlantılı Liste Veri Yapısı

  • Ana
  • Diğer
  • Resimli C ++ 'da Bağlantılı Liste Veri Yapısı

linked list data structure c with illustration

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

C ++ 'da Bağlantılı Listenin Ayrıntılı Bir Çalışması.

Bağlantılı bir liste, veri öğelerini depolamak için doğrusal bir dinamik veri yapısıdır. Temel C ++ ile ilgili önceki konularımızda dizileri zaten görmüştük. Dizilerin, veri öğelerini bitişik konumlarda depolayan doğrusal bir veri yapısı olduğunu da biliyoruz.

Dizilerden farklı olarak, bağlantılı liste veri öğelerini bitişik bellek konumlarında saklamaz.

Bağlantılı bir liste, iki parça içeren 'Düğümler' adı verilen öğelerden oluşur. İlk kısım gerçek verileri depolar ve ikinci kısım bir sonraki düğüme işaret eden bir işaretçiye sahiptir. Bu yapı genellikle 'Tek bağlantılı liste' olarak adlandırılır.

oracle sql sorgular cevaplı örnekler pdf

=> En İyi C ++ Eğitim Öğreticilerine Buradan Göz Atın.

BAĞLANTILI LİSTE

Ne öğreneceksin:

C ++ 'da Bağlantılı Liste

Bu eğitimde tek başına bağlantılı listeye ayrıntılı olarak bakacağız.

Aşağıdaki şema, tekil bağlantılı bir listenin yapısını göstermektedir.

tek bağlantılı bir listenin yapısı

Yukarıda gösterildiği gibi, bağlantılı listenin ilk düğümüne 'baş', son düğüme ise 'Kuyruk' denir. Gördüğümüz gibi, bağlantılı listenin son düğümü, işaret edilen herhangi bir bellek adresine sahip olmayacağından bir sonraki işaretçisini boş olarak alacaktır.

Her düğüm bir sonraki düğüme bir işaretçiye sahip olduğundan, bağlantılı listedeki veri öğelerinin bitişik konumlarda depolanması gerekmez. Düğümler hafızaya dağılabilir. Her düğüm bir sonraki düğümün adresine sahip olacağından, düğümlere istediğimiz zaman erişebiliriz.

Bağlantılı listeye veri öğeleri ekleyebilir ve listeden öğeleri kolayca silebiliriz. Böylece bağlantılı listeyi dinamik olarak büyütmek veya küçültmek mümkündür. Bağlantılı listede kaç tane veri öğesi olabileceğine dair bir üst sınır yoktur. Hafıza mevcut olduğu sürece, bağlantılı listeye çok sayıda veri öğesi ekleyebiliriz.

Bağlantılı liste, kolay ekleme ve silme işleminin yanı sıra, bağlantılı listede kaç öğeye ihtiyacımız olduğunu önceden belirtmemiz gerekmediğinden bellek alanını da boşa harcamaz. Bağlantılı listenin kapladığı tek alan, biraz ek yük ekleyen bir sonraki düğüme işaretçiyi depolamak içindir.

Ardından, bağlantılı bir listede gerçekleştirilebilecek çeşitli işlemleri tartışacağız.

Operasyonlar

Diğer veri yapıları gibi, bağlantılı liste için de çeşitli işlemler gerçekleştirebiliriz. Ancak elemana, arada bir yerde olsa bile doğrudan alt simge kullanarak erişebildiğimiz dizilerden farklı olarak, aynı rasgele erişimi bağlantılı bir listeyle yapamayız.

Herhangi bir düğüme erişmek için, bağlantılı listeyi baştan geçmemiz gerekir ve ancak o zaman istenen düğüme erişebiliriz. Dolayısıyla, bağlantılı listeden rastgele verilere erişmenin pahalı olduğu kanıtlanmıştır.

Bağlantılı bir liste üzerinde çeşitli işlemleri aşağıda belirtildiği gibi gerçekleştirebiliriz:

# 1) Ekleme

Bağlı listenin ekleme işlemi, bağlantılı listeye bir öğe ekler. Bağlantılı listenin yapısı göz önüne alındığında kulağa basit gelse de, bağlantılı listeye bir veri öğesi eklendiğinde, eklediğimiz yeni öğenin önceki ve sonraki düğümlerinin sonraki işaretçilerini değiştirmemiz gerektiğini biliyoruz.

Dikkate almamız gereken ikinci şey, yeni veri öğesinin ekleneceği yerdir.

Bağlantılı listede bir veri öğesinin eklenebileceği üç pozisyon vardır.

# 1) Bağlantılı listenin başında

Bağlantılı bir liste aşağıda gösterilmiştir: 2-> 4-> 6-> 8-> 10. Listenin ilk düğümü olarak yeni bir düğüm 1 eklemek istersek, düğüm 2'yi gösteren kafa şimdi 1'i gösterecek ve düğüm 1'in bir sonraki göstericisi aşağıda gösterildiği gibi düğüm 2'nin bellek adresine sahip olacaktır. şekil.

Başlangıçta ekleme

Böylece yeni bağlantılı liste 1-> 2-> 4-> 6-> 8-> 10 olur.

# 2) Verilen Düğümden Sonra

android için iyi ücretsiz müzik indirici

Burada bir düğüm verilir ve verilen düğümden sonra yeni bir düğüm eklememiz gerekir. Aşağıdaki bağlantılı listede a-> b-> c-> d -> e, c düğümünden sonra bir f düğümü eklemek istersek, bağlantılı liste aşağıdaki gibi görünecektir:

Belirli bir düğümden sonra ekleme

Böylece yukarıdaki diyagramda verilen düğümün mevcut olup olmadığını kontrol ederiz. Varsa, yeni bir f düğümü oluştururuz. Sonra c düğümünün bir sonraki işaretçisini yeni f düğümünü gösterecek şekilde işaret ederiz. F düğümünün bir sonraki işaretçisi şimdi d düğümünü gösterir.

# 3) Bağlantılı Listenin sonunda

Üçüncü durumda, bağlantılı listenin sonuna yeni bir düğüm ekliyoruz. Aynı bağlantılı listeye sahip olduğumuzu düşünün a-> b-> c-> d-> e ve listenin sonuna bir f düğümü eklememiz gerekiyor. Bağlantılı liste, düğüm eklendikten sonra aşağıda gösterildiği gibi görünecektir.

Bağlantılı listenin sonuna ekleme

Böylece yeni bir f düğümü oluşturuyoruz. Daha sonra, null'u gösteren kuyruk işaretçisi f'yi ve bir sonraki f düğümünün göstericisi, boşu işaret eder. Aşağıdaki C ++ programında üç tür ekleme işlevinin tümünü uyguladık.

C ++ 'da, bağlantılı bir listeyi yapı veya sınıf olarak tanımlayabiliriz. Bağlantılı listeyi bir yapı olarak bildirmek, geleneksel bir C tarzı beyandır. Modern C ++ 'da, çoğunlukla standart şablon kitaplığı kullanılırken, sınıf olarak bağlantılı bir liste kullanılır.

Aşağıdaki programda, bağlantılı bir liste bildirmek ve oluşturmak için yapı kullandık. Üyeleri olarak bir sonraki elemana veri ve işaretçiye sahip olacaktır.

#include using namespace std; // A linked list node struct Node { int data; struct Node *next; }; //insert a new node in front of the list void push(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; /* 2. assign data to node */ newNode->data = node_data; /* 3. set next of new node as head */ newNode->next = (*head); /* 4. move the head to point to the new node */ (*head) = newNode; } //insert new node after a given node void insertAfter(struct Node* prev_node, int node_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { coutnext = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = newNode; } /* insert new node at the end of the linked list */ void append(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; struct Node *last = *head; /* used in step 5*/ /* 2. assign data to the node */ newNode->data = node_data; /* 3. set next pointer of new node to null as its the last node*/ newNode->next = NULL; /* 4. if list is empty, new node becomes first node */ if (*head == NULL) { *head = newNode; return; } /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = newNode; return; } // display linked list contents void displayList(struct Node *node) { //traverse the list to display each node while (node != NULL) { coutnext; } if(node== NULL) cout

Çıktı:

Nihai bağlantılı liste:

30–> 20–> 50–> 10–> 40–> boş

Daha sonra, bağlantılı liste ekleme işlemini Java'da gerçekleştiriyoruz. Java dilinde, bağlantılı liste bir sınıf olarak uygulanır. Aşağıdaki program mantıksal olarak C ++ programına benzer, tek fark, bağlantılı liste için bir sınıf kullanmamızdır.

class LinkedList { Node head; // head of list //linked list node declaration class Node { int data; Node next; Node(int d) {data = d; next = null; } } /* Insert a new node at the front of the list */ public void push(int new_data) { //allocate and assign data to the node Node newNode = new Node(new_data); //new node becomes head of linked list newNode.next = head; //head points to new node head = newNode; } // Given a node,prev_node insert node after prev_node public void insertAfter(Node prev_node, int new_data) { //check if prev_node is null. if (prev_node == null) { System.out.println('The given node is required and cannot be null'); return; } //allocate node and assign data to it Node newNode = new Node(new_data); //next of new Node is next of prev_node newNode.next = prev_node.next; //prev_node->next is the new node. prev_node.next = newNode; } //inserts a new node at the end of the list public void append(intnew_data) { //allocate the node and assign data Node newNode = new Node(new_data); //if linked list is empty, then new node will be the head if (head == null) { head = new Node(new_data); return; } //set next of new node to null as this is the last node newNode.next = null; // if not the head node traverse the list and add it to the last Node last = head; while (last.next != null) last = last.next; //next of last becomes new node last.next = newNode; return; } //display contents of linked list public void displayList() { Node pnode = head; while (pnode != null) { System.out.print(pnode.data+'-->'); pnode = pnode.next; } if(pnode == null) System.out.print('null'); } } //Main class to call linked list class functions and construct a linked list class Main{ public static void main(String() args) { /* create an empty list */ LinkedList lList = new LinkedList(); // Insert 40. lList.append(40); // Insert 20 at the beginning. lList.push(20); // Insert 10 at the beginning. lList.push(10); // Insert 50 at the end. lList.append(50); // Insert 30, after 20. lList.insertAfter(lList.head.next, 30); System.out.println(' Final linked list: '); lList. displayList (); } }

Çıktı:

Nihai bağlantılı liste:

10–> 20–> 30–> 40–> 50–> boş

Hem yukarıdaki C ++ programında hem de Java'da, listenin önüne, listenin sonuna ve bir düğümde verilen listelerin arasına bir düğüm eklemek için ayrı işlevlerimiz vardır. Sonunda, üç yöntemi de kullanarak oluşturulan listenin içeriğini yazdırıyoruz.

# 2) Silme

Ekleme gibi, bağlantılı bir listeden bir düğümü silmek, düğümün silinebileceği çeşitli konumları da içerir. Bağlantılı listeden ilk düğümü, son düğümü veya rastgele bir k'inci düğümü silebiliriz. Silme işleminden sonra, bağlantılı listeyi sağlam tutmak için sonraki işaretçiyi ve bağlantılı listedeki diğer işaretçileri uygun şekilde ayarlamamız gerekir.

Aşağıdaki C ++ uygulamasında, listedeki ilk düğümü silme ve listedeki son düğümü silme gibi iki silme yöntemi verdik. Önce başlığa düğüm ekleyerek bir liste oluşturuyoruz. Daha sonra ekleme ve her silme işleminden sonra listenin içeriğini görüntüleriz.

#include using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; //delete first node in the linked list Node* deleteFirstNode(struct Node* head) { if (head == NULL) return NULL; // Move the head pointer to the next node Node* tempNode = head; head = head->next; delete tempNode; return head; } //delete last node from linked list Node* removeLastNode(struct Node* head) { if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // first find second last node Node* second_last = head; while (second_last->next->next != NULL) second_last = second_last->next; // Delete the last node delete (second_last->next); // set next of second_last to null second_last->next = NULL; return head; } // create linked list by adding nodes at head void push(struct Node** head, int new_data) { struct Node* newNode = new Node; newNode->data = new_data; newNode->next = (*head); (*head) = newNode; } // main function int main() { /* Start with the empty list */ Node* head = NULL; // create linked list push(&head, 2); push(&head, 4); push(&head, 6); push(&head, 8); push(&head, 10); Node* temp; cout<<'Linked list created '

Çıktı:

Bağlı liste oluşturuldu

10–> 8–> 6–> 4–> 2–
> BOŞ

Baş düğümü sildikten sonra bağlı liste

8–> 6–> 4–> 2–
> BOŞ

Son düğümü sildikten sonra bağlı liste

8–> 6–> 4–> NULL

Sonraki, bağlantılı listeden düğümleri silmek için Java uygulamasıdır. Uygulama mantığı, C ++ programında kullanılanla aynıdır. Tek fark, bağlantılı listenin bir sınıf olarak bildirilmesidir.

class Main { // Linked list node / static class Node { int data; Node next; }; // delete first node of linked list static Node deleteFirstNode(Node head) { if (head == null) return null; // Move the head pointer to the next node Node temp = head; head = head.next; return head; } // Delete the last node in linked list static Node deleteLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } // search for second last node Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; // set next of second last to null second_last.next = null; return head; } // Add nodes to the head and create linked list static Node push(Node head, int new_data) { Node newNode = new Node(); newNode.data = new_data; newNode.next = (head); (head) = newNode; return head; } //main function public static void main(String args()) { // Start with the empty list / Node head = null; //create linked list head = push(head, 1); head = push(head, 3); head = push(head, 5); head = push(head, 7); head = push(head, 9); Node temp; System.out.println('Linked list created :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteFirstNode(head); System.out.println('Linked list after deleting head node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteLastNode(head); System.out.println('Linked list after deleting last node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); } }

Çıktı:

Bağlı liste oluşturuldu:

9–> 7–> 5–> 3–> 1–
> boş

Baş düğümü sildikten sonra bağlı liste:

7–> 5–> 3–> 1–
> boş

Son düğümü sildikten sonra bağlı liste:

7–> 5–> 3–> boş

Düğüm Sayısını Say

Bağlantılı listeyi dolaşırken düğüm sayısını sayma işlemi gerçekleştirilebilir. Yukarıdaki uygulamada, 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 dolaşmamız gerektiğini zaten görmüştük.

Bir sayacı tutmak ve her bir düğümü geçerken onu artırmak, bize bağlantılı listede bulunan düğümlerin sayısını verecektir. Okuyucuların uygulaması için bu programı bırakacağız.

Diziler ve Bağlantılı Listeler

Bağlantılı listenin işlemlerini ve uygulanmasını gördükten sonra, dizilerin ve bağlantılı listenin birbirleriyle karşılaştırıldığında ne kadar adil olduğunu karşılaştıralım.

DizilerBağlı listeler
Dizilerin boyutu sabittirBağlı liste boyutu dinamiktir
Yeni elemanın yerleştirilmesi pahalıdırYerleştirme / silme daha kolaydır
Rastgele erişime izin verilirRastgele erişim mümkün değil
Öğeler bitişik konumdaÖğelerin bitişik olmayan konumu var
Sonraki işaretçi için fazladan alan gerekmezSonraki işaretçi için gerekli ekstra bellek alanı

Başvurular

Diziler ve bağlantılı listeler hem öğeleri depolamak için kullanıldığından hem de doğrusal veri yapıları olduğundan, bu yapıların ikisi de uygulamaların çoğu için benzer şekillerde kullanılabilir.

sol birleşim ve sol dış birleşim

Bağlantılı listeler için uygulamalardan bazıları aşağıdaki gibidir:

  • Yığınları ve kuyrukları uygulamak için bağlantılı bir liste kullanılabilir.
  • Bağlantılı bir liste, grafikleri bitişik listeler olarak temsil etmemiz gerektiğinde grafikleri uygulamak için de kullanılabilir.
  • Matematiksel bir polinom, bağlantılı bir liste olarak saklanabilir.
  • Hashing tekniği durumunda, hashing işleminde kullanılan kovalar bağlantılı listeler kullanılarak uygulanır.
  • Bir program dinamik bellek tahsisi gerektirdiğinde, bağlantılı listeler bu durumda daha verimli çalıştığından bağlantılı bir liste kullanabiliriz.

Sonuç

Bağlı listeler, veri öğelerini doğrusal bir şekilde ancak bitişik olmayan konumlarda depolamak için kullanılan veri yapılarıdır. Bağlantılı liste, bir veri bölümü ve listedeki sonraki öğenin bellek adresini içeren bir sonraki işaretçi içeren bir düğümler koleksiyonudur.

Listedeki son elemanın bir sonraki göstericisi NULL olarak ayarlanmıştır, böylece listenin sonunu gösterir. Listenin ilk öğesine Başlık denir. Bağlantılı liste, ekleme, silme, geçiş vb. Gibi çeşitli işlemleri destekler. Dinamik bellek tahsisi durumunda, bağlantılı listeler dizilere tercih edilir.

Diziler gibi öğelere rastgele erişemediğimiz için bağlantılı listeler, geçişleri söz konusu olduğunda pahalıdır. Bununla birlikte, yerleştirme-silme işlemleri dizilerle karşılaştırıldığında daha ucuzdur.

Bu eğitimde doğrusal bağlantılı listeler hakkında her şeyi öğrendik. Bağlantılı listeler ayrıca dairesel veya çiftli olabilir. Gelecek eğitimlerimizde bu listelere derinlemesine bakacağız.

=> Tam C ++ Eğitim Serileri İçin Burayı Kontrol Edin.

Önerilen Kaynaklar

^