Lista połączona pojedynczo a lista podwójnie połączona
Połączona lista to liniowa struktura danych używana do przechowywania kolekcji danych. Połączona lista alokuje pamięć do swoich elementów oddzielnie we własnym bloku pamięci, a ogólną strukturę uzyskuje się przez połączenie tych elementów jako ogniwa w łańcuchu. Lista pojedynczo połączona składa się z sekwencji węzłów, a każdy węzeł ma odniesienie do następnego węzła w sekwencji. Podwójnie połączona lista zawiera sekwencję węzłów, w których każdy węzeł zawiera odniesienie do następnego węzła, a także do poprzedniego węzła.
Lista połączona pojedynczo
Każdy element na liście połączonej pojedynczo ma dwa pola, jak pokazano na rysunku 1. Pole danych zawiera aktualnie przechowywane dane, a następne pole zawiera odniesienie do następnego elementu w łańcuchu. Pierwszy element połączonej listy jest przechowywany jako nagłówek połączonej listy.
Rysunek 2 przedstawia pojedynczo połączoną listę z trzema elementami. Każdy element przechowuje swoje dane, a wszystkie elementy z wyjątkiem ostatniego przechowują odniesienie do następnego elementu. Ostatni element zawiera wartość null w następnym polu. Dostęp do dowolnego elementu na liście można uzyskać, zaczynając od nagłówka i podążając za następnym wskaźnikiem, aż napotkasz wymagany element.
Lista podwójnie połączona
Każdy element na podwójnie połączonej liście ma trzy pola, jak pokazano na rysunku 3. Podobnie jak w przypadku listy połączonej pojedynczo, pole danych zawiera rzeczywiste przechowywane dane, a następne pole zawiera odniesienie do następnego elementu w łańcuchu. Dodatkowo poprzednie pole zawiera odwołanie do poprzedniego elementu w łańcuchu. Pierwszy element połączonej listy jest przechowywany jako nagłówek połączonej listy.
Rysunek 4 przedstawia podwójnie powiązaną listę z trzema elementami. Wszystkie elementy pośrednie przechowują odniesienia do pierwszego i poprzedniego elementu. Ostatni element na liście zawiera wartość null w swoim następnym polu, a pierwszy element na liście zawiera wartość null w swoim poprzednim polu. Podwójnie powiązana lista może być przemieszczana do przodu, podążając za kolejnymi odniesieniami w każdym elemencie i podobnie można przechodzić wstecz, korzystając z poprzednich odwołań w każdym elemencie.
Jaka jest różnica między listą pojedynczo połączoną a listą podwójnie połączoną?
Każdy element na liście z pojedynczym łączem zawiera odniesienie do następnego elementu na liście, podczas gdy każdy element na liście podwójnie połączonej zawiera odniesienia do następnego elementu, a także do poprzedniego elementu na liście. Listy podwójnie połączone wymagają więcej miejsca dla każdego elementu na liście, a operacje elementarne, takie jak wstawianie i usuwanie, są bardziej złożone, ponieważ mają do czynienia z dwoma odniesieniami. Ale listy z podwójnymi linkami umożliwiają łatwiejszą manipulację, ponieważ umożliwiają przechodzenie po liście w przód i w tył.
