Różnica między listą pojedynczo połączoną a listą podwójnie połączoną

Lista połączona pojedynczo a lista połączona podwójnie

Lista połączona to liniowa struktura danych służąca do przechowywania kolekcji danych. Połączona lista przydziela pamięć jej elementom osobno we własnym bloku pamięci, a ogólną strukturę uzyskuje się poprzez połączenie tych elementów jako ogniwa w łańcuchu. Pojedynczo połączona lista 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.

Pojedynczo połączona lista

Każdy element na pojedynczo połączonej liście ma dwa pola, jak pokazano na rysunku 1. Pole danych przechowuje rzeczywiste dane przechowywane, 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.

Ryc. 2 przedstawia pojedynczo połączoną listę z trzema elementami. Każdy element przechowuje swoje dane, a wszystkie elementy oprócz 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ż osiągniesz wymagany element.

Podwójnie połączona lista

Każdy element na podwójnie połączonej liście ma trzy pola, jak pokazano na rysunku 3. Podobnie jak w przypadku pojedynczo połączonej listy, pole danych przechowuje rzeczywiste dane przechowywane, a następne pole zawiera odniesienie do następnego elementu w łańcuchu. Ponadto poprzednie pole zawiera odniesienie do poprzedniego elementu w łańcuchu. Pierwszy element połączonej listy jest przechowywany jako nagłówek połączonej listy.

Rycina 4 przedstawia podwójnie połączoną listę z trzema elementami. Wszystkie elementy pośrednie przechowują odniesienia do pierwszego i poprzednich elementów. Ostatni element na liście zawiera wartość null w następnym polu, a pierwszy element na liście ma wartość null w poprzednim polu. Podwójnie połączoną listę można przeglądać do przodu, postępując zgodnie z kolejnymi referencjami w każdym elemencie, podobnie można przeglądać wstecz, używając poprzednich referencji w każdym elemencie.

Jaka jest różnica między listą połączoną pojedynczo a listą podwójnie połączoną?

Każdy element na pojedynczo połączonej liście zawiera odniesienie do następnego elementu na liście, podczas gdy każdy element na podwójnie połączonej liście zawiera odniesienia do następnego elementu, a także poprzedniego elementu na liście. Podwójnie połączone listy wymagają więcej miejsca dla każdego elementu na liście, a podstawowe operacje, takie jak wstawianie i usuwanie, są bardziej złożone, ponieważ mają do czynienia z dwoma referencjami. Ale podwójnie listy linków pozwalają na łatwiejszą manipulację, ponieważ umożliwiają przechodzenie listy w przód i wstecz.