Pengenalan Lembut kepada Struktur Data: Bagaimana Senarai Berkaitan berfungsi

Adakah anda pernah membina Mesin Rube Goldberg? Sekiranya tidak, mungkin anda telah membina barisan domino yang terperinci?

Baiklah, mungkin anda tidak seperti budak kecil seperti saya. Jadi jadilah. Bagi anda yang mempunyai keseronokan untuk melakukan perkara di atas, anda sudah memahami intipati struktur data hari ini: senarai terpaut!

Cara senarai terpaut berfungsi

Bentuk senarai terpaut yang paling mudah - senarai berangkai tunggal - adalah rangkaian nod di mana setiap nod individu mengandungi nilai dan penunjuk ke simpul seterusnya dalam senarai.

Penambahan ( Tambah ) mengembangkan senarai dengan menambahkan item ke hujung senarai.

Penyingkiran ( Buang) akan selalu dikeluarkan dari kedudukan tertentu dalam senarai.

Search ( Contains ) akan mencari senarai untuk mencari nilai.

Contoh kes penggunaan:

Menyimpan nilai dalam jadual hash untuk mengelakkan perlanggaran (lebih lanjut mengenai ini dalam beberapa catatan)
Membuat semula perlumbaan yang luar biasa!

Mari teruskan artikel ini baik dan ringan dengan mengusahakan alat yang dapat digunakan oleh rangkaian CBS untuk merancang rancangan TV perlumbaan mereka yang seterusnya.

Semasa anda melalui ini, saya ingin anda terus bertanya pada diri sendiri: “Bagaimana senarai yang dipautkan berbeza dengan tatasusunan? Bagaimana mereka serupa? "

Mari kita mulakan.

Pertama, anda perlu membuat perwakilan senarai terpaut kami:

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

 size(){ return this._length; }}

Untuk mengesan titik permulaan dan titik akhir perlumbaan, anda membuat sifat kepala dan ekor.

Kemudian, untuk memastikan anda tidak membuat perlumbaan terlalu lama atau terlalu pendek untuk musim ini, anda membuat kaedah panjang dan ukuran. Dengan cara ini, anda sentiasa dapat mengetahui berapa lama perlumbaan.

Sekarang kerana anda mempunyai cara untuk menyimpan senarai perlumbaan, anda harus membuat kaedah untuk menambah senarai ini. Persoalannya, apa yang anda tambah secara khusus?

Ingat, senarai terpaut adalah rangkaian nod di mana setiap simpul mempunyai nilai dan penunjuk ke simpul seterusnya dalam senarai. Mengetahui hal ini, anda menyedari simpul hanyalah objek dengan nilai dan harta benda seterusnya.

Oleh kerana anda akan membuat nod baru setiap kali anda menambah senarai, anda memutuskan untuk membuat konstruktor yang menjadikannya lebih mudah untuk membuat simpul baru untuk setiap nilai yang ditambahkan ke senarai anda.

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

Dengan menyediakan konstruktor ini, anda boleh membuat kaedah tambah.

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

Setelah anda menambahkan kaedah ini, anda akan dapat menambahkan banyak lokasi ke senarai Amazing Race anda. Beginilah rupanya. Perhatikan bahawa saya telah menambahkan sedikit ruang putih untuk menjadikannya lebih mudah difahami.

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

Baiklah, jadi setelah anda membuat senarai ini dan cara untuk menambahkannya, anda menyedari bahawa anda memerlukan pertolongan untuk menambahkan lokasi ke senarai ini kerana anda menghidapi Decidophobia (ya, itu masalah).

Anda memutuskan untuk membaginya dengan rakan sekerja anda, Kent, memintanya untuk menambahkan beberapa tempat lagi. Satu-satunya masalah adalah, apabila anda memberikannya, anda tidak memberitahunya tempat yang telah anda tambahkan. Malangnya, anda juga lupa, setelah menderita amnesia disebabkan oleh kegelisahan keputusan.

Sudah tentu dia boleh menjalankan console.log (AmazingRace) dan membaca apa yang dihasilkan oleh konsol. Tetapi Kent adalah seorang pengaturcara yang malas dan memerlukan kaedah untuk memeriksa sama ada sesuatu itu wujud supaya dia dapat mengelakkan pendua. Dengan itu, anda membina kaedah berisi untuk memeriksa nilai yang ada.

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

Hebat, sekarang Kent mempunyai cara untuk memeriksa nilai sebelum menambahkannya, untuk mengelakkan pendua.

Sebagai tambahan, anda mungkin tertanya-tanya mengapa anda tidak hanya menggunakan kaedah mengandung dalam kaedah tambah untuk mengelakkan penambahan pendua? Semasa anda melaksanakan senarai terpaut - atau struktur data apa pun, anda boleh secara teorinya menambahkan fungsi tambahan yang anda mahukan.

Anda bahkan boleh masuk dan menukar kaedah asli pada struktur yang ada. Cubalah yang berikut di REPL:

Array.prototype.push = () => { return 'cat';}

let arr = [];arr.push('eggs'); // returns 'cat';

Sebab mengapa kita tidak melakukan perkara ini adalah kerana standard yang dipersetujui. Pada dasarnya, pembangun mempunyai jangkaan bagaimana kaedah tertentu harus berfungsi.

Since our linked list class isn’t native to JavaScript, we have more freedom in implementing it, but there are still basic expectations of how data structures such as these should function. Linked lists don’t inherently store unique values. But they do have methods like contains that allow us to pre-check and maintain uniqueness in our list.

Kent gets back to you with his list of destinations, but some of them are questionable. For example, the North Pole might not be the best Amazing Race destination.

So you decide to build out a method to be able to remove a node. It’s important to remember that once you remove the node, you unlink the list, and will have to re-link what came before and after the removed node.

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:

if the value exists in the list…
iterate over the linked list, keeping track of the previous and current node
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:

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

Cara senarai terpaut berfungsi

A time complexity analysis on the queue methods

Linked List vs Array?

Time for a quick recap

Further Reading