Abstrakcyjne struktury danych: Lista
Lista wiązana jednokierunkowa
Lista wiązana jednokierunkowa to w zasadzie najprostsza lista jaką można stworzyć. Charakteryzuje się ona między innymi wbudowaną nawigacją pozwalającą na sprawne przesuwanie się element po elemencie do przodu. Jej ogólna struktura w formie graficznej wygląda tak:
Jak widać, każdy element listy zawiera jakąś wartość oraz adres do następnego co umożliwia sprawne przesuwanie się.
Teraz już wiemy co chcemy zaprogramować więc pora zabrać się do stworzenia struktury naszej listy w Java:
class Value {
int value;
Value next;
}
public class Main {
public static void main(String[] args) {
}
}No to tradycyjnie stworzyliśmy sobie nową klasę o nazwie Value, a w niej dwa pola jedno typu int do przechowywania danych, a drugie typu List (czyli naszej jeszcze nie utworzonej listy) do przechowywania informacji o następnym punkcie na liście.
Oczywiście nie możemy zapomnieć o inicjalizacji wszystkich pól:
class Value
{
int value;
Value next;
Value(int x, Value Next)
{
value = x;
next = Next;
}
}
public class Main {
public static void main(String[] args) {
}
}Powyżej stworzyliśmy obiekt odpowiadający pojedynczemu elementowi listy. Teraz musimy stworzyć drugi obiekt o nazwie List, który będzie naszą główną listą:
class Value
{
int value;
Value next;
Value(int x, Value Next)
{
value = x;
next = Next;
}
}
class List
{
}
public class Main {
public static void main(String[] args) {
}
}W klasie List będziemy potrzebowali mieć pole typu Value o nazwie first do szybkiego pobierania informacji o pierwszym elemencie listy – to właśnie od niego będziemy zawsze zaczynać przegląd wszystkich danych. Zmienna ta musi zostać oczywiście zainicjalizowana w konstruktorze.
class Value
{
int value;
Value next;
Value(int x, Value Next)
{
value = x;
next = Next;
}
}
class List
{
Value first;
List()
{
first = null;
}
}
public class Main {
public static void main(String[] args) {
}
}Mamy już ogólną strukturę naszej listy więc teraz zabierzmy się za napisanie pozostałych metod. Do przygotowania mamy jeszcze funkcje takie jak:
add()– umożliwia dodanie nowego elementu do listy,searchValue()– wyszukuje element na liście z wartością podaną jako argument,delete()– usuwa wskazany jako argument element z listy.
Metoda add() będzie wyglądała tak:
class Value
{
int value;
Value next;
Value(int x, Value Next)
{
value = x;
next = Next;
}
}
class List
{
Value first;
List()
{
first = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null);
first = l;
}
else
{
l = new Value(x, v.next);
v.next = l;
}
return l;
}
}
public class Main {
public static void main(String[] args) {
}
}Tworzymy tutaj nowy obiekt klasy Value (czyli nową pozycję na liście) i następnie sprawdzamy czy mamy już pierwszy element jeżeli nie to właśnie obiekt, który stworzyliśmy musi się nim stać, jeżeli tak, to do pola next poprzedniego obiektu (poprzedniej pozycji na liście, podanej jako argument) przypisujemy referencję (wskaźnik) do naszego nowo utworzonego elementu na liście. Na samym końcu zwracamy nasz obiekt tak, żeby potem w mainie wiedzieć jaki jest ostatni element na liście (nie musimy tego robić, kiedy w klasie List zrobimy dodatkowe pole przechowujące tą informację).
Kolejna funkcja jaką mamy do napisania czyli searchValue() wygląda tak:
lass Value
{
int value;
Value next;
Value(int x, Value Next)
{
value = x;
next = Next;
}
}
class List
{
Value first;
List()
{
first = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null);
first = l;
}
else
{
l = new Value(x, v.next);
v.next = l;
}
return l;
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}Tutaj sprawa jest dość prosta. Począwszy od pierwszego elementu (pole first) przechodzimy po całej liście do momentu znalezienia szukanej wartości lub przejścia przez całą listę. Na końcu oczywiście zwracamy znalezioną wartość.
No i na koniec pozostała nam metoda delete():
class Value
{
int value;
Value next;
Value(int x, Value Next)
{
value = x;
next = Next;
}
}
class List
{
Value first;
List()
{
first = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null);
first = l;
}
else
{
l = new Value(x, v.next);
v.next = l;
}
return l;
}
void delete(int x)
{
Value f = first;
Value prev = null;
while (f != null && f.value != x) {
prev = f ;
f = f.next;
}
if (f != null)
if (prev == null)
first = f.next;
else
prev.next = f.next;
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}Tutaj na początku tworzymy sobie dwa pola, pierwsze przechowuje informację o początkowym elemencie listy, a drugie o poprzedzającym elemencie (na początku jest puste, bo first nie ma swojego poprzednika). Dalej szukamy naszego elementu na liście i przy okazji zapisujemy informację o elemencie poprzedzającym. Po przebrnięciu przez ten fragment musimy rozważyć dwa przypadki bowiem inaczej będzie wyglądała procedura skasowania pierwszego elementu, a inaczej kolejnych. Musimy się tutaj również zabezpieczyć przed próbą jakiś zmian na liście w wypadku kiedy nie znajdziemy elementu, którego chcemy usunąć. Jeżeli kasujemy pierwszy element to po prostu do pola first przypisujemy first.next czyli kolejny punkt na liście. Natomiast, jeżeli kasujemy jakiś inny element to po prostu do wskaźnika next elementu poprzedniego przypisujemy referencję (czyli wskazujemy na nowy obiekt) do obiektu następnego po tym, który chcemy skasować.
Nasza lista jest już gotowa, pora więc napisać maina i sprawdzić czy wszystko działa. Poniżej publikuję kod przykładowego programu:
class Value
{
int value;
Value next;
Value(int x, Value Next)
{
value = x;
next = Next;
}
}
class List
{
Value first;
List()
{
first = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null);
first = l;
}
else
{
l = new Value(x, v.next);
v.next = l;
}
return l;
}
void delete(int x)
{
Value f = first;
Value prev = null;
while (f != null && f.value != x) {
prev = f ;
f = f.next;
}
if (f != null)
if (prev == null)
first = f.next;
else
prev.next = f.next;
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
List lista = new List(); //tworzymy listę
Value value = null;
for(int i = 0;i<10;i++)
{
value = lista.add(i,value); //dopisujemy do listy elementy od 0 do 9
}
Value x = lista.add(11,value); //dopisujemy element 11 na koniec listy
lista.add(13,value); //dopisujemy element 13 po elemencie 9
System.out.println(lista.searchValue(5)); //sprawdzamy czy element 5 jest na liście
lista.delete(6); //usuwamy element 6
Value f = lista.first;
while(f != null)
{
System.out.print(f.value + " -> "); //wypisujemy listę
f = f.next;
}
}
}
W pierwszych kilku fragmentach kodu w klasie Value masz next typu List zamiast Value, poza tym takie coś jak:
List()
{
first = null;
}
jest nadmiarowe w Javie gdyż domyślnie zmienne składowe klasy będące obiektami inicjalizowane są nullami.
Faktycznie wkradł mi się drobny błąd, dzięki za info ;) Natomiast co do inicjalizacji to faktycznie w Java pola tego typu będą domyślnie wypełniane nullami więc nie ma potrzeby ich inicjalizacji w konstruktorze jednak w innych technologiach oraz przy innym typie zmiennych (np. int gdzie do zmiennej domyślnie zapisywane jest 0) będzie inaczej, a dobrą praktyką jest zawsze inicjalizowanie zmiennych ;)
Napisz poprawnie wyraz „dopóki” w ostatniej linijce drugiego akapitu, bo aż kłuje w oczy.
Dzięki za informację, poprawione ;)
Witam ;)
W 3 kodzie na stronie jest „mały błąd” – w konstruktorze jako jeden z argumentów bierzemy Next typu List, a przypisujemy go do next typu Value.
Świetna strona, pozdrawiam :)
Dzięki za czujność ;) Poprawione…
Witam,
czy mógłby mi ktoś wytłumaczyć dlaczego element 11 znajduje się na końcu listy?
A dokładniej, o co chodzi?
Nie bardzo rozumiem dlaczego element 11 znajduje się na końcu listy skoro metoda z 13 wywoływana jest później.
O który przykład chodzi?
2 strona (lista jednokierunkowa wiązana), na samym dole w metodzie main (wiersz 80-81)
W momencie dodawania elementu 11 do listy znajduje się on na jej końcu ;)