Lista jednokierunkowa (linked list)
Ostatnia aktualizacja
Lista jednokierunkowa przechowuje sekwencję jako łańcuch węzłów, w którym każdy węzeł zawiera wartość i wskaźnik na następny węzeł. W przeciwieństwie do tablicy węzły nie leżą w pamięci obok siebie: aby przejść listę, podążasz za wskaźnikami next. Kliknij odtwarzanie powyżej i zobacz, jak węzły są dołączane na początku i na końcu, jak wartość jest wyszukiwana przez przejście łańcucha i jak węzeł jest usuwany przez przepięcie wskaźnika.
Wstawianie lub usuwanie na początku kosztuje O(1), bo wystarczy przestawić głowę. Dotarcie do pozycji w środku lub na końcu kosztuje O(n), bo najpierw trzeba tam dojść. Ten kompromis, czyli tanie końce i brak dostępu swobodnego, odróżnia listę jednokierunkową od tablicy.
Złożoność czasowa
| Operacja | Złożoność | Uwagi |
|---|---|---|
| Wstawianie na początek | O(1) | Przestawienie głowy |
| Wstawianie na koniec | O(n) | Najpierw przejście do końca (O(1) ze wskaźnikiem tail) |
| Wyszukiwanie | O(n) | Podążanie za wskaźnikami next |
| Usuwanie głowy | O(1) | Przestawienie głowy za usuwany węzeł |
| Dostęp po indeksie | O(n) | Brak dostępu swobodnego |
Lista jednokierunkowa a tablica
| Aspekt | Lista jednokierunkowa | Tablica |
|---|---|---|
| Pamięć | Rozproszone węzły + wskaźniki | Ciągły blok |
| Dostęp swobodny | O(n) | O(1) |
| Wstawianie/usuwanie na początku | O(1) | O(n) (przesunięcie) |
| Współpraca z pamięcią podręczną | Słaba | Dobra |
Przykład krok po kroku
Budowanie listy [10, 20], dodanie 5 na początek, a potem usunięcie 20:
| Krok | Struktura | Działanie |
|---|---|---|
| Start | head -> null | Pusta lista |
| Wstaw 10 na początek | head -> 10 -> null | Przestaw głowę na nowy węzeł, którego next to stara głowa (null) |
| Wstaw 20 na koniec | head -> 10 -> 20 -> null | Przejdź do węzła 10, ustaw jego next na nowy węzeł 20 |
| Wstaw 5 na początek | head -> 5 -> 10 -> 20 -> null | Nowy węzeł 5 wskazuje na starą głowę 10; głowa wskazuje teraz na 5 |
| Usuń 20 | head -> 5 -> 10 -> null | Przejdź do 10, zmień jego next z 20 na null; węzeł 20 zostaje odłączony |
Kiedy używać listy jednokierunkowej
| Używaj, gdy | Unikaj, gdy |
|---|---|
| Znacznie częściej wstawiasz lub usuwasz na końcach (lub przy trzymanym węźle), niż odwołujesz się po indeksie | Potrzebujesz szybkiego dostępu swobodnego po pozycji (indeksowanie w O(1)) |
| Rozmiar często się zmienia i nie chcesz kosztów zmiany rozmiaru ani kopiowania | Wykonujesz ciasne pętle, w których o wydajności decyduje lokalność pamięci podręcznej |
| Budujesz kolejkę, stos lub listę sąsiedztwa | Pamięci jest mało: każdy węzeł płaci za dodatkowy wskaźnik na element |
| Potrzebujesz stabilnych referencji do węzłów, które przetrwają wstawienia w innych miejscach | Głównie czytasz dane i rzadko je zmieniasz, więc tablica jest prostsza i szybsza |
Linked List: kod
Przejrzysta, gotowa do uruchomienia implementacja algorytmu 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.
Linked List: kod (Python)
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.next = None5
6
7class LinkedList:8 def __init__(self):9 self.head = None10
11 def append(self, value):12 node = Node(value)13 if self.head is None:14 self.head = node15 return16 current = self.head17 while current.next:18 current = current.next19 current.next = node20
21 def find(self, value):22 current = self.head23 while current:24 if current.value == value:25 return True26 current = current.next27 return False28
29 def delete(self, value):30 # Re-link the previous node around the match31 current, prev = self.head, None32 while current:33 if current.value == value:34 if prev is None:35 self.head = current.next36 else:37 prev.next = current.next38 return True39 prev, current = current, current.next40 return False41
42 def __str__(self):43 values, current = [], self.head44 while current:45 values.append(str(current.value))46 current = current.next47 return " -> ".join(values) + " -> None"48
49
50lst = LinkedList()51for value in [3, 7, 1, 9]:52 lst.append(value)53
54print("List: ", lst)55print("find(7): ", lst.find(7))56lst.delete(1)57print("After delete(1):", lst)Linked List: kod (JavaScript)
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.next = null;5 }6}7
8class LinkedList {9 constructor() {10 this.head = null;11 }12
13 append(value) {14 const node = new Node(value);15 if (!this.head) {16 this.head = node;17 return;18 }19 let current = this.head;20 while (current.next) current = current.next;21 current.next = node;22 }23
24 find(value) {25 for (let n = this.head; n; n = n.next) {26 if (n.value === value) return n;27 }28 return null;29 }30
31 delete(value) {32 if (!this.head) return false;33 if (this.head.value === value) {34 this.head = this.head.next;35 return true;36 }37 // Walk to the node just before the one to remove38 for (let n = this.head; n.next; n = n.next) {39 if (n.next.value === value) {40 n.next = n.next.next;41 return true;42 }43 }44 return false;45 }46
47 toArray() {48 const out = [];49 for (let n = this.head; n; n = n.next) out.push(n.value);50 return out;51 }52}53
54const list = new LinkedList();55for (const value of [10, 20, 30, 40]) list.append(value);56console.log("List:", list.toArray().join(" -> "));57console.log("find(30):", list.find(30) !== null);58list.delete(20);59console.log("After delete(20):", list.toArray().join(" -> "));Linked List: kod (Java)
Java
1public class Main {2 static class Node {3 int value;4 Node next;5 Node(int value) { this.value = value; }6 }7
8 static Node head;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = node; return; }13 Node cur = head;14 while (cur.next != null) cur = cur.next;15 cur.next = node;16 }17
18 static boolean find(int value) {19 for (Node cur = head; cur != null; cur = cur.next) {20 if (cur.value == value) return true;21 }22 return false;23 }24
25 // Unlink the first node holding value26 static void delete(int value) {27 if (head == null) return;28 if (head.value == value) { head = head.next; return; }29 Node cur = head;30 while (cur.next != null && cur.next.value != value) cur = cur.next;31 if (cur.next != null) cur.next = cur.next.next;32 }33
34 static void print() {35 StringBuilder sb = new StringBuilder();36 for (Node cur = head; cur != null; cur = cur.next) {37 sb.append(cur.value).append(" -> ");38 }39 System.out.println(sb.append("null"));40 }41
42 public static void main(String[] args) {43 append(3); append(7); append(1); append(9);44 print();45 System.out.println("find 7: " + find(7));46 delete(7);47 print();48 System.out.println("find 7: " + find(7));49 }50}Linked List: kod (C++)
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* next = nullptr;6 explicit Node(int v) : value(v) {}7};8
9struct LinkedList {10 Node* head = nullptr;11
12 void append(int value) {13 Node* node = new Node(value);14 if (head == nullptr) {15 head = node;16 return;17 }18 Node* cur = head;19 while (cur->next != nullptr) cur = cur->next;20 cur->next = node;21 }22
23 bool find(int value) const {24 for (Node* cur = head; cur != nullptr; cur = cur->next) {25 if (cur->value == value) return true;26 }27 return false;28 }29
30 void remove(int value) {31 if (head == nullptr) return;32 if (head->value == value) { // removing the head is a special case33 Node* old = head;34 head = head->next;35 delete old;36 return;37 }38 for (Node* cur = head; cur->next != nullptr; cur = cur->next) {39 if (cur->next->value == value) {40 Node* old = cur->next;41 cur->next = old->next;42 delete old;43 return;44 }45 }46 }47
48 void print() const {49 for (Node* cur = head; cur != nullptr; cur = cur->next) {50 std::cout << cur->value << " -> ";51 }52 std::cout << "null\n";53 }54};55
56int main() {57 LinkedList list;58 for (int value : {10, 20, 30, 40}) list.append(value);59 list.print();60 std::cout << std::boolalpha << "find(30): " << list.find(30) << "\n";61 list.remove(20);62 list.remove(10);63 list.print();64 return 0;65}Linked List: kod (C)
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* next;8} Node;9
10Node* head = NULL;11
12void append(int value) {13 Node* node = malloc(sizeof(Node));14 node->value = value;15 node->next = NULL;16 if (head == NULL) {17 head = node;18 return;19 }20 Node* cur = head;21 while (cur->next != NULL) cur = cur->next;22 cur->next = node;23}24
25bool find(int value) {26 for (Node* cur = head; cur != NULL; cur = cur->next) {27 if (cur->value == value) return true;28 }29 return false;30}31
32void deleteValue(int value) {33 if (head == NULL) return;34 if (head->value == value) { // removing the head is a special case35 Node* old = head;36 head = head->next;37 free(old);38 return;39 }40 for (Node* cur = head; cur->next != NULL; cur = cur->next) {41 if (cur->next->value == value) {42 Node* old = cur->next;43 cur->next = old->next;44 free(old);45 return;46 }47 }48}49
50void printList(void) {51 for (Node* cur = head; cur != NULL; cur = cur->next) {52 printf("%d -> ", cur->value);53 }54 printf("NULL\n");55}56
57int main(void) {58 int values[] = {10, 20, 30, 40};59 for (int i = 0; i < 4; i++) append(values[i]);60 printList();61 printf("find(30): %s\n", find(30) ? "true" : "false");62 deleteValue(20);63 deleteValue(10);64 printList();65 return 0;66}Lista jednokierunkowa: najczęstsze pytania
Czym różni się lista jednokierunkowa od tablicy?
Tablica przechowuje elementy w jednym ciągłym bloku, co daje dostęp swobodny w
O(1), ale wstawianie i usuwanie w O(n) z przesuwaniem elementów. Lista jednokierunkowa przechowuje węzły w dowolnych miejscach pamięci połączone wskaźnikami, co daje wstawianie i usuwanie w O(1) w znanej pozycji, ale dostęp w O(n), bo trzeba przejść łańcuch.Kiedy używać listy jednokierunkowej?
Listy jednokierunkowe sprawdzają się, gdy często wstawiasz lub usuwasz elementy na końcach (albo przy węźle, do którego masz już referencję) i rzadko potrzebujesz dostępu swobodnego, na przykład w kolejkach, stosach, listach sąsiedztwa i pamięciach podręcznych LRU. Jeśli potrzebujesz szybkiego dostępu po indeksie, zwykle lepsza jest tablica lub tablica dynamiczna.
Jaka jest złożoność czasowa listy jednokierunkowej?
Wstawianie lub usuwanie na początku kosztuje
O(1). Wyszukiwanie albo dotarcie do końca bez wskaźnika tail kosztuje O(n), bo podążasz za wskaźnikami next jeden po drugim. Nie ma dostępu swobodnego w O(1): odwołanie po indeksie w liście jednokierunkowej kosztuje O(n).Czym różni się lista jednokierunkowa od dwukierunkowej?
Lista jednokierunkowa przechowuje w każdym węźle tylko wskaźnik
next, więc można iść w jednym kierunku, a usunięcie węzła wymaga referencji do jego poprzednika. Lista dwukierunkowa dodaje wskaźnik prev, który umożliwia przechodzenie wstecz i usuwanie trzymanego węzła w O(1), kosztem dodatkowego wskaźnika na węzeł i większej pracy przy każdym wstawieniu i usunięciu.Dlaczego wstawianie na koniec kosztuje O(n), skoro wstawianie na początek kosztuje O(1)?
Wstawianie na początek tylko przepina wskaźnik
head, co jest stałą pracą. Dotarcie do końca oznacza podążanie za wskaźnikami next od głowy aż do samego końca, co kosztuje O(n). Osobny wskaźnik tail sprawia, że wstawianie na koniec też kosztuje O(1), dlatego w praktyce listy często śledzą oba końce.Czy listy jednokierunkowe mają wstawianie w O(1) wszędzie?
Nie, to częste nieporozumienie. Samo wstawienie kosztuje
O(1) tylko wtedy, gdy masz już wskaźnik na węzeł, za którym wstawiasz. Znalezienie tej pozycji po wartości lub indeksie nadal kosztuje O(n), bo trzeba do niej dojść po łańcuchu.Powiązane materiały
Więcej wizualizacji
