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

Ако не сте прочели предишната ми публикация за единично свързани списъци, препоръчвам ви да го направите, защото този път ще работим върху това, което изградихме миналия път.

В двойно свързаните списъци елементите са представени от възли, които съдържат три атрибута:

  • Стойността, която елементът притежава.
  • Указател към следващия възел в списъка.
  • Указател към предишния възел в списъка.

Както и при единично свързаните списъци, първият елемент на списъка се нарича „глава“, а последният се нарича „опашка“.

Границите на двойно свързаните списъци са ограничени от предходния указател на първия елемент и следващия указател на последния. И двата указателя трябва да бъдат зададени на нула.

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

Премахване

Премахва дадения възел от свързания списък и коригира указателите, за да поддържа елементите заедно.

Ако възелът, който трябва да премахнем, е главата на списъка, трябва да покрием две ситуации:

  1. Head е единственият възел в списъка. Задаваме head и tail на нула и сме готови.
  2. 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 стъпки:

  1. Посочете предишния показалец на главата на списъка, който добавяме към опашката на текущия списък.
  2. Насочете следващия указател от опашката на текущия списък към главата на списъка, който добавяме.
  3. Задайте опашката на текущия списък на опашката на списъка, който добавяме.
  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.