Свързаният списък е структура от данни, която се състои от последователност от възли, която съдържа стойност и препратка (връзка) към следващия възел.
Big-O нотация
access: O(n) search: O(n) insert: O(1) delete: O(1)
Достъпът и търсенето са доста бавни, тъй като възлите са свързани един по един, различно от масиви, където има индекси или хеш таблици, където има ключове.
Вмъкването и изтриването са бързи, както се случва в началото или в края.
Единично срещу двойно свързан списък
Единично свързаният списък съдържа възли, които имат препратка само в една посока (следващия възел), докато двойно свързаният списък съдържа препратка към противоположна посока.
Това позволява на разработчиците да персонализират структурата на данните, в зависимост от това кое е по-ценно, времето или паметта.
Да кажем, че искате да вмъкнете данни в 7-ми индекс в свързани списъци от 8 елемента. За единично свързан списък нямате друг избор, освен да преминете през списъка от 0-ия индекс до 7-ия индекс, тъй като има само препратка към следващия възел.
Двойно свързаните списъци ми позволяват да преминавам от назад, правейки времевата сложност на O(n)/2. Идеята Big-O ще опрости това до O(n), но има ясно предимство от използването на двойно свързан списък в такъв случай. Но сложността на пространството се увеличава, тъй като всеки възел трябва да съхранява допълнителна променлива.
Ето моя персонализиран списък с единични връзки в Javascript.
