Πώς να εφαρμόσετε μια συνδεδεμένη λίστα σε JavaScript

Εάν μαθαίνετε δομές δεδομένων, μια συνδεδεμένη λίστα είναι μια δομή δεδομένων που πρέπει να γνωρίζετε. Εάν δεν το καταλαβαίνετε πραγματικά ή πώς εφαρμόζεται σε JavaScript, αυτό το άρθρο είναι εδώ για να σας βοηθήσει.

Σε αυτό το άρθρο, θα συζητήσουμε τι είναι μια συνδεδεμένη λίστα, πώς είναι διαφορετική από έναν πίνακα και πώς να την εφαρμόσετε σε JavaScript. Ας αρχίσουμε.

Τι είναι μια συνδεδεμένη λίστα;

Μια συνδεδεμένη λίστα είναι μια γραμμική δομή δεδομένων παρόμοια με έναν πίνακα. Ωστόσο, σε αντίθεση με τους πίνακες, τα στοιχεία δεν αποθηκεύονται σε μια συγκεκριμένη θέση ή ευρετήριο μνήμης. Αντίθετα, κάθε στοιχείο είναι ένα ξεχωριστό αντικείμενο που περιέχει ένα δείκτη ή έναν σύνδεσμο προς το επόμενο αντικείμενο αυτής της λίστας.

Κάθε στοιχείο (συνήθως ονομάζεται κόμβοι) περιέχει δύο στοιχεία: τα δεδομένα που αποθηκεύονται και έναν σύνδεσμο προς τον επόμενο κόμβο. Τα δεδομένα μπορεί να είναι οποιοσδήποτε έγκυρος τύπος δεδομένων. Αυτό μπορείτε να το δείτε στο παρακάτω διάγραμμα.

Εικόνα συνδεδεμένης λίστας

Το σημείο εισόδου σε μια συνδεδεμένη λίστα ονομάζεται επικεφαλής. Η κεφαλή είναι μια αναφορά στον πρώτο κόμβο της συνδεδεμένης λίστας. Ο τελευταίος κόμβος στη λίστα δείχνει μηδέν. Εάν μια λίστα είναι κενή, η κεφαλή είναι μηδενική αναφορά.

Στο JavaScript, μια συνδεδεμένη λίστα μοιάζει με αυτήν:

const list = { head: { value: 6 next: { value: 10 next: { value: 12 next: { value: 3 next: null } } } } } };

Ένα πλεονέκτημα των συνδεδεμένων λιστών

  • Οι κόμβοι μπορούν εύκολα να αφαιρεθούν ή να προστεθούν από μια συνδεδεμένη λίστα χωρίς να αναδιοργανωθεί ολόκληρη η δομή δεδομένων. Αυτό είναι ένα πλεονέκτημα που έχει έναντι των συστοιχιών.

Μειονεκτήματα των συνδεδεμένων λιστών

  • Οι λειτουργίες αναζήτησης είναι αργές σε συνδεδεμένες λίστες. Σε αντίθεση με τους πίνακες, η τυχαία πρόσβαση στα στοιχεία δεδομένων δεν επιτρέπεται. Οι κόμβοι έχουν πρόσβαση διαδοχικά ξεκινώντας από τον πρώτο κόμβο.
  • Χρησιμοποιεί περισσότερη μνήμη από τις συστοιχίες λόγω της αποθήκευσης των δεικτών.

Τύποι συνδεδεμένων λιστών

Υπάρχουν τρεις τύποι συνδεδεμένων λιστών:

  • Λίστες Singly Linked : Κάθε κόμβος περιέχει μόνο έναν δείκτη στον επόμενο κόμβο. Αυτό μιλάμε μέχρι τώρα.
  • Διπλά συνδεδεμένες λίστες : Κάθε κόμβος περιέχει δύο δείκτες, έναν δείκτη στον επόμενο κόμβο και έναν δείκτη στον προηγούμενο κόμβο.
  • Κυκλικές συνδεδεμένες λίστες : Οι κυκλικές συνδεδεμένες λίστες είναι μια παραλλαγή μιας συνδεδεμένης λίστας στην οποία ο τελευταίος κόμβος δείχνει τον πρώτο κόμβο ή οποιονδήποτε άλλο κόμβο πριν από αυτόν, σχηματίζοντας έτσι έναν βρόχο.

Εφαρμογή κόμβου λίστας σε JavaScript

Όπως αναφέρθηκε προηγουμένως, ένας κόμβος λίστας περιέχει δύο στοιχεία: τα δεδομένα και τον δείκτη στον επόμενο κόμβο. Μπορούμε να εφαρμόσουμε έναν κόμβο λίστας σε JavaScript ως εξής:

class ListNode { constructor(data) { this.data = data this.next = null } }

Εφαρμογή συνδεδεμένης λίστας σε JavaScript

Ο παρακάτω κώδικας δείχνει την εφαρμογή μιας συνδεδεμένης κλάσης λίστας με έναν κατασκευαστή. Σημειώστε ότι εάν ο κόμβος κεφαλής δεν περάσει, η κεφαλή αρχικοποιείται σε μηδέν.

class LinkedList { constructor(head = null) { this.head = head } }

Συνδυάζοντας τα όλα μαζί

Ας δημιουργήσουμε μια συνδεδεμένη λίστα με την τάξη που μόλις δημιουργήσαμε. Πρώτον, δημιουργούμε δύο κόμβους λίστας, node1και node2και ένας δείκτης από τον κόμβο 1 στον κόμβο 2.

let node1 = new ListNode(2) let node2 = new ListNode(5) node1.next = node2

Στη συνέχεια, θα δημιουργήσουμε μια συνδεδεμένη λίστα με το node1.

let list = new LinkedList(node1)

Ας προσπαθήσουμε να αποκτήσουμε πρόσβαση στους κόμβους στη λίστα που μόλις δημιουργήσαμε.

console.log(list.head.next.data) //returns 5

Μερικές μέθοδοι LinkedList

Στη συνέχεια, θα εφαρμόσουμε τέσσερις βοηθητικές μεθόδους για τη συνδεδεμένη λίστα. Αυτοί είναι:

  1. Μέγεθος()
  2. Σαφή()
  3. getLast ()
  4. getFirst ()

1. μέγεθος ()

Αυτή η μέθοδος επιστρέφει τον αριθμό των κόμβων που υπάρχουν στη συνδεδεμένη λίστα.

size() { let count = 0; let node = this.head; while (node) { count++; node = node.next } return count; } 

2. καθαρό ()

Αυτή η μέθοδος αδειάζει τη λίστα.

clear() { this.head = null; }

3. getLast ()

Αυτή η μέθοδος επιστρέφει τον τελευταίο κόμβο της συνδεδεμένης λίστας.

getLast() { let lastNode = this.head; if (lastNode) { while (lastNode.next) { lastNode = lastNode.next } } return lastNode }

4. getFirst ()

Αυτή η μέθοδος επιστρέφει τον πρώτο κόμβο της συνδεδεμένης λίστας.

getFirst() { return this.head; }

Περίληψη

Σε αυτό το άρθρο, συζητήσαμε τι είναι μια συνδεδεμένη λίστα και πώς μπορεί να εφαρμοστεί σε JavaScript. Συζητήσαμε επίσης τους διαφορετικούς τύπους συνδεδεμένων λιστών, καθώς και τα συνολικά πλεονεκτήματα και μειονεκτήματά τους.

Ελπίζω να σας άρεσε να το διαβάζετε.

Θέλετε να λαμβάνετε ειδοποίηση όταν δημοσιεύω ένα νέο άρθρο; Κάντε κλικ ΕΔΩ.