Към съдържанието
wannacode

Свързан списък

Накратко: Свързаният списък е верига от възли, всеки с връзка към следващия: с head и tail добавянето в двата края и махането отпред са O(1), а достъпът по индекс е O(n).

Проблем

Опашката, която спира изпращането

Сървърът изпраща имейли от опашка. Новите влизат отзад, спешните (смяна на парола) отпред, а работникът взима винаги първия. Кодът ползва обикновения списък:

const emails = [];
emails.push("фактура");
emails.push("бюлетин");
emails.push("отчет");
emails.unshift("парола");
const next = emails.shift();
console.log("Изпращам: " + next);
console.log("Остават: " + emails.join(", "));
Изход
Изпращам: парола
Остават: фактура, бюлетин, отчет

В понеделник сутрин бюлетинът за всички клиенти пълни опашката със 100 000 имейла. Работникът изпраща по-бавно от обикновено, после почти спира, а имейлите за смяна на парола закъсняват с минути.

Причината: списъкът е динамичен масив. Взимането на първия мести всички останали с едно място напред, а спешният отпред мести всички назад. Да изпратиш 100 000 имейла един след друг са 99 999 + 99 998 + … + 1 = 4 999 950 000 премествания, само за да вземеш първия.

Идеята

Възли, head и tail

Възелът и вмъкването отпред вече ги видя в урока „Стек, опашка и свързан списък“: всеки елемент е отделен обект със стойност и стрелка next към следващия. Тук правиш целия клас и смяташ колко струва всяка операция.

Списъкът пази три неща:

  • head: първият възел. Оттам почва всяко обхождане.
  • tail: последният възел. С него добавянето в края не минава през целия списък.
  • размерът, за да не се брои всеки път.

Двата края трябва да са верни след всяка операция. Празният списък има head и tail null. Списък с един възел има head и tail, които сочат същия възел. Почти всяка грешка в свързан списък е забравен край: махаш последния, а tail още сочи него.

Виж го

Свой свързан списък

Ето целия клас. Възлите не се местят никога: всяка операция сменя само стрелки.

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


class SimpleLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }


  addFirst(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    if (this.tail === null) {
      this.tail = node;
    }
    this.size++;
  }


  addLast(value) {
    const node = new Node(value);
    if (this.tail === null) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    this.tail = node;
    this.size++;
  }


  removeFirst() {
    if (this.head === null) {
      throw new Error("списъкът е празен");
    }
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head === null) {
      this.tail = null;
    }
    this.size--;
    return value;
  }


  remove(value) {
    let prev = null;
    let n = this.head;
    while (n !== null && n.value !== value) {
      prev = n;
      n = n.next;
    }
    if (n === null) {
      return false;
    }
    if (prev === null) {
      this.head = n.next;
    } else {
      prev.next = n.next;
    }
    if (n === this.tail) {
      this.tail = prev;
    }
    this.size--;
    return true;
  }


  find(value) {
    let index = 0;
    for (let n = this.head; n !== null; n = n.next) {
      if (n.value === value) {
        return index;
      }
      index++;
    }
    return -1;
  }


  get(index) {
    if (index < 0 || index >= this.size) {
      throw new RangeError(`index ${index}, size ${this.size}`);
    }
    let n = this.head;
    for (let i = 0; i < index; i++) {
      n = n.next;
    }
    return n.value;
  }


  toString() {
    const values = [];
    for (let n = this.head; n !== null; n = n.next) {
      values.push(n.value);
    }
    return values.join(" → ");
  }
}

Гледай кои стрелки се сменят при всяка операция:

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


constructor() {
  this.head = null;
  this.tail = null;
  this.size = 0;
}
Стъпка по стъпка, с думи
  1. Три имейла, всеки в свой възел: стойността и next, стрелката към следващия. head сочи първия, tail последния.
  2. addFirst(„парола“): нов възел, неговият next сочи стария първи, и head минава на него. Две стрелки, нищо не се мести: O(1).
  3. addLast(„покана“): tail вече знае последния, затова не се минава по списъка. Неговият next сочи новия, и tail се мести: O(1).
  4. removeFirst(): head минава на следващия възел. Към „парола“ вече не сочи нищо, и паметта му се освобождава сама.
  5. remove(„бюлетин“): възлите нямат индекс. n тръгва от head и върви, докато го намери; prev остава един възел назад. Това е O(n).
  6. prev.next = n.next: една стрелка заобикаля „бюлетин“. „отчет“ и „покана“ не помръдват.
  7. В краищата: две стрелки, O(1). По средата: една стрелка, но до мястото се стига стъпка по стъпка, O(n).
const emails = new SimpleLinkedList();
emails.addLast("фактура");
emails.addLast("бюлетин");
emails.addLast("отчет");
emails.addFirst("парола");
emails.addLast("покана");
console.log(String(emails));
console.log("Изпращам: " + emails.removeFirst());
emails.remove("бюлетин");
console.log(String(emails));
console.log("Място на отчет: " + emails.find("отчет"));
console.log("Имейли: " + emails.size);
Изход
парола → фактура → бюлетин → отчет → покана
Изпращам: парола
фактура → отчет → покана
Място на отчет: 1
Имейли: 3
removeFirst на празен списък хвърля Error. toString е това, което String(emails) и "…" + emails ползват.

Пробвай

Предвиди изхода

Седем операции подред. Внимавай кой е последният след махането:

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


class SimpleLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }


  addFirst(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    if (this.tail === null) {
      this.tail = node;
    }
    this.size++;
  }


  addLast(value) {
    const node = new Node(value);
    if (this.tail === null) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    this.tail = node;
    this.size++;
  }


  removeFirst() {
    if (this.head === null) {
      throw new Error("списъкът е празен");
    }
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head === null) {
      this.tail = null;
    }
    this.size--;
    return value;
  }


  remove(value) {
    let prev = null;
    let n = this.head;
    while (n !== null && n.value !== value) {
      prev = n;
      n = n.next;
    }
    if (n === null) {
      return false;
    }
    if (prev === null) {
      this.head = n.next;
    } else {
      prev.next = n.next;
    }
    if (n === this.tail) {
      this.tail = prev;
    }
    this.size--;
    return true;
  }


  find(value) {
    let index = 0;
    for (let n = this.head; n !== null; n = n.next) {
      if (n.value === value) {
        return index;
      }
      index++;
    }
    return -1;
  }


  get(index) {
    if (index < 0 || index >= this.size) {
      throw new RangeError(`index ${index}, size ${this.size}`);
    }
    let n = this.head;
    for (let i = 0; i < index; i++) {
      n = n.next;
    }
    return n.value;
  }


  toString() {
    const values = [];
    for (let n = this.head; n !== null; n = n.next) {
      values.push(n.value);
    }
    return values.join(" → ");
  }
}


const emails = new SimpleLinkedList();
emails.addFirst("отчет");
emails.addFirst("фактура");
emails.addLast("покана");
emails.removeFirst();
emails.addFirst("парола");
emails.remove("покана");
emails.addLast("бюлетин");
console.log(String(emails));
console.log("Имейли: " + emails.size);
Отговор

Идеята

Кое колко струва: масив срещу свързан списък

Операция Динамичен масив Свързан списък
четене по индекс O(1) O(n)
добавяне отпред O(n) O(1)
добавяне отзад O(1) амортизирано O(1) с tail
махане на първия O(n) O(1)
махане на последния O(1) O(n), двусвързан: O(1)
по средата O(n): местене O(n): ходене до мястото

Последният ред е капанът. Самото пренасочване по средата е O(1), но до мястото се стига от head, стъпка по стъпка. Свързаният списък печели по средата само ако вече държиш възела, например защото току-що си го намерил с hash таблица.

Има и цена в паметта. Масивът пази стойностите (или референциите) една до друга. Всеки възел е отделен обект: стойността, стрелката и заглавката, която средата пази за всеки обект. При малки стойности възелът заема няколко пъти повече памет от мястото в масива.

Виж го

Измери го

Вмъкване отпред: динамичният масив от предишния урок срещу свързания списък. Броим записите на елементи: при масива новия и всяко преместване, при списъка само новия възел. Стрелките, които се сменят, са две за всяко вмъкване и не растат с n.

  • Вмъкване отпред O(n²)
  • Свързан списък: отпред O(n)
Алгоритъмn = 10n = 1000n = 10 000n = 100 000
Вмъкване отпред63501 51650 021 376≈ 5 002 137 600
Свързан списък: отпред10100010 000100 000
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}


class SimpleLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }


  addFirst(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    if (this.tail === null) {
      this.tail = node;
    }
    this.size++;
  }


  addLast(value) {
    const node = new Node(value);
    if (this.tail === null) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    this.tail = node;
    this.size++;
  }


  removeFirst() {
    if (this.head === null) {
      throw new Error("списъкът е празен");
    }
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head === null) {
      this.tail = null;
    }
    this.size--;
    return value;
  }


  remove(value) {
    let prev = null;
    let n = this.head;
    while (n !== null && n.value !== value) {
      prev = n;
      n = n.next;
    }
    if (n === null) {
      return false;
    }
    if (prev === null) {
      this.head = n.next;
    } else {
      prev.next = n.next;
    }
    if (n === this.tail) {
      this.tail = prev;
    }
    this.size--;
    return true;
  }


  find(value) {
    let index = 0;
    for (let n = this.head; n !== null; n = n.next) {
      if (n.value === value) {
        return index;
      }
      index++;
    }
    return -1;
  }


  get(index) {
    if (index < 0 || index >= this.size) {
      throw new RangeError(`index ${index}, size ${this.size}`);
    }
    let n = this.head;
    for (let i = 0; i < index; i++) {
      n = n.next;
    }
    return n.value;
  }


  toString() {
    const values = [];
    for (let n = this.head; n !== null; n = n.next) {
      values.push(n.value);
    }
    return values.join(" → ");
  }
}

При 10 000 имейла масивът прави 50 021 376 записа, а свързаният списък 10 000.

Сега обратното: прочитане на всеки елемент по индекс, get(0), get(1) и така до края. Броим местата, до които стигаш: в масива get(i) е един скок, а в списъка минава i + 1 възела.

  • Масив: get(i) за всяко i O(n)
  • Свързан списък: get(i) за всяко i O(n²)
Алгоритъмn = 10n = 1000n = 10 000n = 100 000
Масив: get(i) за всяко i10100010 000100 000
Свързан списък: get(i) за всяко i55500 50050 005 000≈ 5 000 500 000
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}


class SimpleLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }


  addFirst(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    if (this.tail === null) {
      this.tail = node;
    }
    this.size++;
  }


  addLast(value) {
    const node = new Node(value);
    if (this.tail === null) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    this.tail = node;
    this.size++;
  }


  removeFirst() {
    if (this.head === null) {
      throw new Error("списъкът е празен");
    }
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head === null) {
      this.tail = null;
    }
    this.size--;
    return value;
  }


  remove(value) {
    let prev = null;
    let n = this.head;
    while (n !== null && n.value !== value) {
      prev = n;
      n = n.next;
    }
    if (n === null) {
      return false;
    }
    if (prev === null) {
      this.head = n.next;
    } else {
      prev.next = n.next;
    }
    if (n === this.tail) {
      this.tail = prev;
    }
    this.size--;
    return true;
  }


  find(value) {
    let index = 0;
    for (let n = this.head; n !== null; n = n.next) {
      if (n.value === value) {
        return index;
      }
      index++;
    }
    return -1;
  }


  get(index) {
    if (index < 0 || index >= this.size) {
      throw new RangeError(`index ${index}, size ${this.size}`);
    }
    let n = this.head;
    for (let i = 0; i < index; i++) {
      n = n.next;
    }
    return n.value;
  }


  toString() {
    const values = [];
    for (let n = this.head; n !== null; n = n.next) {
      values.push(n.value);
    }
    return values.join(" → ");
  }
}

При 10 000 елемента масивът прави 10 000 скока, а свързаният списък 50 005 000 стъпки. Цикъл по индекс върху свързан списък е O(n²). Обхождай го с цикъла по стрелките (или с for-each), както прави toString: това е O(n).

По-точно, за любопитните

Същите числа на твоя език, с броячи в класа:

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


class SimpleLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
    this.writes = 0;
    this.steps = 0;
  }


  addFirst(value) {
    const node = new Node(value);
    this.writes++;
    node.next = this.head;
    this.head = node;
    if (this.tail === null) {
      this.tail = node;
    }
    this.size++;
  }


  addLast(value) {
    const node = new Node(value);
    if (this.tail === null) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    this.tail = node;
    this.size++;
  }


  removeFirst() {
    if (this.head === null) {
      throw new Error("списъкът е празен");
    }
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head === null) {
      this.tail = null;
    }
    this.size--;
    return value;
  }


  remove(value) {
    let prev = null;
    let n = this.head;
    while (n !== null && n.value !== value) {
      prev = n;
      n = n.next;
    }
    if (n === null) {
      return false;
    }
    if (prev === null) {
      this.head = n.next;
    } else {
      prev.next = n.next;
    }
    if (n === this.tail) {
      this.tail = prev;
    }
    this.size--;
    return true;
  }


  find(value) {
    let index = 0;
    for (let n = this.head; n !== null; n = n.next) {
      if (n.value === value) {
        return index;
      }
      index++;
    }
    return -1;
  }


  get(index) {
    if (index < 0 || index >= this.size) {
      throw new RangeError(`index ${index}, size ${this.size}`);
    }
    let n = this.head;
    this.steps++;
    for (let i = 0; i < index; i++) {
      n = n.next;
      this.steps++;
    }
    return n.value;
  }


  toString() {
    const values = [];
    for (let n = this.head; n !== null; n = n.next) {
      values.push(n.value);
    }
    return values.join(" → ");
  }
}


for (const n of [10, 1000, 100000]) {
  const list = new SimpleLinkedList();
  for (let i = 0; i < n; i++) {
    list.addFirst(String(1001 + i));
  }
  console.log(`отпред, n = ${n}: ${list.writes} записа`);
}
for (const n of [10, 1000]) {
  const list = new SimpleLinkedList();
  for (let i = 0; i < n; i++) {
    list.addLast(String(1001 + i));
  }
  for (let i = 0; i < n; i++) {
    list.get(i);
  }
  console.log(`get(i) за всяко i, n = ${n}: ${list.steps} стъпки`);
}
Изход
отпред, n = 10: 10 записа
отпред, n = 1000: 1000 записа
отпред, n = 100000: 100000 записа
get(i) за всяко i, n = 10: 55 стъпки
get(i) за всяко i, n = 1000: 500500 стъпки

Bench брои операции, не време. По часовник разликата при обхождане е още по-голяма в полза на масива заради кеша: масивът е един блок, а възлите са разпръснати и всеки следващ може да не е в кеша. Тук това не е измерено, само е обяснено в урока за динамичния масив.

Пробвай

Намери грешката

Колега е писал addLast. Три имейла отзад, а списъкът излиза така:

const emails = new SimpleLinkedList();
emails.addLast("фактура");
emails.addLast("бюлетин");
emails.addLast("отчет");
console.log(String(emails));
console.log("Имейли: " + emails.size);
Изход
фактура → отчет
Имейли: 3

Размерът е 3, а имейлите са два. На кой ред е грешката?

Избери реда с грешката.

Пробвай

Попълни

remove е намерил възела n и този преди него, prev. Накъде трябва да сочи prev сега?

remove(value) {
  let prev = null;
  let n = this.head;
  while (n !== null && n.value !== value) {
    prev = n;
    n = n.next;
  }
  if (n === null) {
    return false;
  }
  if (prev === null) {
    this.head = n.next;
  } else {
    prev.next = ;
  }
  if (n === this.tail) {
    this.tail = prev;
  }
  this.size--;
  return true;
}

Идеята

Двусвързан списък

Едносвързаният списък не може да маха последния бързо: трябва му предпоследният, а към него никой не сочи назад. Двусвързаният списък пази във всеки възел две стрелки, next и prev. Тогава и двата края са O(1), а възел, който вече държиш, се маха с четири стрелки, без да търсиш предишния.

Цената е още една стрелка във всеки възел и повече за пренасочване при всяка операция.

В JavaScript няма вграден свързан списък. Масивът има unshift и shift, но те местят всичко.

Идеята

Къде свързаният списък печели наистина

За обикновена опашка вграденото е по-добро. В JavaScript готова няма, но масив с индекс на първия не мести нищо. Как работи, е в урока „Стек и опашка“. Свързаният списък печели, когато вече държиш възела и трябва да го извадиш или преместиш:

  • LRU кеш. Магазинът пази в паметта последните отворени продукти и изхвърля най-отдавна отворения. Hash таблица намира възела на продукта за O(1), а двусвързан списък го мести най-отзад. Най-старият е винаги отпред.
  • История с назад и напред. Браузърът и редакторът пазят стъпките в двусвързан списък: назад и напред са една стрелка.
  • Списъците в ядрото на операционната система. Процесите и буферите сами носят стрелките си и се вадят от списъка за O(1).

Ето LRU с вграденото, последните три отворени продукта:

class Recent {
  constructor(limit) {
    this.limit = limit;
    this.items = new Set();
  }


  open(product) {
    if (this.items.has(product)) {
      this.items.delete(product);
    } else if (this.items.size === this.limit) {
      const oldest = this.items.values().next().value;
      this.items.delete(oldest);
    }
    this.items.add(product);
  }


  toString() {
    return [...this.items].join(", ");
  }
}


const recent = new Recent(3);
for (const product of ["лаптоп", "мишка", "монитор", "лаптоп", "клавиатура"]) {
  recent.open(product);
  console.log(String(recent));
}
Изход
лаптоп
лаптоп, мишка
лаптоп, мишка, монитор
мишка, монитор, лаптоп
монитор, лаптоп, клавиатура
Set в JavaScript пази реда на добавяне. Отвътре не е свързан списък, а hash таблица с масив от записи, но delete и add пак дават O(1) средно. Свой LRU със свързан списък е последната задача по-долу.

Упражнение

Двусвързан списък

Реши задачата в редактора си.

Махане от двата края. Направи DoublyLinkedList: възелът има и prev. Напиши addFirst, addLast, removeFirst и removeLast, всички за O(1). Пази двата края верни: когато списъкът стане празен, и head, и tail са null.

Добави трите имейла отзад и паролата отпред. Отпечатай списъка, махни последния и първия, отпечатай пак. Махни още два отзад, отпечатай размера, после добави поканата отзад:

Изход
парола → фактура → бюлетин → отчет
Последен: отчет
Първи: парола
фактура → бюлетин
Имейли: 0
покана

Още задачи

  • Средата с два указателя. Намери средния възел с едно минаване: единият указател върви по една стъпка, другият по две. Когато бързият стигне края, бавният е по средата.
  • Цикъл в списъка. Грешка е закачила последния възел към някой от предишните. Открий го със същите два указателя: ако има цикъл, бързият настига бавния.
  • Махни всички срещания. removeAll(value) маха всеки възел с тази стойност с едно минаване и връща колко е махнал. Не забравяй tail.
  • LRU на ръка. Направи LRU кеша от картата горе със свой двусвързан списък и Map от продукт към възел.

Тест

Провери се

1. Свързан списък има 1000 възела, а пазиш само head. Колко възела минаваш, за да прочетеш елемента с индекс 999?
2. Защо е нужен tail, ако head вече държи целия списък?
3. В едносвързан списък с head и tail колко струва махането на последния?
4. Bench показва, че вмъкването отпред в свързан списък прави n операции, а в динамичен масив около n²/2. Защо въпреки това масивът често е по-бърз при обхождане?
5. LRU кеш пази последните 1000 отворени продукта и изхвърля най-отдавна отворения. Какво го прави O(1) за всяко отваряне?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·