Lista dwukierunkowa
Ostatnia aktualizacja
Lista dwukierunkowa to lista, w której każdy węzeł przechowuje dwa wskaźniki: next (na następny węzeł) i prev (na poprzedni). To dodatkowe połączenie wstecz pozwala przechodzić listę w obu kierunkach i usuwać węzeł w O(1), gdy masz już do niego referencję, bo do poprzednika docierasz bezpośrednio, zamiast iść od głowy. Kliknij odtwarzanie powyżej i zobacz, jak węzły łączą się i przepinają w obie strony.
Kosztem jest jeden dodatkowy wskaźnik na węzeł i więcej pracy przy aktualizacjach: każde wstawienie i usunięcie musi zaktualizować zarówno next, jak i prev u sąsiadów. To struktura stojąca za wieloma kolejkami dwustronnymi i pamięciami podręcznymi LRU, w których liczy się szybkie usuwanie z obu końców.
Złożoność czasowa
| Operacja | Złożoność | Uwagi |
|---|---|---|
| Wstawianie na początek/koniec | O(1) | Ze wskaźnikami head i tail |
| Usuwanie znanego węzła | O(1) | Bezpośredni dostęp do prev, bez przechodzenia |
| Wyszukiwanie | O(n) | Nadal liniowe przeglądanie |
| Dostęp po indeksie | O(n) | Brak dostępu swobodnego |
Lista jednokierunkowa a dwukierunkowa
| Aspekt | Jednokierunkowa | Dwukierunkowa |
|---|---|---|
| Wskaźniki na węzeł | 1 (next) | 2 (next + prev) |
| Przechodzenie wstecz | Nie | Tak |
| Usuwanie znanego węzła | O(n) (szukanie prev) | O(1) |
| Narzut pamięci | Mniejszy | Większy |
Przykład krok po kroku
Budowanie [10, 20, 30] przez dodawanie na koniec, a potem usunięcie węzła 20:
| Krok | Struktura | Działanie |
|---|---|---|
| Start | null | Pusta lista: head i tail mają wartość null |
| Dodaj 10 | 10 | Pierwszy węzeł; head i tail wskazują na niego, prev = next = null |
| Dodaj 20 | 10 <-> 20 | Ustaw 10.next = 20 i 20.prev = 10; tail = 20 |
| Dodaj 30 | 10 <-> 20 <-> 30 | Ustaw 20.next = 30 i 30.prev = 20; tail = 30 |
| Usuń 20 | 10 <-> 30 | Używając 20.prev i 20.next: ustaw 10.next = 30 i 30.prev = 10 w O(1) |
Kiedy używać listy dwukierunkowej
| Używaj, gdy | Unikaj, gdy |
|---|---|
| Musisz przechodzić listę lub łączyć jej fragmenty w obu kierunkach | Zawsze poruszasz się tylko do przodu: lista jednokierunkowa jest lżejsza |
Usuwasz dowolne węzły, do których masz już referencję (O(1)) | Głównie odwołujesz się do elementów po pozycji: użyj tablicy z dostępem O(1) |
| Implementujesz kolejkę dwustronną, pamięć podręczną LRU lub historię cofania | Pamięci jest mało: dodatkowy wskaźnik prev podwaja narzut połączeń |
| Wstawienia i usunięcia często zachodzą na obu końcach | Danych jest mało i rzadko się zmieniają: kopiowanie tablicy jest tańsze |
Doubly Linked List: kod
Przejrzysta, gotowa do uruchomienia implementacja algorytmu Doubly Linked List w językach: Python, JavaScript, Java, C++, C. Wybierz język, skopiuj kod albo otwórz go od razu w edytorze online Coddy.
Doubly Linked List: kod (Python)
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.prev = None5 self.next = None6
7
8class DoublyLinkedList:9 def __init__(self):10 self.head = None11 self.tail = None12
13 def append(self, value):14 node = Node(value)15 if self.tail is None:16 self.head = self.tail = node17 return18 # Wire both directions: old tail <-> new node19 node.prev = self.tail20 self.tail.next = node21 self.tail = node22
23 def prepend(self, value):24 node = Node(value)25 if self.head is None:26 self.head = self.tail = node27 return28 node.next = self.head29 self.head.prev = node30 self.head = node31
32 def forward(self):33 values, current = [], self.head34 while current:35 values.append(current.value)36 current = current.next37 return values38
39 def backward(self):40 values, current = [], self.tail41 while current:42 values.append(current.value)43 current = current.prev44 return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49 lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())Doubly Linked List: kod (JavaScript)
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.prev = null;5 this.next = null;6 }7}8
9class DoublyLinkedList {10 constructor() {11 this.head = null;12 this.tail = null;13 }14
15 // Tail pointer makes append O(1)16 append(value) {17 const node = new Node(value);18 if (!this.tail) {19 this.head = node;20 this.tail = node;21 return;22 }23 node.prev = this.tail;24 this.tail.next = node;25 this.tail = node;26 }27
28 forward() {29 const out = [];30 for (let n = this.head; n; n = n.next) out.push(n.value);31 return out;32 }33
34 backward() {35 const out = [];36 for (let n = this.tail; n; n = n.prev) out.push(n.value);37 return out;38 }39}40
41const list = new DoublyLinkedList();42for (const value of [10, 20, 30, 40]) list.append(value);43console.log("Forward: ", list.forward().join(" <-> "));44console.log("Backward:", list.backward().join(" <-> "));Doubly Linked List: kod (Java)
Java
1public class Main {2 static class Node {3 int value;4 Node prev, next;5 Node(int value) { this.value = value; }6 }7
8 static Node head, tail;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = tail = node; return; }13 node.prev = tail;14 tail.next = node;15 tail = node;16 }17
18 // Unlink in O(1) once found: fix both neighbor pointers19 static void delete(int value) {20 for (Node cur = head; cur != null; cur = cur.next) {21 if (cur.value != value) continue;22 if (cur.prev != null) cur.prev.next = cur.next; else head = cur.next;23 if (cur.next != null) cur.next.prev = cur.prev; else tail = cur.prev;24 return;25 }26 }27
28 public static void main(String[] args) {29 append(1);30 append(2);31 append(3);32 append(4);33
34 StringBuilder forward = new StringBuilder("Forward:");35 for (Node cur = head; cur != null; cur = cur.next) forward.append(" ").append(cur.value);36 System.out.println(forward);37
38 StringBuilder backward = new StringBuilder("Backward:");39 for (Node cur = tail; cur != null; cur = cur.prev) backward.append(" ").append(cur.value);40 System.out.println(backward);41
42 delete(3);43 StringBuilder after = new StringBuilder("After delete 3:");44 for (Node cur = head; cur != null; cur = cur.next) after.append(" ").append(cur.value);45 System.out.println(after);46 }47}Doubly Linked List: kod (C++)
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* prev = nullptr;6 Node* next = nullptr;7 explicit Node(int v) : value(v) {}8};9
10struct DoublyLinkedList {11 Node* head = nullptr;12 Node* tail = nullptr;13
14 void append(int value) {15 Node* node = new Node(value);16 if (tail == nullptr) {17 head = tail = node;18 return;19 }20 node->prev = tail; // link both directions21 tail->next = node;22 tail = node;23 }24
25 void prepend(int value) {26 Node* node = new Node(value);27 if (head == nullptr) {28 head = tail = node;29 return;30 }31 node->next = head;32 head->prev = node;33 head = node;34 }35
36 void printForward() const {37 for (Node* cur = head; cur != nullptr; cur = cur->next) {38 std::cout << cur->value << " <-> ";39 }40 std::cout << "null\n";41 }42
43 void printBackward() const {44 for (Node* cur = tail; cur != nullptr; cur = cur->prev) {45 std::cout << cur->value << " <-> ";46 }47 std::cout << "null\n";48 }49};50
51int main() {52 DoublyLinkedList list;53 for (int value : {10, 20, 30}) list.append(value);54 list.prepend(5);55 std::cout << "Forward: ";56 list.printForward();57 std::cout << "Backward: ";58 list.printBackward();59 return 0;60}Doubly Linked List: kod (C)
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* prev;7 struct Node* next;8} Node;9
10Node* head = NULL;11Node* tail = NULL;12
13Node* newNode(int value) {14 Node* n = calloc(1, sizeof(Node));15 n->value = value;16 return n;17}18
19void append(int value) {20 Node* node = newNode(value);21 if (tail == NULL) {22 head = tail = node;23 return;24 }25 node->prev = tail; // link both directions26 tail->next = node;27 tail = node;28}29
30void prepend(int value) {31 Node* node = newNode(value);32 if (head == NULL) {33 head = tail = node;34 return;35 }36 node->next = head;37 head->prev = node;38 head = node;39}40
41void printForward(void) {42 for (Node* cur = head; cur != NULL; cur = cur->next) {43 printf("%d <-> ", cur->value);44 }45 printf("NULL\n");46}47
48void printBackward(void) {49 for (Node* cur = tail; cur != NULL; cur = cur->prev) {50 printf("%d <-> ", cur->value);51 }52 printf("NULL\n");53}54
55int main(void) {56 int values[] = {10, 20, 30};57 for (int i = 0; i < 3; i++) append(values[i]);58 prepend(5);59 printf("Forward: ");60 printForward();61 printf("Backward: ");62 printBackward();63 return 0;64}Lista dwukierunkowa: najczęstsze pytania
Czym różni się lista jednokierunkowa od dwukierunkowej?
Lista jednokierunkowa ma jeden wskaźnik na węzeł (
next), więc można poruszać się tylko do przodu. Lista dwukierunkowa dodaje wskaźnik prev, który pozwala przechodzić wstecz i usuwać węzeł, do którego masz referencję, w O(1), kosztem dodatkowego wskaźnika na węzeł i aktualizacji dwóch połączeń przy każdej zmianie.Kiedy lista dwukierunkowa jest warta dodatkowej pamięci?
Gdy potrzebujesz przechodzenia wstecz albo usuwania w
O(1) dowolnych węzłów, do których masz już referencję. Klasyczne przypadki to kolejki dwustronne (deque) i pamięci podręczne LRU, w których wpisy są często przenoszone i usuwane z obu końców.Dlaczego lista dwukierunkowa może usunąć węzeł w O(1)?
Aby usunąć węzeł, trzeba połączyć jego poprzednika z następnikiem. W liście jednokierunkowej trzeba by przejść od głowy, aby znaleźć poprzednika (
O(n)); w liście dwukierunkowej wskaźnik prev węzła daje poprzednika bezpośrednio, więc przepięcie ma złożoność O(1).Lista dwukierunkowa czy tablica: co wybrać?
Użyj tablicy, gdy potrzebujesz dostępu po indeksie w
O(1) i iteracji przyjaznej dla pamięci podręcznej, a wstawienia zachodzą głównie na końcu. Użyj listy dwukierunkowej, gdy często wstawiasz lub usuwasz elementy w środku albo na obu końcach, mając referencję do węzła, bo to O(1) wobec przesuwania O(n) w tablicy. Tablice wygrywają pamięcią i lokalnością; lista wygrywa przy zmianach struktury.Czym jest węzeł wartownik w liście dwukierunkowej?
Wartownik (węzeł pozorny) to element zastępczy umieszczony przed głową i/lub za ogonem, dzięki któremu lista nigdy nie jest naprawdę pusta. Eliminuje sprawdzanie
null dla head, tail i wstawień lub usunięć na granicach, więc każda operacja korzysta z tego samego kodu przepinania. Wiele produkcyjnych implementacji pamięci podręcznej LRU używa dwóch wartowników, aby nie obsługiwać końców osobno.Jaki jest najczęstszy błąd przy usuwaniu z listy dwukierunkowej?
Zapomnienie o aktualizacji
head lub tail przy usuwaniu pierwszego lub ostatniego węzła, co zostawia wiszący wskaźnik na zwolniony węzeł. Zawsze sprawdź, czy node.prev ma wartość null (zaktualizuj head) albo czy node.next ma wartość null (zaktualizuj tail), zanim przepniesz sąsiadów.Powiązane materiały
Więcej wizualizacji
