linked list data structure c with illustration
Λεπτομερής μελέτη συνδεδεμένης λίστας στο C ++.
Μια συνδεδεμένη λίστα είναι μια γραμμική δυναμική δομή δεδομένων για την αποθήκευση στοιχείων δεδομένων. Έχουμε ήδη δει πίνακες στα προηγούμενα θέματα σχετικά με το βασικό C ++. Γνωρίζουμε επίσης ότι οι πίνακες είναι μια γραμμική δομή δεδομένων που αποθηκεύει στοιχεία δεδομένων σε γειτονικές τοποθεσίες.
Σε αντίθεση με τους πίνακες, η συνδεδεμένη λίστα δεν αποθηκεύει στοιχεία δεδομένων σε γειτονικές θέσεις μνήμης.
Μια συνδεδεμένη λίστα αποτελείται από στοιχεία που ονομάζονται 'Κόμβοι' που περιέχουν δύο μέρη. Το πρώτο μέρος αποθηκεύει τα πραγματικά δεδομένα και το δεύτερο μέρος έχει ένα δείκτη που δείχνει στον επόμενο κόμβο. Αυτή η δομή ονομάζεται συνήθως 'Singly Linked List'.
=> Δείτε τα καλύτερα εκπαιδευτικά σεμινάρια C ++ εδώ.
Τι θα μάθετε:
Συνδεδεμένη λίστα σε C ++
Θα ρίξουμε μια ματιά στη λίστα που συνδέεται μεμονωμένα σε αυτό το σεμινάριο.
Το παρακάτω διάγραμμα δείχνει τη δομή μιας μοναδικής συνδεδεμένης λίστας.
Όπως φαίνεται παραπάνω, ο πρώτος κόμβος της συνδεδεμένης λίστας ονομάζεται 'head' ενώ ο τελευταίος κόμβος ονομάζεται 'Tail'. Όπως βλέπουμε, ο τελευταίος κόμβος της συνδεδεμένης λίστας θα έχει τον επόμενο δείκτη ως μηδενικό, καθώς δεν θα έχει καμιά διεύθυνση μνήμης.
Δεδομένου ότι κάθε κόμβος έχει δείκτη στον επόμενο κόμβο, τα στοιχεία δεδομένων στη συνδεδεμένη λίστα δεν χρειάζεται να αποθηκεύονται σε συνεχόμενες τοποθεσίες. Οι κόμβοι μπορούν να διασκορπιστούν στη μνήμη. Μπορούμε να έχουμε πρόσβαση στους κόμβους ανά πάσα στιγμή, καθώς κάθε κόμβος θα έχει διεύθυνση του επόμενου κόμβου.
Μπορούμε να προσθέσουμε στοιχεία δεδομένων στη συνδεδεμένη λίστα, καθώς και να διαγράψουμε εύκολα στοιχεία από τη λίστα. Έτσι, είναι δυνατή η δυναμική ανάπτυξη ή συρρίκνωση της συνδεδεμένης λίστας. Δεν υπάρχει ανώτερο όριο για το πόσα στοιχεία δεδομένων μπορούν να υπάρχουν στη συνδεδεμένη λίστα. Όσο υπάρχει διαθέσιμη μνήμη, μπορούμε να προσθέσουμε όσα στοιχεία δεδομένων προστίθενται στη συνδεδεμένη λίστα.
Εκτός από την εύκολη εισαγωγή και διαγραφή, η συνδεδεμένη λίστα επίσης δεν σπαταλά χώρο μνήμης καθώς δεν χρειάζεται να προσδιορίσουμε εκ των προτέρων πόσα στοιχεία χρειαζόμαστε στη συνδεδεμένη λίστα. Ο μόνος χώρος που έχει ληφθεί από τη συνδεδεμένη λίστα είναι για την αποθήκευση του δείκτη στον επόμενο κόμβο που προσθέτει λίγο γενικά.
Στη συνέχεια, θα συζητήσουμε τις διάφορες λειτουργίες που μπορούν να εκτελεστούν σε μια συνδεδεμένη λίστα.
Λειτουργίες
Όπως και οι άλλες δομές δεδομένων, μπορούμε επίσης να εκτελέσουμε διάφορες λειτουργίες για τη συνδεδεμένη λίστα. Αλλά σε αντίθεση με τους πίνακες, στους οποίους μπορούμε να έχουμε πρόσβαση στο στοιχείο χρησιμοποιώντας συνδρομητή απευθείας, ακόμη κι αν βρίσκεται κάπου στο μεταξύ, δεν μπορούμε να κάνουμε την ίδια τυχαία πρόσβαση με μια συνδεδεμένη λίστα.
Για να αποκτήσουμε πρόσβαση σε οποιονδήποτε κόμβο, πρέπει να διασχίσουμε τη συνδεδεμένη λίστα από την αρχή και μόνο τότε θα έχουμε πρόσβαση στον επιθυμητό κόμβο. Ως εκ τούτου, η τυχαία πρόσβαση στα δεδομένα από τη συνδεδεμένη λίστα αποδεικνύεται δαπανηρή.
Μπορούμε να εκτελέσουμε διάφορες λειτουργίες σε μια συνδεδεμένη λίστα όπως δίνεται παρακάτω:
# 1) Εισαγωγή
Η λειτουργία εισαγωγής συνδεδεμένης λίστας προσθέτει ένα στοιχείο στη συνδεδεμένη λίστα. Αν και μπορεί να ακούγεται απλό, δεδομένης της δομής της συνδεδεμένης λίστας, γνωρίζουμε ότι κάθε φορά που ένα στοιχείο δεδομένων προστίθεται στη συνδεδεμένη λίστα, πρέπει να αλλάξουμε τους επόμενους δείκτες των προηγούμενων και των επόμενων κόμβων του νέου στοιχείου που έχουμε εισαγάγει.
Το δεύτερο πράγμα που πρέπει να λάβουμε υπόψη είναι ο τόπος όπου θα προστεθεί το νέο στοιχείο δεδομένων.
Υπάρχουν τρεις θέσεις στη συνδεδεμένη λίστα όπου μπορεί να προστεθεί ένα στοιχείο δεδομένων.
# 1) Στην αρχή της συνδεδεμένης λίστας
Μια συνδεδεμένη λίστα εμφανίζεται παρακάτω 2-> 4-> 6-> 8-> 10. Εάν θέλουμε να προσθέσουμε έναν νέο κόμβο 1, ως τον πρώτο κόμβο της λίστας, τότε η κεφαλή που δείχνει τον κόμβο 2 θα δείχνει τώρα στο 1 και ο επόμενος δείκτης του κόμβου 1 θα έχει μια διεύθυνση μνήμης του κόμβου 2, όπως φαίνεται στα παρακάτω εικόνα.
Έτσι, η νέα συνδεδεμένη λίστα γίνεται 1-> 2-> 4-> 6-> 8-> 10.
# 2) Μετά τον δεδομένο κόμβο
Εδώ, δίνεται ένας κόμβος και πρέπει να προσθέσουμε έναν νέο κόμβο μετά τον συγκεκριμένο κόμβο. Στην παρακάτω λίστα a-> b-> c-> d -> e, εάν θέλουμε να προσθέσουμε έναν κόμβο f μετά τον κόμβο c τότε η συνδεδεμένη λίστα θα έχει την εξής μορφή:
Έτσι, στο παραπάνω διάγραμμα, ελέγχουμε εάν υπάρχει ο δεδομένος κόμβος. Εάν υπάρχει, δημιουργούμε έναν νέο κόμβο f. Στη συνέχεια, δείχουμε τον επόμενο δείκτη του κόμβου c για να δείξουμε τον νέο κόμβο f. Ο επόμενος δείκτης του κόμβου f τώρα δείχνει στον κόμβο d.
# 3) Στο τέλος της συνδεδεμένης λίστας
Στην τρίτη περίπτωση, προσθέτουμε έναν νέο κόμβο στο τέλος της συνδεδεμένης λίστας. Ας υποθέσουμε ότι έχουμε την ίδια συνδεδεμένη λίστα a-> b-> c-> d-> e και πρέπει να προσθέσουμε έναν κόμβο f στο τέλος της λίστας. Η συνδεδεμένη λίστα θα φαίνεται όπως φαίνεται παρακάτω μετά την προσθήκη του κόμβου.
Έτσι δημιουργούμε έναν νέο κόμβο f. Στη συνέχεια, ο δείκτης ουράς που δείχνει προς το null δείχνει στο f και ο επόμενος δείκτης του κόμβου f δείχνει το null. Έχουμε εφαρμόσει και τους τρεις τύπους λειτουργιών ένθεσης στο παρακάτω πρόγραμμα C ++.
Στο C ++, μπορούμε να δηλώσουμε μια συνδεδεμένη λίστα ως δομή ή ως τάξη. Η δήλωση συνδεδεμένης λίστας ως δομής είναι μια παραδοσιακή δήλωση τύπου C. Μια συνδεδεμένη λίστα ως τάξη χρησιμοποιείται στο σύγχρονο C ++, κυρίως κατά τη χρήση τυπικής βιβλιοθήκης προτύπων.
Στο ακόλουθο πρόγραμμα, χρησιμοποιήσαμε τη δομή για να δηλώσουμε και να δημιουργήσουμε μια συνδεδεμένη λίστα. Θα έχει δεδομένα και δείκτη στο επόμενο στοιχείο ως μέλη του.
#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 Παραγωγή:
Τελική συνδεδεμένη λίστα:
30–> 20–> 50–> 10–> 40–> μηδέν
Στη συνέχεια, εφαρμόζουμε τη λειτουργία εισαγωγής συνδεδεμένης λίστας στην Java. Στη γλώσσα Java, η συνδεδεμένη λίστα εφαρμόζεται ως τάξη. Το παρακάτω πρόγραμμα είναι λογικό παρόμοιο με το πρόγραμμα C ++, η μόνη διαφορά είναι ότι χρησιμοποιούμε μια κλάση για τη συνδεδεμένη λίστα.
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 (); } } Παραγωγή:
Τελική συνδεδεμένη λίστα:
10–> 20–> 30–> 40–> 50–> μηδέν
Και στα δύο παραπάνω προγράμματα, C ++ καθώς και Java, έχουμε ξεχωριστές λειτουργίες για να προσθέσουμε έναν κόμβο μπροστά από τη λίστα, το τέλος της λίστας και μεταξύ των λιστών που δίνονται σε έναν κόμβο. Στο τέλος, εκτυπώνουμε το περιεχόμενο της λίστας που δημιουργήθηκε χρησιμοποιώντας και τις τρεις μεθόδους.
# 2) Διαγραφή
Όπως η εισαγωγή, η διαγραφή ενός κόμβου από μια συνδεδεμένη λίστα περιλαμβάνει επίσης διάφορες θέσεις από τις οποίες μπορεί να διαγραφεί ο κόμβος. Μπορούμε να διαγράψουμε τον πρώτο κόμβο, τον τελευταίο κόμβο ή έναν τυχαίο κόμβο kth από τη συνδεδεμένη λίστα. Μετά τη διαγραφή, πρέπει να προσαρμόσουμε κατάλληλα τον επόμενο δείκτη και τους άλλους δείκτες στη συνδεδεμένη λίστα, ώστε να διατηρείται ανέπαφη η συνδεδεμένη λίστα.
Στην ακόλουθη υλοποίηση C ++, έχουμε δώσει δύο μεθόδους διαγραφής, δηλαδή διαγραφή του πρώτου κόμβου στη λίστα και διαγραφή του τελευταίου κόμβου στη λίστα. Αρχικά δημιουργούμε μια λίστα προσθέτοντας κόμβους στο κεφάλι. Στη συνέχεια, εμφανίζουμε τα περιεχόμενα της λίστας μετά την εισαγωγή και κάθε διαγραφή.
#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 ' Παραγωγή:
Δημιουργήθηκε συνδεδεμένη λίστα
10–> 8–> 6–> 4–> 2–
> NULL
Συνδεδεμένη λίστα μετά τη διαγραφή του κόμβου κεφαλής
8–> 6–> 4–> 2–
> NULL
Συνδεδεμένη λίστα μετά τη διαγραφή του τελευταίου κόμβου
8–> 6–> 4–> NULL
Στη συνέχεια είναι η εφαρμογή Java για τη διαγραφή κόμβων από τη συνδεδεμένη λίστα. Η λογική εφαρμογής είναι η ίδια όπως χρησιμοποιείται στο πρόγραμμα C ++. Η μόνη διαφορά είναι ότι η συνδεδεμένη λίστα δηλώνεται ως τάξη.
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'); } } Παραγωγή:
Δημιουργήθηκε συνδεδεμένη λίστα:
9–> 7–> 5–> 3–> 1–
> μηδέν
Συνδεδεμένη λίστα μετά τη διαγραφή του κόμβου κεφαλής:
7–> 5–> 3–> 1–
> μηδέν
Συνδεδεμένη λίστα μετά τη διαγραφή του τελευταίου κόμβου:
7–> 5–> 3–> μηδέν
ασφαλής δωρεάν μετατροπέας youtube σε mp3
Μετρήστε τον αριθμό των κόμβων
Η λειτουργία για τον υπολογισμό του αριθμού των κόμβων μπορεί να εκτελεστεί ενώ διασχίζει τη συνδεδεμένη λίστα. Έχουμε ήδη δει στην εφαρμογή παραπάνω ότι όποτε χρειαστεί να εισαγάγουμε / διαγράψουμε έναν κόμβο ή να εμφανίσουμε τα περιεχόμενα της συνδεδεμένης λίστας, πρέπει να διασχίσουμε τη συνδεδεμένη λίστα από την αρχή.
Διατηρώντας έναν μετρητή και αυξάνοντάς τον καθώς διασχίζουμε κάθε κόμβο θα μας δώσει τον αριθμό του αριθμού των κόμβων που υπάρχουν στη συνδεδεμένη λίστα. Θα αφήσουμε αυτό το πρόγραμμα για εφαρμογή από τους αναγνώστες.
Πίνακες και συνδεδεμένες λίστες
Έχοντας δει τις λειτουργίες και την εφαρμογή της συνδεδεμένης λίστας, ας συγκρίνουμε πώς οι πίνακες και η συνδεδεμένη λίστα είναι δίκαιες σε σύγκριση μεταξύ τους.
Πίνακες Συνδεδεμένες λίστες Οι πίνακες έχουν σταθερό μέγεθος Το μέγεθος της συνδεδεμένης λίστας είναι δυναμικό Η εισαγωγή νέου στοιχείου είναι ακριβή Η εισαγωγή / διαγραφή είναι ευκολότερη Επιτρέπεται η τυχαία πρόσβαση Δεν είναι δυνατή η τυχαία πρόσβαση Τα στοιχεία βρίσκονται σε γειτονική τοποθεσία Τα στοιχεία έχουν μη συνεχόμενη τοποθεσία Δεν απαιτείται επιπλέον χώρος για τον επόμενο δείκτη Απαιτείται επιπλέον χώρος μνήμης για τον επόμενο δείκτη
Εφαρμογές
Καθώς οι πίνακες και οι συνδεδεμένες λίστες χρησιμοποιούνται και για την αποθήκευση αντικειμένων και είναι γραμμικές δομές δεδομένων, και οι δύο αυτές δομές μπορούν να χρησιμοποιηθούν με παρόμοιο τρόπο για τις περισσότερες από τις εφαρμογές.
Ορισμένες από τις εφαρμογές για συνδεδεμένες λίστες έχουν ως εξής:
- Μια συνδεδεμένη λίστα μπορεί να χρησιμοποιηθεί για την εφαρμογή στοίβων και ουρών.
- Μια συνδεδεμένη λίστα μπορεί επίσης να χρησιμοποιηθεί για την εφαρμογή γραφημάτων όποτε πρέπει να αντιπροσωπεύουμε γραφήματα ως λίστες γειτνίασης.
- Ένα μαθηματικό πολυώνυμο μπορεί να αποθηκευτεί ως συνδεδεμένη λίστα.
- Στην περίπτωση της τεχνικής κατακερματισμού, οι κάδοι που χρησιμοποιούνται στο κατακερματισμό εφαρμόζονται χρησιμοποιώντας τις συνδεδεμένες λίστες.
- Κάθε φορά που ένα πρόγραμμα απαιτεί δυναμική κατανομή μνήμης, μπορούμε να χρησιμοποιήσουμε μια συνδεδεμένη λίστα καθώς οι συνδεδεμένες λίστες λειτουργούν πιο αποτελεσματικά σε αυτήν την περίπτωση.
συμπέρασμα
Οι συνδεδεμένες λίστες είναι οι δομές δεδομένων που χρησιμοποιούνται για την αποθήκευση στοιχείων δεδομένων με γραμμικό τρόπο αλλά μη συνεχόμενες τοποθεσίες. Μια συνδεδεμένη λίστα είναι μια συλλογή κόμβων που περιέχουν ένα τμήμα δεδομένων και έναν επόμενο δείκτη που περιέχει τη διεύθυνση μνήμης του επόμενου στοιχείου στη λίστα.
Το τελευταίο στοιχείο της λίστας έχει τον επόμενο δείκτη που έχει οριστεί σε NULL, υποδεικνύοντας έτσι το τέλος της λίστας. Το πρώτο στοιχείο της λίστας ονομάζεται Head. Η συνδεδεμένη λίστα υποστηρίζει διάφορες λειτουργίες όπως εισαγωγή, διαγραφή, διέλευση κ.λπ. Σε περίπτωση δυναμικής κατανομής μνήμης, οι συνδεδεμένες λίστες προτιμώνται από τις συστοιχίες.
Οι συνδεδεμένες λίστες είναι ακριβές όσον αφορά τη διασταύρωσή τους, καθώς δεν μπορούμε να έχουμε πρόσβαση τυχαία στα στοιχεία όπως οι πίνακες. Ωστόσο, οι λειτουργίες εισαγωγής-διαγραφής είναι λιγότερο δαπανηρές σε σύγκριση με συστοιχίες.
Έχουμε μάθει τα πάντα για γραμμικές συνδεδεμένες λίστες σε αυτό το σεμινάριο. Οι συνδεδεμένες λίστες μπορούν επίσης να είναι κυκλικές ή διπλάσιες. Θα δούμε σε βάθος αυτές τις λίστες στα επερχόμενα σεμινάρια μας.
=> Δείτε εδώ για πλήρη σειρά εκπαιδευτικών C ++.
Συνιστώμενη ανάγνωση
- Δομή δεδομένων κυκλικής συνδεδεμένης λίστας σε C ++ με απεικόνιση
- Διπλά συνδεδεμένη δομή δεδομένων λίστας σε C ++ με απεικόνιση
- Δομή δεδομένων ουράς σε C ++ με απεικόνιση
- Δομή δεδομένων στοίβας σε C ++ με απεικόνιση
- Δομή δεδομένων ουράς προτεραιότητας σε C ++ με απεικόνιση
- Κορυφαία 15 καλύτερα δωρεάν εργαλεία εξόρυξης δεδομένων: Η πιο περιεκτική λίστα
- 15 καλύτερα εργαλεία ETL το 2021 (μια πλήρης ενημερωμένη λίστα)
- Εισαγωγή στις δομές δεδομένων στο C ++