Gyengéd bevezetés az adatstruktúrákhoz: Hogyan működnek a kapcsolt listák?

Épített már valaha Rube Goldberg gépet? Ha nem, akkor talán kidolgozott domino sorozatot épített?

Oké, lehet, hogy nem voltál olyan dögös gyerek, mint én. Úgy legyen. Azok számára, akiknek örömmel tettük a fentiek bármelyikét, már felfogtátok a mai adatstruktúra lényegét: összekapcsolt listák!

Hogyan működnek a linkelt listák?

A kapcsolt listák legegyszerűbb formája - egyenként összekapcsolt lista - egy olyan csomópont-sorozat, ahol minden egyes csomópont tartalmaz egy értéket és egy mutatót is a lista következő csomópontjára.

A Kiegészítések ( Hozzáadás ) növeli a listát azáltal, hogy elemeket ad hozzá a lista végéhez.

Az eltávolítások ( Eltávolítás) mindig eltávolításra kerülnek a lista egy adott helyéről.

A Keresés ( Tartalmaz ) értéket keres a listában.

Példa felhasználási esetekre:

  • Értékek tárolása hash-táblában az ütközések elkerülése érdekében (erről bővebben néhány bejegyzésben)
  • A csodálatos verseny átalakítása!

Tartsuk szépen és könnyedén ezt a cikket egy olyan eszköz kidolgozásával, amelyet a CBS hálózata felhasználhat a következő elképesztő versenytévésorozat megtervezéséhez.

Ahogy átmész ezen, azt szeretném, ha folyamatosan kérdeznéd magadtól: „Hogyan különböznek a linkek a tömböktől? Miben hasonlítanak egymásra?

Kezdjük el.

Először létre kell hoznia a linkelt listánk reprezentációját:

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

A verseny kezdő és végpontjának nyomon követése érdekében meg kell hoznia a fej és a farok tulajdonságait.

Ezután annak érdekében, hogy ne legyen túl hosszú vagy túl rövid a verseny a szezonhoz, hozzon létre egy hossztulajdonságot és méretmódszert. Így mindig nyomon követheti, hogy pontosan milyen hosszú a verseny.

Most, hogy van módja a versenylista tárolására, létre kell hoznia egy módszert, amellyel hozzá lehet adni ehhez a listához. A kérdés az, hogy mit ad hozzá konkrétan?

Ne feledje, hogy a csatolt lista csomópontok sorozata, ahol minden csomópontnak van értéke és mutatója a lista következő csomópontjára. Ennek ismeretében rájössz, hogy a csomópont csak egy objektum, amelynek értéke és következő tulajdonsága van.

Mivel új csomópontot fog létrehozni minden alkalommal, amikor hozzáad a listához, úgy dönt, hogy létrehoz egy konstruktort, amely megkönnyíti az új csomópont létrehozását a listához hozzáadott minden értékhez.

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

Ha rendelkezésre áll ez a konstruktor, létrehozhatja az add metódust.

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");

Most, hogy hozzáadta ezt a módszert, hozzáadhat egy csomó helyet az Amazing Race listájához. Így fog kinézni. Ne feledje, hogy a megértés megkönnyítése érdekében felvettem egy kis extra helyet.

{ _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 }

Oké, most, miután létrehozta ezt a listát és egy módot a hozzáadásra, rájön, hogy segítségre van szüksége a helyek hozzáadásához ehhez a listához, mert decidofóbiája van (igen, ez egy dolog).

Úgy dönt, hogy megosztja munkatársával, Kent, és megkéri, hogy adjon hozzá még néhány helyet. Az egyetlen probléma az, hogy amikor odaadod neki, nem mondod meg neki, hogy mely helyeket már hozzáadtad. Sajnos Ön is elfelejtette, miután szenvedett amnéziát a döntési szorongás miatt.

Természetesen csak futtathatta a console.log-ot (AmazingRace), és átolvashatta , mit ad ki a konzol. De Kent lusta programozó, és szüksége van egy módra annak ellenőrzésére, hogy létezik-e valami, így megakadályozhatja a másolatokat. Ezt szem előtt tartva készít egy tartalmaz egy metódust a meglévő értékek ellenőrzésére.

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');

Félelmetes, most Kentnek módja van ellenőrizni az értékeket, mielőtt hozzáadná őket, elkerülve az ismétlődéseket.

Félretevésként felmerülhet a kérdés, hogy miért nem csak az add metódusban használta a tartalmazza metódust az ismétlődő kiegészítések megakadályozására? Amikor összekapcsolt listát - vagy bármilyen adatstruktúrát alkalmaz -, elméletileg hozzáadhat bármilyen további funkciót.

Akár be is léphet és módosíthatja a meglévő struktúrák natív módszereit. Próbálja ki az alábbiakat a REPL-ben:

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

Miért nem tesszük meg ezeket a dolgokat, az elfogadott normák miatt van. Lényegében a fejlesztők elvárják, hogy bizonyos módszerek hogyan működjenek.

Mivel az összekapcsolt listás osztályunk nem a JavaScript-ben honos, nagyobb a szabadsága annak megvalósításában, de még mindig vannak alapvető elvárások arra vonatkozóan, hogy az ilyen adatstruktúrák hogyan működjenek. Az összekapcsolt listák eleve nem tárolnak egyedi értékeket. De vannak olyan módszereik, mint az olyan tartalom, amely lehetővé teszi számunkra, hogy előzetesen ellenőrizzük és fenntartsuk a listánk egyediségét.

Kent visszatér Önhöz az úti célok listájával, de néhányuk megkérdőjelezhető. Például lehet, hogy az Északi-sark nem a legjobb Amazing Race célpont.

Tehát úgy dönt, hogy kiépít egy módszert egy csomópont eltávolítására. Fontos megjegyezni, hogy miután eltávolította a csomópontot, leválasztja a listát, és újra kell kapcsolnia azt, ami az eltávolított csomópont előtt és után történt.

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.

Finally, Ian Elliot wrote a walk-through that helps you implementing all of the methods. But see if you can implement addHead() and insertAfter() for your linked list before peeking at this ?