Μια ευγενής εισαγωγή στις δομές δεδομένων: Πώς λειτουργούν οι συνδεδεμένες λίστες

Έχετε δημιουργήσει ποτέ μια μηχανή Rube Goldberg; Εάν όχι, ίσως έχετε δημιουργήσει μια περίπλοκη σειρά ντόμινο;

Εντάξει, ίσως δεν ήσουν τόσο χαριτωμένος ενός παιδιού όσο ήμουν. Ας είναι. Για όσους από εσάς είχατε την ευχαρίστηση να κάνετε οποιοδήποτε από τα παραπάνω, έχετε ήδη κατανοήσει την ουσία της σημερινής δομής δεδομένων: συνδεδεμένες λίστες!

Πώς λειτουργούν οι συνδεδεμένες λίστες

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

Οι προσθήκες ( Προσθήκη ) αναπτύσσουν τη λίστα προσθέτοντας στοιχεία στο τέλος της λίστας.

Οι καταργήσεις ( Κατάργηση) θα καταργούνται πάντα από μια δεδομένη θέση στη λίστα.

Η Αναζήτηση ( Περιέχει ) θα πραγματοποιήσει αναζήτηση στη λίστα για μια τιμή.

Παραδείγματα περιπτώσεων χρήσης:

  • Αποθήκευση τιμών σε έναν πίνακα κατακερματισμού για την αποφυγή συγκρούσεων (περισσότερα σε αυτό σε λίγες δημοσιεύσεις)
  • Ανακατασκευάζοντας τον καταπληκτικό αγώνα!

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

Καθώς περνάτε από αυτό, θέλω να συνεχίσετε να αναρωτιέστε: «Πώς οι λίστες συνδέσμων διαφέρουν από τις συστοιχίες; Πώς είναι παρόμοια; "

Ας αρχίσουμε.

Πρώτον, πρέπει να δημιουργήσετε την αναπαράσταση της συνδεδεμένης λίστας μας:

class LinkedList{ constructor(){ this._head = null; this._tail = null; this._length = 0; }
 size(){ return this._length; }}

Για να παρακολουθείτε το σημείο εκκίνησης και το τελικό σημείο του αγώνα, δημιουργείτε τις ιδιότητες κεφαλής και ουράς.

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

Τώρα που έχετε έναν τρόπο να αποθηκεύσετε τη λίστα αγώνων, θα πρέπει να δημιουργήσετε έναν τρόπο προσθήκης σε αυτήν τη λίστα. Το ερώτημα είναι, τι προσθέτετε συγκεκριμένα;

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

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

class Node{ constructor(value){ this.value = value; this.next = null; }}

Έχοντας αυτόν τον κατασκευαστή διαθέσιμο μπορείτε να δημιουργήσετε τη μέθοδο προσθήκης σας

class Node { constructor(value) { this.value = value; this.next = null; }}
class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); //we create our node if(!this._head && !this._tail){ //If it's the first node this._head = node; //1st node is head & tail this._tail = node; }else{ this._tail.next = node; //add node to the back this._tail = this._tail.next; //reset tail to last node } this._length++; } size() { return this._length; }}
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");

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

{ _head: { value: 'Colombo, Sri Lanka', next: { value: 'Lagos, Nigeria', next: { value: 'Surat, India', next: { value: 'Suzhou, China', next: null } } } }, _tail: { value: 'Suzhou, China', next: null }, _length: 4 }

Εντάξει, οπότε τώρα που έχετε δημιουργήσει αυτήν τη λίστα και έναν τρόπο να προσθέσετε, συνειδητοποιείτε ότι θέλετε κάποια βοήθεια για την προσθήκη τοποθεσιών σε αυτήν τη λίστα, επειδή έχετε Decidophobia (ναι, είναι πράγματι).

Αποφασίζετε να το μοιραστείτε με τον συνάδελφό σας, Κεντ, ζητώντας του να προσθέσει μερικά ακόμη μέρη. Το μόνο πρόβλημα είναι ότι, όταν το δώσετε, δεν του λέτε ποια μέρη έχετε ήδη προσθέσει. Δυστυχώς, έχετε ξεχάσει επίσης, αφού υποφέρατε από αμνησία από το άγχος της απόφασης.

Φυσικά μπορούσε απλώς να τρέξει το console.log (AmazingRace) και να διαβάσει τι εξάγει η κονσόλα. Αλλά ο Κεντ είναι ένας τεμπέλης προγραμματιστής και χρειάζεται έναν τρόπο για να ελέγξει αν υπάρχει κάτι, ώστε να αποτρέψει τα διπλά. Έχοντας αυτό κατά νου, δημιουργείτε μια μέθοδο περιέχει για να ελέγξετε τις υπάρχουσες τιμές.

class Node { constructor(value) { this.value = value; this.next = null; }}class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; } }
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");
//Kent's check
AmazingRace.contains('Suzhou, China'); //trueAmazingRace.contains('Hanoi, Vietnam'); //falseAmazingRace.add('Hanoi, Vietnam');AmazingRace.contains('Seattle, Washington'); //falseAmazingRace.add('Seattle, Washington');AmazingRace.contains('North Pole'); // falseAmazingRace.add('North Pole');

Φοβερό, τώρα το Kent έχει έναν τρόπο να ελέγχει τις τιμές πριν τις προσθέσει, για να αποφύγει τα διπλά.

Εκτός αυτού, ίσως αναρωτιέστε γιατί δεν χρησιμοποιήσατε μόνο τη μέθοδο περιέχει στη μέθοδο προσθήκης για να αποτρέψετε διπλές προσθήκες; Όταν εφαρμόζετε μια συνδεδεμένη λίστα - ή οποιαδήποτε δομή δεδομένων, για αυτό το θέμα - θα μπορούσατε θεωρητικά να προσθέσετε όποια επιπλέον λειτουργικότητα θέλετε.

Μπορείτε ακόμη και να εισέλθετε και να αλλάξετε εγγενείς μεθόδους σε υπάρχουσες δομές. Δοκιμάστε τα παρακάτω σε ένα REPL:

Array.prototype.push = () => { return 'cat';}
let arr = [];arr.push('eggs'); // returns 'cat';

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

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

Ο Κεντ σας απαντά με τη λίστα των προορισμών του, αλλά ορισμένοι από αυτούς είναι αμφισβητήσιμοι. Για παράδειγμα, ο Βόρειος Πόλος μπορεί να μην είναι ο καλύτερος προορισμός Amazing Race.

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

class Node { constructor(value) { this.value = value; this.next = null; }}class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } remove(value) { if(this.contains(value)){ // see if our value exists let current = this._head; // begin at start of list let previous = this._head; while(current){ // check each node if(current.value === value){ if(this._head === current){ // if it's the head this._head = this._head.next; // reset the head this._length--; // update the length return; // break out of the loop } if(this._tail === current){ // if it's the tail node this._tail = previous; // make sure to reset it } previous.next = current.next; // unlink (see img below) this._length--; // update the length return; // break out of } previous = current; // look at the next node current = current.next; // ^^ } } } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; } }
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");AmazingRace.add('Hanoi, Vietnam');AmazingRace.add('Seattle, Washington');AmazingRace.add('North Pole');
//Kent's check
AmazingRace.remove('North Pole');

There’s a lot of code in that remove function up there. Essentially it boils down to the following:

  1. if the value exists in the list…
  2. iterate over the linked list, keeping track of the previous and current node
  3. then, if there’s a match →

4A . if it’s the head

  • reset the head to the next node in the list
  • update the length
  • break out of the loop

4B. if it’s the tail

  • reset the tail to the previous node in the list
  • unlink the node by resetting the pointers as seen below

4C. If it’s not a match → continue iterating

  • make the next node current
  • make the current node previous

One last thing to note: you may have realized that you didn’t actually delete the node. You just removed the references to it. Well, that’s OK because once all references to an object are removed, the garbage collector helps us remove it from memory. You can read up on the garbage collection here.

With the remove method now implemented, you can run this little piece of code below to make sure contestants don’t freeze to death, or accidentally bother Santa as he’s prepping for this year’s festivities.

AmazingRace.remove('North Pole');

You’ve done it! You’ve created a simple implementation of a linked list. And you can grow the list by adding items, and shrink it by removing items — all based on the item’s value.

See if you can add you can expand the linked list to allow you to insert values at the beginning, end, or any point in between.

You have all you need to implement those methods. The names and arguments for these methods should look a little like this:

addHead(value) {
}
insertAfter(target, value){
}

Feel free to share your implementations in the comments below ?

A time complexity analysis on the queue methods

Here’s the code again:

class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } remove(value) { if(this.contains(value)){ let current = this._head; let previous = this._head; while(current){ if(current.value === value){ if(this._head === current){ this._head = this._head.next; this._length--; return; } if(this._tail === current){ this._tail = previous; } previous.next = current.next; this._length--; return; } previous = current; current = current.next; } } } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; }
// To Be Implemented
addHead(value) {
}
insertAfter(target, value){
}

Add is O(1): Since you always know the last item in the list thanks to tail property, you don’t have to iterate over the list.

Remove is O(n): In the worst case scenario you’re going to have to iterate over the entire list to find the value to be removed. Great part though is the actual removal of the node is O(1) because you’re just resetting pointers.

Contains is O(n): You have to iterate over the entire list to check if the value exists in your list.

addHead is O(1): Similar to our add method above, we always know the position of the head, so no iteration necessary.

insertAfter is O(n): Similar to our Remove method above, you’ll have to iterate over the entire list to find the target node that your value should be inserted after. Likewise, the actual insertion is O(1) because you’re just resetting pointers.

Linked List vs Array?

Why would you use a linked list instead of an arrays? Arrays technically allow you to do all of the things linked lists do, such as additions, insertions, and removals. Also, all these methods are already readily available to us in JavaScript.

Well, the biggest difference comes in the insertions and removals. Since arrays are indexed, when you perform an insertion or removal in the middle of the array, you have to reset the position of all following values to their new indices.

Imagine inserting into the start or middle of an array 100,000 values long! Insertions and removals like this are extremely expensive. Because of this, linked lists are often preferred for large data sets that are often shifted around.

On the other hand, arrays are great when it comes to finding items (random access) since they are indexed. If you know the position of an item, you can access it in O(1) time via array[position].

Linked lists always require you to iterate over the linked lists sequentially. Given this, arrays are usually preferred for either smaller data sets, or data sets that aren’t shifted around as often.

Time for a quick recap

Linked Lists:

  1. have a tail and head property to track the ends of the list
  2. have an add, addHead, insertAfter, and remove method to manage the contents of your list
  3. have a length property to track how long your linked list is

Further Reading

There are also the doubly-linked list and circular-linked list data structures. You can read about them on Wikipedia.

Also, here’s a solid, quick overview by Vivek Kumar.

Τέλος, ο Ian Elliot έγραψε μια αναλυτική περιγραφή που σας βοηθά να εφαρμόσετε όλες τις μεθόδους. Αλλά δείτε αν μπορείτε να εφαρμόσετε το addHead () και το insertAfter () για τη λίστα που έχετε συνδέσει, προτού δείτε αυτό;