Wpisany przez Michał Knasiecki,
16 sierpnia 2005 18:36
Lista jest to liniowo uporządkowany zbiór elementów, z których dowolny element
można usunąć oraz dodać w dowolnym miejscu. Pierwszy i ostatni element listy nazywamy
końcami listy. Szczególnym przypadkiem listy może być stos (gdy pobrać,
odczytać i wstawić element można tylko na końcu listy) lub kolejka
(pobrać i odczytać element można tylko na początku listy, a dodać na końcu).
Listy mogą być posortowane (najmniejszy element jest w korzeniu). Rozważmy przypadek jednokierunkowej listy posortowanej.
Aby dodać element do listy posortowanej należy sprawdzić, w którym miejscu powienien się on znajdować. Sprawdzamy od korzenia, schodząc w dół, jeśli element, który chcemy dodać jest większy od badanego węzła i mniejszy od jego następnika, to należy umieścić go między nimi. Musimy więc ustawić wskaźnik aktualnego węzła na dodawany element, a wskaźnik tego elementu na następnik. Ponieważ jest to lista jednokierunkowa, przeszukiwanie jej należy zawsze zaczynać od korzenia. Dodając więc pierwszy element do pustej listy należy zapamiętać jego wskaźnik, by później móc się do niego przenieść.
W przeciwieństwie do stosu i kolejki listy mogą zawierać dwa wskaźniki. Takie listy nazywamy dwukierunkowymi, poruszać się możemy w niej w obydwu kierunkach, co przyspiesza wszystkie operacje. Oto schemat listy dwukierunkowej:
Listy mogą być posortowane (najmniejszy element jest w korzeniu). Rozważmy przypadek jednokierunkowej listy posortowanej.
Aby dodać element do listy posortowanej należy sprawdzić, w którym miejscu powienien się on znajdować. Sprawdzamy od korzenia, schodząc w dół, jeśli element, który chcemy dodać jest większy od badanego węzła i mniejszy od jego następnika, to należy umieścić go między nimi. Musimy więc ustawić wskaźnik aktualnego węzła na dodawany element, a wskaźnik tego elementu na następnik. Ponieważ jest to lista jednokierunkowa, przeszukiwanie jej należy zawsze zaczynać od korzenia. Dodając więc pierwszy element do pustej listy należy zapamiętać jego wskaźnik, by później móc się do niego przenieść.
W przeciwieństwie do stosu i kolejki listy mogą zawierać dwa wskaźniki. Takie listy nazywamy dwukierunkowymi, poruszać się możemy w niej w obydwu kierunkach, co przyspiesza wszystkie operacje. Oto schemat listy dwukierunkowej:
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Paweł Szulc | C# | Lista jednokierunkowa niesortowana | .cs | .cs | ***** / 4 |
Marian | C/C++ | C++ (lista jednokierunkowa) | .cpp | .cpp | ***** / 51 |
Emil Hotkowski | C/C++ | C++ (lista dwukierunkowa) | .cpp | .cpp | ***** / 24 |
Michał Knasiecki | Delphi/Pascal | Borland Delphi 5 | .pas | .pas | ***** / 6 |
Dominik Goździuk | Java | Lista dwustronna dwukierunkowa | .java | .java | ***** / 10 |
Marek Rynarzewski | Php | Lista dwukierunkowa z wartownikiem | .php | .php | ***** / 1 |
Poprawiony: 30 sierpnia 2012 20:01
Do tego jeszcze przydałoby się aby typem danych był void* a nie stosunkowo bezużyteczny int
Np Lista autorów + podlista tytułów książek napisanych przez tych autorów.