Lista połączona pojedynczo a lista połączona podwójnie
Lista połączona to liniowa struktura danych służąca do przechowywania zbioru danych. Lista połączona przydziela 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 ogniw 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. Lista podwójnie połączona zawiera sekwencję węzłów, w których każdy węzeł zawiera odniesienie do następnego węzła, jak również do poprzedniego węzła.
Lista pojedynczo połączona
Każdy element listy połączonej pojedynczo ma dwa pola, jak pokazano na rysunku 1. Pole danych zawiera faktycznie przechowywane dane, a następne pole zawiera odniesienie do następnego elementu w łańcuchu. Pierwszy element listy połączonej jest przechowywany jako nagłówek listy połączonej.
Rysunek 2 przedstawia listę połączoną pojedynczo 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 swoim następnym polu. Dostęp do dowolnego elementu na liście można uzyskać, zaczynając od początku i podążając za następnym wskaźnikiem, aż do osiągnięcia wymaganego elementu.
Lista podwójnie połączona
Każdy element w podwójnie połączonej liście ma trzy pola, jak pokazano na rysunku 3. Podobnie jak w przypadku pojedynczo połączonej listy, pole danych zawiera rzeczywiste przechowywane dane, a następne pole zawiera odniesienie do następnego elementu w łańcuchu. Dodatkowo poprzednie pole zawiera odniesienie do poprzedniego elementu w łańcuchu. Pierwszy element listy połączonej jest przechowywany jako nagłówek listy połączonej.
Rysunek 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 swoim następnym polu, a pierwszy element na liście zawiera wartość null w swoim poprzednim polu. Po liście podwójnie połączonej można przechodzić do przodu, podążając za kolejnymi odwołaniami w każdym elemencie i podobnie można przechodzić wstecz, używając poprzednich odwołań w każdym elemencie.
Jaka jest różnica między listą połączoną pojedynczo a listą połączoną podwójnie?
Każdy element na liście pojedynczo połączonej 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, jak również do poprzedniego elementu na liście. Listy podwójnie połączone wymagają więcej miejsca na każdy element na liście, a podstawowe operacje, takie jak wstawianie i usuwanie, są bardziej złożone, ponieważ mają do czynienia z dwoma odwołaniami. Jednak listy podwójnych linków umożliwiają łatwiejszą manipulację, ponieważ umożliwiają przechodzenie po liście w kierunku do przodu i do tyłu.
