Лагідний вступ до структур даних: як працюють зв’язані списки

Ви коли-небудь будували машину Rube Goldberg? Якщо ні, можливо, ви побудували складну лінію доміно?

Гаразд, можливо, ти не був такою заторможеною дитиною, як я. Тож нехай так. Для тих з вас, хто мав задоволення зробити щось із вищезазначеного, ви вже зрозуміли суть сьогоднішньої структури даних: зв’язані списки!

Як працюють зв’язані списки

Найпростіша форма пов'язаних списків - однопов'язаний список - це серія вузлів, де кожен окремий вузол містить як значення, так і вказівник на наступний вузол у списку.

Додатки ( Add ) збільшують список, додаючи елементи в кінець списку.

Видалення ( Видалити) завжди видалятиме із заданої позиції у списку.

Пошук ( Містить ) буде шукати значення у списку.

Приклади випадків використання:

  • Зберігання значень у хеш-таблиці для запобігання зіткненням (докладніше про це у кількох постах)
  • Переробка дивовижної гонки!

Давайте збережемо цю статтю приємною та легкою, працюючи над інструментом, який мережа 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 }

Гаразд, отже, тепер, коли ви створили цей список і додали спосіб, ви усвідомлюєте, що вам потрібна допомога з додаванням місць до цього списку, оскільки у вас є децидофобія (так, це річ).

Ви вирішили поділитися ним зі своїм колегою Кентом, попросивши його додати ще кілька місць. Єдина проблема полягає в тому, що коли ви даєте йому його, ви не говорите йому, які місця ви вже додали. На жаль, ви теж забули після того, як пережили амнезію, спричинену тривогою щодо прийняття рішення.

Звичайно, він міг просто запустити 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');

Чудово, тепер у Кента є спосіб перевірити значення перед їх додаванням, щоб уникнути дублікатів.

Окрім того, вам може бути цікаво, чому ви не просто використовували метод contains у методі add, щоб запобігти повторним доповненням? Коли ви реалізовуєте пов'язаний список - або будь-яку структуру даних, з цього приводу - ви теоретично можете додати будь-яку додаткову функціональність, яку хочете.

Ви навіть можете зайти і змінити власні методи на існуючих структурах. Спробуйте наведене нижче у REPL:

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

Причина, по якій ми не робимо жодної з цих речей, полягає в узгоджених стандартах. По суті, розробники очікують, як повинні працювати певні методи.

Оскільки наш клас пов'язаних списків не є рідним для JavaScript, ми маємо більше свободи в його реалізації, але все ще існують основні очікування щодо того, як повинні функціонувати такі структури даних. Пов’язані списки за своєю суттю не зберігають унікальні значення. Але у них є такі методи, як вміст, які дозволяють нам попередньо перевірити та зберегти унікальність у нашому списку.

Кент зв’язується з вами зі своїм списком напрямків, але деякі з них сумнівні. Наприклад, Північний полюс може бути не найкращим напрямком Дивовижних перегонів.

Тож ви вирішили побудувати метод, щоб мати можливість видалити вузол. Важливо пам’ятати, що як тільки ви видалите вузол, ви від’єднаєте список, і вам доведеться повторно пов’язати те, що з’явилося до та після видаленого вузла.

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

У цій функції видалення є багато коду . По суті, це зводиться до наступного:

  1. якщо значення існує у списку ...
  2. перебирати зв’язаний список, відстежуючи попередній і поточний вузол
  3. тоді, якщо є збіг →

4А. якщо це голова

  • скинути головку до наступного вузла у списку
  • оновити довжину
  • вирватися з циклу

4В. якщо це хвіст

  • скинути хвіст до попереднього вузла у списку
  • від'єднайте вузол, скинувши покажчики, як показано нижче

4С. Якщо це не збіг → продовжуйте ітерацію

  • зробити наступний вузол поточним
  • зробити поточний вузол попереднім

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 ?