Pewnie początkujący programiści po przeczytaniu tytułu tego wpisu zaczęli się zastanawiać o co właściwie chodzi, więc spieszę z wyjaśnieniem. Dane w programach komputerowych, możemy przechowywać w zwykłych zmiennych lub na przykład za pomocą stosu, który w pewnych przypadkach jest bardzo pomocny. Na tym jednak nie kończą się możliwości programowania zorientowanego obiektowo, które daje znacznie więcej pola do popisu programistom. W tym artykule zapoznamy się z listami jako strukturami do przechowywania pewnych informacji.
Lista jako struktura danych ideowo nie różni się właściwie niczym od na przykład listy produktów z którą chodzimy na zakupy. W programowaniu wyróżniamy jednak kilka jej typów. Mamy więc listy jednokierunkowe, listy dwukierunkowe, listy cykliczne, listy z głową itd. Na pierwszy rzut oka, może się wydawać to trochę skomplikowane (co to za głowa?) ale w rzeczywistości implementacja tej struktury danych przynosi naprawdę wiele korzyści, a czasem okazuje się jedyną drogą do rozwiązania danego problemu programistycznego. Wyobraźmy sobie sytuację, że piszemy aplikację obsługującą klientów banku. Każda osoba chce wykonać przelew, a my możemy zrobić tylko jeden na raz. Jak więc zapisać dane o wszystkich osobach czekających w kolejce? Teoretycznie możemy użyć po prostu tablicy ale niestety nie wiemy ile osób będzie chciało przelać swoje oszczędności. Oczywiście możemy założyć, że będzie ich milion, dwa miliony, albo trzydzieści osiem – co jeśli jednak pomyliliśmy się i brakło dla kogoś miejsca? Ten właśnie problem rozwiązuje lista, którą możemy wydłużać i wydłużać dopóki wystarczy nam pamięci na dysku twardym. Ale na to jako programiści nie mamy już niestety wpływu.
Zalety i wady używania list:
| ZALETY | WADY |
|
|
Skoro zapoznaliśmy się już z teorią to pora napisać swoją własną listę. Zacznijmy oczywiście od szkieletu programu:
public class Main {
public static void main(String[] args) {
}
}Powyższego kodu, chyba nie trzeba nikomu tłumaczyć, można go wygenerować w dobrym IDE do Java.
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 Value (referencja do kolejnego elementu) 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:
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;
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
if(f == null) //wartości nie ma na liście
return -1;
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;
if(f == null) //wartości nie ma na liście
return -1;
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;
if(f == null) //wartości nie ma na liście
return -1;
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;
}
}
}Lista wiązana dwukierunkowa
W poprzednim przykładzie napisaliśmy listę wiązaną jednokierunkową, teraz trochę ją przerobimy na listę wiązaną dwukierunkową czyli do każdego elementu dodamy wskaźnik na poprzedni oraz dla lepszej wygody zrobimy pole last, w którym będziemy przechowywać informacje o ostatnim elemencie listy.
Graficzna implementacja listy wiązanej dwukierunkowej:

Dla przypomnienia, to cały czas będziemy pracować na tym kodzie:
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;
if(f == null) //wartości nie ma na liście
return -1;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}No to skoro każdy element listy ma mieć wskaźnik na poprzedni to musimy nieco zmodyfikować naszą klasę Value. Dodajemy więc nowe pole o nazwie prev i inicjalizujemy je w konstruktorze:
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
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;
if(f == null) //wartości nie ma na liście
return -1;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}Oczywiście powyższy kod nam się nie skompiluje ponieważ metody takie jak add() oraz delete() są źle skonstruowane (jest niepoprawna liczba argumentów), musimy więc je przerobić.
Zabierzmy się więc za metodę add():
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
List()
{
first = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, 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;
if(f == null) //wartości nie ma na liście
return -1;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}Jeśli chodzi o przypadek, w którym dodajemy do listy pierwszy element, no to tutaj sprawa jest banalnie prosta, jako argument odpowiadający za referencję do poprzedniego elementu podajemy oczywiście null i na tym kończymy modyfikację tego fragmentu kodu.
Teraz rozważmy drugi przypadek, gdzie dodajemy element do listy w której już jakieś elementy są:
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
List()
{
first = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, null);
first = l;
}
else
{
l = new Value(x, v.next);
if(l.next != null)
v.next.prev = l;
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;
if(f == null) //wartości nie ma na liście
return -1;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}Tutaj musimy sprawdzić czy nie jest to ostatni element i jeżeli nie jest, to do pola prev elementu następnego (v.next.prev) przypisujemy referencję do naszego nowego elementu. W przeciwnym wypadku automatycznie zostanie tam wstawiony null.
No to metodę add() mamy już za sobą więc pora na kolejną czyli delete():
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
List()
{
first = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, null);
first = l;
}
else
{
l = new Value(x, v.next);
if(l.next != null)
v.next.prev = l;
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;
if(first != null) //lista nie jest pusta po usunięciu
first.prev = null;
}
else
{
prev.next = f.next;
if(f.next != null)
f.next.prev = prev;
}
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
if(f == null) //wartości nie ma na liście
return -1;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}Tutaj rozważamy dwa przypadki. Pierwszy to kasowanie pierwszego elementu naszej listy, w tym wypadku sprawa jest prosta: aktualizujemy pole first oraz do pola prev obiektu first przypisujemy null. W kolejnym kroku mamy nieco więcej do napisania. Zaczynamy od tego, że do pola elementu poprzedniego przypisujemy referencję na następny element po tym, który chcemy skasować (czyli jak by go omijamy) oraz zgodnie z tą samą zasadą aktualizujemy pole prev tak aby ominąć skasowany obiekt. Tutaj musimy się jeszcze zabezpieczyć przed próbą wykonania operacji na nieistniejącym punkcie listy.
Na końcu dla naszej lepszej wygody dorobimy jeszcze pole last odpowiedzialne za przechowywanie informacji o ostatnim elemencie listy:
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
Value last;
List()
{
first = null;
last = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, null);
first = l;
last = l;
}
else
{
l = new Value(x, v.next, v);
if(l.next != null)
v.next.prev = l;
else
last = l;
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;
if(first != null) //lista nie jest pusta po usunięciu
first.prev = null;
}
else
{
prev.next = f.next;
if(f.next == null)
last = prev;
else
f.next.prev = prev;
}
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
if(f == null) //wartości nie ma na liście
return -1;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}Poniżej tradycyjnie zamieszczam w pełni działający program:
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
Value last;
List()
{
first = null;
last = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, null);
first = l;
last = l;
}
else
{
l = new Value(x, v.next, v);
if(l.next != null)
v.next.prev = l;
else
last = l;
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;
if(first != null) //lista nie jest pusta po usunięciu
first.prev = null;
}
else
{
prev.next = f.next;
if(f.next == null)
last = prev;
else
f.next.prev = prev;
}
}
int searchValue(int x)
{
Value f = first;
while(f != null && f.value != x)
f = f.next;
if(f == null) //wartości nie ma na liście
return -1;
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;
}
System.out.println();
System.out.println("----------------LISTA ODWRÓCONA-----------------");
f = lista.last;
while(f != null)
{
System.out.print(f.value + " -> "); //wypisujemy listę
f = f.prev;
}
}
}Lista cykliczna dwukierunkowa wiązana
W poprzednim przykładzie napisaliśmy listę dwukierunkową wiązaną, teraz postaramy się ją przerobić na cykliczną listę dwukierunkową wiązaną. Od poprzedniej naszej listy różni się ona tym, że pierwszy element znacznikiem prev wskazuje na ostatni, a ostatni znacznikiem next na pierwszy.
Graficznie prezentuje się to tak:

Dla przypomnienia, to wszystkie operacje będziemy wykonywać na tym kodzie:
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
Value last;
List()
{
first = null;
last = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, null);
first = l;
last = l;
}
else
{
l = new Value(x, v.next, v);
if(l.next != null)
v.next.prev = l;
else
last = l;
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;
first.prev = null;
}
else
{
prev.next = f.next;
if(f.next == null)
last = prev;
else
f.next.prev = prev;
}
}
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) {
}
}Nowa metoda add() będzie więc wyglądać tak:
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
Value last;
List()
{
first = null;
last = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, null);
first = l;
last = l;
first.prev = last; //pierwszy element wskazuje sam na siebie
last.next = first;
}
else
{
l = new Value(x, v.next, v);
v.next.prev = l;
v.next = l;
if(v == last) //dopisaliśmy element na końcu listy
last = 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;
first.prev = null;
}
else
{
prev.next = f.next;
if(f.next == null)
last = prev;
else
f.next.prev = prev;
}
}
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) {
}
}Nowa metoda delete() będzie wyglądać tak:
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
Value last;
List()
{
first = null;
last = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, null);
first = l;
last = l;
first.prev = last; //pierwszy element wskazuje sam na siebie
last.next = first;
}
else
{
l = new Value(x, v.next, v);
v.next.prev = l;
v.next = l;
if(v == last) //dopisaliśmy element na końcu listy
last = 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 == first) //wykonaliśmy pełny cykl - wartości nie ma na liście
{
f = null;
break;
}
}
if (f != null)
if (f.next == f) //usuwamy jedyny element listy
{
first = null;
last = null;
}
else if (prev == null) //usuwamy pierwszy element
{
first = f.next;
first.prev = last;
last.next = first;
}
else
{
prev.next = f.next;
f.next.prev = prev;
if(f == last) //usuwamy ostatni element
last = prev;
}
}
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) {
}
}Oczywiście musimy również przeprowadzić drobną modyfikację metody searchValue() tak aby program nam się nie zapętlił:
class Value
{
int value;
Value next;
Value prev;
Value(int x, Value Next, Value Prev)
{
value = x;
next = Next;
prev = Prev;
}
}
class List
{
Value first;
Value last;
List()
{
first = null;
last = null;
}
Value add(int x, Value v)
{
Value l;
if(first == null)
{
l = new Value(x, null, null);
first = l;
last = l;
first.prev = last; //pierwszy element wskazuje sam na siebie
last.next = first;
}
else
{
l = new Value(x, v.next, v);
v.next.prev = l;
v.next = l;
if(v == last) //dopisaliśmy element na końcu listy
last = 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 == first) //wykonaliśmy pełny cykl - wartości nie ma na liście
{
f = null;
break;
}
}
if (f != null)
if (f.next == f) //usuwamy jedyny element listy
{
first = null;
last = null;
}
else if (prev == null) //usuwamy pierwszy element
{
first = f.next;
first.prev = last;
last.next = first;
}
else
{
prev.next = f.next;
f.next.prev = prev;
if(f == last) //usuwamy ostatni element
last = prev;
}
}
int searchValue(int x)
{
Value f = first;
if(f.value == x)
return f.value;
else
f = f.next;
while(f != first && f.value != x)
f = f.next;
if(f == first) //wykonaliśmy pełny cykl - wartości nie ma na liście
return -1;
return f.value;
}
}
public class Main {
public static void main(String[] args) {
}
}Implementacja wbudowanej listy w Java
Po przebrnięciu przez teorię, możemy wreszcie w pełni świadomie skorzystać z wbudowanych w Java list. Więcej na ten temat przeczytacie w dokumentacji: www.docs.oracle.com/javase/7/docs/api/java/util/List.html, a ja poniżej zamieszczam przykładowy program korzystający z wbudowanej listy w Java:
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList lista = new LinkedList();
lista.addFirst(10);
lista.add(15);
System.out.println(lista.pop()); //ściągamy pierwszy element
System.out.println(lista.pop()); //ściągamy drugi element
}
}


Dzięki za informację, 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 ;)
Napisz poprawnie wyraz „dopóki” w ostatniej linijce drugiego akapitu, bo aż kłuje w oczy.