Dwukierunkowe listy wiązane
Połączenia w obu kierunkach
Dwukierunkowe listy wiązane to bezpłatna lekcja C Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.
Łącza w obu kierunkach
Lista dwukierunkowa zapewnia każdemu węzłowi dwa wskaźniki: jeden do węzła next, a drugi do węzła prev (poprzedniego).
Umożliwia to przechodzenie przez listę w obu kierunkach i upraszcza usuwanie.
#include <stdio.h>
struct Node {
int value;
struct Node *prev;
struct Node *next;
};
int main(void) {
printf("Each node links forward and backward\n");
return 0;
}Definiowanie węzła
Struktura zawiera wskaźnik prev obok next. Na końcach listy oba mają wartość NULL.
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
int main(void) {
struct Node *n = malloc(sizeof(struct Node));
n->value = 1; n->prev = NULL; n->next = NULL;
printf("%d\n", n->value);
free(n);
return 0;
}Funkcja pomocnicza tworząca węzeł
Tak jak wcześniej, funkcja pomocnicza centralizuje alokowanie pamięci. Ustawia zarówno prev, jak i next na NULL.
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v) {
struct Node *n = malloc(sizeof(struct Node));
n->value = v; n->prev = NULL; n->next = NULL;
return n;
}
int main(void) {
struct Node *n = make(42);
printf("%d\n", n->value);
free(n);
return 0;
}Łączenie węzłów w obu kierunkach
Podczas łączenia dwóch węzłów trzeba zaktualizować oba kierunki: next pierwszego węzła i prev drugiego.
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
int main(void) {
struct Node *a = make(1), *b = make(2);
a->next = b;
b->prev = a;
printf("forward %d, back %d\n", a->next->value, b->prev->value);
free(a); free(b);
return 0;
}Wstawianie na początku
Podczas dodawania na początku: next nowego węzła wskazuje starą głowę, prev starej głowy wskazuje nowy węzeł, a następnie głowa zostaje przesunięta na nowy węzeł.
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
void push(struct Node **head, int v) {
struct Node *n = make(v);
n->next = *head;
if (*head) (*head)->prev = n;
*head = n;
}
int main(void) {
struct Node *head = NULL;
push(&head, 2); push(&head, 1);
printf("%d %d\n", head->value, head->next->value);
return 0;
}Przechodzenie do przodu
Przechodzenie do przodu wygląda tak samo jak w liście jednokierunkowej: należy podążać za next aż do wartości NULL.
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
int main(void) {
struct Node *a = make(1), *b = make(2);
a->next = b; b->prev = a;
for (struct Node *p = a; p; p = p->next) printf("%d ", p->value);
printf("\n");
free(a); free(b);
return 0;
}Przechodzenie do tyłu
Największą zaletą jest możliwość przechodzenia od dowolnego węzła wstecz za pomocą wskaźników prev aż do głowy.
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
int main(void) {
struct Node *a = make(1), *b = make(2), *c = make(3);
a->next = b; b->prev = a; b->next = c; c->prev = b;
for (struct Node *p = c; p; p = p->prev) printf("%d ", p->value);
printf("\n");
free(a); free(b); free(c);
return 0;
}Łatwiejsze usuwanie
Ponieważ każdy węzeł zna swojego poprzednika, można go usunąć bez wyszukiwania poprzedniego węzła.
Wystarczy połączyć node->prev z node->next w obu kierunkach.
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
void del(struct Node **head, struct Node *n) {
if (n->prev) n->prev->next = n->next; else *head = n->next;
if (n->next) n->next->prev = n->prev;
free(n);
}
int main(void) {
struct Node *a = make(1), *b = make(2), *c = make(3);
a->next=b; b->prev=a; b->next=c; c->prev=b;
struct Node *head = a;
del(&head, b);
printf("%d %d\n", head->value, head->next->value);
return 0;
}Aktualizowanie obu sąsiadów
Podczas usuwania węzła należy zawsze poprawić wartość next poprzedniego węzła oraz wartość prev następnego węzła.
Na obu końcach należy sprawdzać wartość NULL, aby nie wyłuskać nieistniejącego sąsiada.
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
int main(void) {
struct Node *a = make(1), *b = make(2);
a->next = b; b->prev = a;
a->next = NULL;
free(b);
printf("now only %d remains\n", a->value);
free(a);
return 0;
}Przechowywanie wskaźnika ogona
Wiele list dwukierunkowych przechowuje również wskaźnik tail do ostatniego węzła, co umożliwia dołączanie w czasie O(1) i przechodzenie wstecz od końca.
#include <stdio.h>
#include <stdlib.h>
struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}
int main(void) {
struct Node *head = make(1), *tail = head;
struct Node *n = make(2);
tail->next = n; n->prev = tail; tail = n;
printf("tail = %d\n", tail->value);
free(head); free(n);
return 0;
}Kompromisy
Listy dwukierunkowe wymagają dodatkowej pamięci (o jeden wskaźnik więcej na węzeł) i aktualizowania dwóch łączy przy każdej zmianie.
W zamian zapewniają przechodzenie w obu kierunkach oraz usuwanie znanego węzła w czasie O(1). Należy wybrać rozwiązanie odpowiednie do swoich potrzeb.
#include <stdio.h>
int main(void) {
printf("Singly: less memory, one-way\n");
printf("Doubly: more memory, two-way + easy delete\n");
return 0;
}Szybki sprawdzian
Sprawdź swoją wiedzę na temat list dwukierunkowych.
Podsumowanie
Poznał(a) Pan/Pani listy dwukierunkowe:
- Każdy węzeł ma wskaźniki
previnext. - Łączenie wymaga aktualizowania obu kierunków.
- Można przechodzić przez listę do przodu i do tyłu oraz usuwać znany węzeł w czasie O(1).
- Kosztem jest dodatkowa pamięć i większa liczba aktualizacji wskaźników; wskaźnik tail umożliwia dołączanie w czasie O(1).
Często zadawane pytania
Czy lekcja „Dwukierunkowe listy wiązane” jest bezpłatna?
Tak — pełny tekst „Dwukierunkowe listy wiązane” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Dwukierunkowe listy wiązane”?
Połączenia w obu kierunkach Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć C Academy?
Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Dwukierunkowe listy wiązane”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?
Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Jednokierunkowe listy wiązane
- Wstawianie i usuwanie
- Przechodzenie i wyszukiwanie
- Dwukierunkowe listy wiązane