Основната разлика между единичните и двойно свързаните списъци е, че в по-късните всеки елемент съдържа указател към елемента, който го предхожда. Това ни позволява да обходим списъка от опашката към главатаи премахваме елементи в постоянно време.
Ако не сте прочели предишната ми публикация за единично свързани списъци, препоръчвам ви да го направите, защото този път ще работим върху това, което изградихме миналия път.
В двойно свързаните списъци елементите са представени от възли, които съдържат три атрибута:
- Стойността, която елементът притежава.
- Указател към следващия възел в списъка.
- Указател към предишния възел в списъка.
Както и при единично свързаните списъци, първият елемент на списъка се нарича „глава“, а последният се нарича „опашка“.
Границите на двойно свързаните списъци са ограничени от предходния указател на първия елемент и следващия указател на последния. И двата указателя трябва да бъдат зададени на нула.
X <-[prev|data|next] <-> [prev|data|next] <-> [prev|data|next] -> X
Що се отнася до сложността на операциите, единично и двойно свързаните списъци работят почти еднакво, единствената разлика е в метода за премахване. Тъй като в двойно свързан списък всеки възел съдържа указател към предишния възел, премахванията са O(1).
* Забележка: Ако не сте запознати с нотацията Big O или не знаете със сигурност какво означава „сложност на операциите“, може да искате да проверите „предишния ми пост“, където замазах тези понятия.
Интерфейс на двойно свързани списъци
Ако погледнете таблицата по-долу, ще забележите, че дефиницията на интерфейса за двойно свързани списъци е почти същата като тази за единично свързани списъци. Това е добра новина за нас, защото тъй като ще създадем двойно свързан списък, разширяващ „единично свързани“, по-голямата част от кода вече е готов ;)
(Методите, които трябва да добавим или заменим, са подчертани с удебелен текст).
За да избегна да се повтарям (и да ви губя времето, докато го правя), няма да включвам подробности за методите, наследени от единично свързания списък, защото можете да ги видите в предишната публикация. Ще се концентрирам само върху двойно свързани списъци.
Поставете
Създава нов възел за вмъкване на стойност в списъка. Ако списъкът няма възли, новият възел става главата на списъка; в противен случай се добавя в края на списъка.
Тъй като списъкът поддържа указатели към главата и опашката си, сложността на този метод е O(1).
Имайте предвид, че когато списъкът съдържа елементи, трябва да настроим предишния указател на възела, който ще вмъкнем, да сочи към опашката на списъка.
def insert data
node = Node.new data
unless head
self.head = node
else
node.prev = self.tail
self.tail.next = node
end
self.tail = node
self.length += 1
end
Премахване
Премахва дадения възел от свързания списък и коригира указателите, за да поддържа елементите заедно.
Ако възелът, който трябва да премахнем, е главата на списъка, трябва да покрием две ситуации:
- Head е единственият възел в списъка. Задаваме head и tail на нула и сме готови.
- Head не е единственият възел в списъка. Възелът, който е до главата, става новата глава и оригиналната глава излиза извън обхвата.
Ако възелът, който трябва да премахнем, не е в началото на списъка, трябва само да коригираме указателите, за да оставим целевия възел извън обхвата. Първо, трябва да настроим следващия указател на възела, който предхожда целевия възел, за да сочи към възела, който е до целта. Второ, трябва да настроим предишния указател на възела, който е до целевия възел, за да сочи към възела, който го предхожда.
Както се случва с почти всички методи в двойно свързаните списъци, част от кода струва колкото хиляда думи. Така че нека вместо това проверим кода.
def remove node return nil unless node
if node == head if head.next.nil? self.head = self.tail = nil else self.head = self.head.next end else p = node.prev n = node.next p&.next = n n&.prev = p end self.length -= 1 end
В случай, че не сте го забелязали, този път не трябваше да обикаляме списъка, за да намерим възела, който предхожда елемента, който искаме да премахнем и следователно тази операция O(1).
котка
Този метод ни позволява да обединим два списъка заедно и е разделен на 4 стъпки:
- Посочете предишния показалец на главата на списъка, който добавяме към опашката на текущия списък.
- Насочете следващия указател от опашката на текущия списък към главата на списъка, който добавяме.
- Задайте опашката на текущия списък на опашката на списъка, който добавяме.
- Коригирайте дължината на текущия списък.
Сложността на този метод е O(1).
def cat list return nil unless list
list.head.prev = self.tail self.tail.next = list.head self.tail = list.tail self.length += list.length end
Намерете последно
Този метод ни позволява да получим последния елемент от списъка, който удовлетворява даден предикат. (Или първото появяване, започващо от опашката.)
Начинът, по който намираме последния елемент, е като обхождаме списъка от опашката до главата, прилагайки предиката към всеки елемент, докато резултатът от тази операция стане верен или списъкът се изчерпи.
Сложността на този метод е O(n), защото може да се наложи да обходим целия списък.
def find_last &predicate return nil unless block_given?
current = self.tail while current return current if predicate.call(current) current = current.prev end end
За да видите този метод в действие, да предположим, че имате списък с числа и искате да намерите последното срещанена числото 3.
Както направихме с единично свързаните списъци, нека първо опитаме „елементарния“ начин:
e = nil
current = list.tail
while current
if current.data == 3
e = current.data
break
end
current = current.prev
end
Сега, елегантният и Ruby „идиоматичен“ начин:
e = list.find_last { |item| item.data == 3; }
Обърнете всяка
Този метод преминава през списъка от опашката до главата, като дава един елемент наведнъж, докато стигне до края на списъка.
Не е изненадващо, че прилагането на този метод е подобно на това, което направихме с единично свързани списъци; разликата е, че в този случай вместо да започнем от началото на списъка, започваме от опашката и се движим назад, докато текущият възел стане нула.
- Сложността за получаване на предишния елемент е O(1).
- Сложността за получаване на целия списък е O(n).
def reverse_each return nil unless block_given?
current = self.tail while current yield current current = current.prev end end
Обратен печат
Този метод отпечатва съдържанието на текущия списък назад.
def reverse_print
if self.length == 0
puts "empty"
else
self.reverse_each { |item| puts item.data }
end
end
Кога да използвате двойно свързани списъци
Двойно свързаните списъци работят чудесно, когато трябва да се движите напред и назад върху (малка) последователност от елементи без обвиване.
Например мениджърът на кадри на приложение за редактиране на видео, където потребителят може да се движи напред и назад (кадър по кадър) от началото към филма до края, може да бъде подходящ за тази структура от данни.
И не на последно място, тъй като премахванията са O(1), двойно свързаните списъци могат да бъдат добър избор за онези случаи, когато трябва да се справите с много операции за изтриване.
И така, това е всичко за двойно свързани списъци. Надявам се да ви е харесало!
Можете да получите изходния код от тук.
Следващия път, кръгови свързани списъци.
Благодаря за четенето! и останете на линия.
PS: Не забравяйте да ръкопляскате, ако харесвате тази публикация :)
PS2: Ако сте член на програмата Kindle Unlimited, можете да прочетете малко усъвършенствана версия на тази поредица безплатно на вашето устройство Kindle.