Lista wiązana dwukierunkowa to jedna z fundamentalnych struktur danych używanych w informatyce i programowaniu. W odróżnieniu od list jednokierunkowych, każdy element listy dwukierunkowej posiada dwa wskaźniki: jeden wskazujący na następny element oraz drugi wskazujący na element poprzedni. Dzięki temu możliwe jest nie tylko przechodzenie w przód, ale także cofanie się w strukturze, co czyni tę listę bardziej uniwersalną w wielu zastosowaniach.
Budowa listy dwukierunkowej
Każdy element listy dwukierunkowej, nazywany węzłem (ang. node), składa się z trzech podstawowych części:
- Wartości (danych) – przechowuje informację, którą chcemy zapisać w liście.
- Wskaźnika do następnego węzła – przechowuje referencję do kolejnego elementu w liście.
- Wskaźnika do poprzedniego węzła – przechowuje referencję do poprzedniego elementu w liście.
Dzięki tej budowie każdy węzeł łączy się z dwoma innymi, tworząc podwójną relację, co pozwala na bardziej elastyczne operacje na liście.
Zalety listy wiązanej dwukierunkowej
- Dwukierunkowy dostęp: możliwość przemieszczania się w obie strony.
- Łatwe usuwanie: usunięcie elementu z dowolnego miejsca w liście nie wymaga przesuwania innych elementów.
- Dynamiczne zarządzanie pamięcią: lista nie wymaga z góry zdefiniowanego rozmiaru, w przeciwieństwie do tablic.
Wady listy wiązanej dwukierunkowej
- Większe zużycie pamięci: każdy węzeł przechowuje dwa wskaźniki, co zwiększa zapotrzebowanie na pamięć.
- Złożoność operacji: zarządzanie wskaźnikami podczas dodawania lub usuwania elementów może być bardziej skomplikowane niż w przypadku innych struktur danych.
Implementacja listy wiązanej dwukierunkowej w Pythonie
Oto przykład implementacji listy dwukierunkowej w języku Python:
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def prepend(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
def delete(self, key):
current = self.head
while current:
if current.data == key:
if current.prev:
current.prev.next = current.next
if current.next:
current.next.prev = current.prev
if current == self.head:
self.head = current.next
return
current = current.next
def display(self):
current = self.head
while current:
print(current.data, end=" <-> ")
current = current.next
print("None")
# Przykład użycia
list = DoublyLinkedList()
list.append(10)
list.append(20)
list.prepend(5)
list.display() # Output: 5 <-> 10 <-> 20 <-> None
list.delete(10)
list.display() # Output: 5 <-> 20 <-> NoneOperacje na liście wiązanej dwukierunkowej
Dodawanie elementów
- Na początku: Polega na utworzeniu nowego węzła i ustawieniu go jako nowej głowy listy, z jednoczesnym wskazaniem na dawną głowę.
- Na końcu: Polega na przejściu do ostatniego węzła i dodaniu nowego węzła jako jego następnika.
Usuwanie elementów
Usuwanie elementów z listy dwukierunkowej wymaga aktualizacji wskaźników w poprzednim i następnym węźle, aby ominęły usuwany węzeł.
Wyszukiwanie elementów
Przechodzimy po kolei przez węzły, sprawdzając wartości, dopóki nie znajdziemy poszukiwanego elementu lub nie dotrzemy do końca listy.
Przykłady zastosowań listy wiązanej dwukierunkowej
- Edytory tekstowe: pozwalają na szybkie poruszanie się w obie strony pomiędzy wierszami lub znakami.
- Systemy operacyjne: realizują listy procesów lub historii poleceń.
- Struktury baz danych: służą do implementacji wskaźnikowych struktur danych, takich jak indeksy B-drzew.
Lista wiązana dwukierunkowa to struktura, która pomimo nieco większej złożoności implementacyjnej, znajduje szerokie zastosowanie w rozmaitych dziedzinach informatyki. Jej elastyczność sprawia, że jest niezastąpiona tam, gdzie wymagane jest dynamiczne zarządzanie danymi i szybki dostęp do elementów w obu kierunkach.