Struktury danych: Jednokierunkowa lista wiązana

Jedną z najprostszych, dynamicznych struktur danych wykorzystywanych w programowaniu są listy . Podobnie jak tablice pozwalają przechowywać różnego rodzaju obiekty, jednak to co je wyróżnia to ich zmienny rozmiar. Na lekcji poświęconej domyślnie zaimplementowanym listom w Javie dowiedzieliśmy się, że wyróżniamy dwa rodzaje listy:

  • Listy wiązane
  • Listy tablicowe

Jednak to nie koniec podziału, ponieważ listy wiązane można podzielić wg innych kryteriów. Mogą one być:

  • jednokierunkowe
  • dwukierunkowe

a także:

  • cykliczne
  • acykliczne

Kurs Java

W tej części kursu skupimy się przede wszystkim na acyklicznej, jednokierunkowej liście wiązanej, ale pokażemy również w jak prosty sposób można ją przekształcić w inne dopisując często kilka linijek kodu.

Omawianą strukturę najłatwiej sobie wyobrazić przedstawiając ją na obrazku:

linkedlist

Jak widać każdy element takiej listy musi posiadać jakieś powiązanie do elementu kolejnego, ale przede wszystkim przechowywać informację o przechowywanym obiekcie. Ostatni element acyklicznej jednokierunkowej listy wskazuje na wartość null, która zwana jest głową, dzięki czemu przy jej przechodzeniu wiemy kiedy doszliśmy do końca. Elementy poprzedzające głowę to tzw. ogon. Zwróćmy też uwagę, że strzałki są skierowane tylko w jedną stronę, aby lista była dwukierunkowa każdy element musiałby przechowywać dodatkową referencję do obiektu poprzedniego. Czasami jest to przydatne, a czasami nie, powinniśmy się kierować w tym przypadku złożonością obliczeniową konkretnego przypadku.

W przypadku listy cyklicznej element ostatni wskazywałby nie na wartość null, a na jej pierwszy element. Obrazkowo dwukierunkowa lista cykliczna wyglądałaby więc następująco:

linkedlist cykliczna

Przeglądając taką listę możemy poruszać się w obie strony i nie występuje tutaj zakończenie listy w postaci wartości null.

Przydatne przy implementacji tego typu struktury jest zastosowanie elementu zwanego wartownikiem. Jest on niedostępny dla użytkownika, jednak w dużym stopniu upraszcza implementację metod. Pusta lista z wartownikiem posiada wtedy 1 element, który wskazuje na wartość null.

Podstawowe metody jakie powinna mieć zaimplementowana lista to:

  • add() - dodaje element do listy
  • delete() - usuwa element przechowujący obiekt podany jako parametr
  • get() - zwraca wartość obiektu z elementu listy o wskazanym indeksie
  • set() - ustawia obiekt w elemencie o podanej pozycji
  • size() - zwraca rozmiar listy
  • isEmpty() - zwraca true, lub false, gdy lista jest, lub nie jest pusta - najlepiej wykorzystać metodę size()
  • clear() - czyści listę. W przypadku listy z wartownikiem wystarczy ustawić jego następnik na wartość null.

Dodatkowo można zaimplementować często wykorzystywane getFirst(), getLast(), removeFirst() itp, ale powyższe są podstawowe.

Cechy listy wiązanej.

Ponieważ w liście tego typu wyszukiwanie elementu polega na sekwencyjnym przechodzeniu kolejnych pozycji, to średnia złożoność obliczeniowa operacji wyszukiwania jest liniowa O(n). Za to usuwanie oraz wstawianie ma złożoność stałą O(1), ponieważ operacje te polegają jedynie na przesunięciu odpowiednich referencji. Struktura ta sprawuje się więc bardzo dobrze w wypadku, gdy mamy posortowaną listę i często następują w niej operacje wstawiania i usuwania, szczególnie gdzieś w środku.

Implementacja - jednokierunkowa lista wiązana z wartownikiem

//Jednokierunkowa lista wiązana z wartownikiem
public class LinkedList{
	private Node head = new Node(null); //wartownik
	private int size; //rozmiar listy
	/**
	 * Konstruktor domyślny, tworzy pustą listę
	 */
	public LinkedList(){
		clear();
	}
	/**
	 * Metoda "czyszcząca" listę, w rzeczywistości ustawia pierwszy element listy, czyli pole next wartownika na null
	 */
	public void clear(){
		head.setNext(null);
		size=0;
	}
	/**
	 * Metoda dodająca nowy element do listy
	 */
	public void add(Object value){
		if (head.getNext()==null) head.setNext(new Node(value)); //jeśli lista jest pusta ustawiamy następnik wartownika
		Node last = head.getNext();
		while(last.getNext() != null) //szukamy ostatniego elementu
			last=last.getNext();
		++size;
		last.setNext(new Node(value)); //i ustawiamy jego następnik na nowy węzeł z podaną wartością value
	}
	/**
	 * Metoda usuwająca obiekt podany jako parametr
	 * @return true, gdy usunięto element, false w innym wypadku
	 */
	public boolean delete(Object o){
		if(head.getNext() == null) return false;
		if(head.getNext().getValue().equals(o)){
			head.setNext(head.getNext().getNext());
			size--;
			return true;
		}

		Node delete = head.getNext();
		while(delete != null && delete.getNext() != null){
			if(delete.getNext().getValue().equals(o)){
				delete.setNext(delete.getNext().getNext());
                                size--;
				return true;
			}
			delete = delete.getNext();
		}
		return false;
	}
	/**
	 * Metoda zwracająca obiekt o podanym indeksie na liście
	 * @param index - indeks elementu w liście, którego wartości oczekujemy
	 * @return - oczekiwany obiekt, lub null, gdy nie istnieje
	 */
	public Object get(int index) throws IndexOutOfBoundsException{
		if(index<0 || index>size) throw new IndexOutOfBoundsException();
		Node find = head.getNext();
		for(int i=0; i <= index; i++)
			find = find.getNext();
		return find.getValue();
	}
	public Object set(int index, Object value) throws IndexOutOfBoundsException{
		if(index<0 || index>size) throw new IndexOutOfBoundsException();
		Node find = head.getNext();
		for(int i=0; i <= index; i++)
			find = find.getNext();
		find.setValue(value);
		return value;
	}
	/**
	 * Metoda zwracająca aktualny rozmiar listy
	 * @return rozmiar listy
	 */
	public int size(){
		return size;
	}
	/**
	 * Metoda, która sprawdza, czy lista jest pusta
	 * @return true, gdy rozmiar listy wynosi 0, w innym wypadku false
	 */
	public boolean isEmpty(){
		return size == 0;
	}

	/**
	 * Klasa wewnętrzna, która definiuje elementy przechowywane na liście
	 */
	private static final class Node{
		private Object value; //aktualny element
		private Node next; //referencja na obiekt kolejny
		/**
		 * Konstruktor ustawiający element na obiekt podany jako argument, wstawianie na początek listy
		 * @param val obiekt, który chcemy przechowywać
		 */
		public Node(Object val){
			this(val, null);
		}
		/**
		 * Konstruktor, który pozwala wstawić element na określone miejsce
		 * @param val obiekt, który chcemy umieścić na liście
		 * @param n obiekt kolejny
		 */
		public Node(Object val, Node n){
			value = val;
			next = n;
		}
		/**
		 * @return aktualny obiekt
		 */
		public Object getValue(){
			return value;
		}
		/**
		 * @return kolejny element
		 */
		public Node getNext(){
			return next;
		}
		/**
		 * @param n kolejny element
		 */
		public void setNext(Node n){
			next = n;
		}

		public void setValue(Object o){
			value = o;
		}
	}
}

Uwaga. Powyższy kod był pisany na szybko i możliwe, że posiada jakieś błędy. Będzie także uzupełniony o więcej metod i komentarzy.

Dyskusja i komentarze

Masz pytania do tego wpisu? Może chcesz się podzielić spostrzeżeniami? Zapraszamy dyskusji na naszej grupie na Facebooku.

Poniżej znajdziesz archiwalne wpisy z czasów, gdy strona była jeszcze hobbystycznym blogiem.

psimek

Przy metodzie delete zapomniałeś o zmniejszaniu pola size.

tomek

w metodzie delete, w pętli while warunek "delete != null" jest niepotrzebny, ponieważ zawsze jest prawdziwy.

Slawek

Nie mam możliwości sprawdzenia tego w tej chwili, ale na pierwszy rzut oka w przypadku listy pustej jednak by się wysypało.

karl

dlaczego po kompilacji nie moge tego pliku uruchomić???

karl

proszę o szybką odpowiedź

Slawek

To jest struktura danych, a nie program. Dzięki temu możesz przechowywać inne obiekty, więc musisz dopisać sobie klasę testową.

maciekb

"clear() – czyści listę. W przypadku listy z wartownikiem wystarczy ustawić jego następnik na wartość null." Czy to nie jest wyciek pamięci? Chyba że w javie w takiej sytuacji zaalokowana wcześniej pamięć automatycznie jest zwalniana.

Slawek

właśnie od tego jest garbage collector. Jeżeli jakieś obiekty są poza zasięgiem to są przy najbliższej okazji zwalniane. Do wycieku pamięci można łatwiej doprowadzić w liście tablicowej - tam przez pomyłkę możemy usuwać elementy poprzez zmniejszanie rozmiaru listy (jakiejś zmiennej size), ale nie zerując obiektów w niej przechowywanych (poza zasięgiem listy, ale wciąż trzymanych w wewnętrznej tablicy). mniej więcej <code> class ArrayList { int[] tab = new int[100]; int size = 10; ... } </code> przy czym nie mamy dostępu do elementów tablicy znajdujących się na indeksach >=10, pomimo iż wciąż są tam stare, tylko pozornie usunięte obiekty.

maciekb

no faktycznie, potem doczytałem dopiero o GC. Jak się przechodzi z C++ na Jave to ok, ale jak ktoś się najpierw uczyl pisać w Javie i zaczyna się uczyć C++ to się można zdziwić że trzeba pamiętać o zwalnianiu pamięci ;)

Assa

czy aby nie lepiej użyć ArrayList'y, ew. stosu? Na pewno będzie bezpieczniej, a artykułów o LinkedList'ach jest pełno...

Slawek

arraylist, linkedlist, a w szczególności stos, mają zupełnie inne zastosowania, każda ma swoje plusy i minusy w specyficznych sytuacjach.

Sebastian

Rozumiem, ze zapis typu: Obiekt.metodaObiektu1().metoda2(); oznacza wywołanie metody metoda2() obiektu, który jest zwracany przez metodę metodaObiektu1(). Rozumiem tez, ze pole value obiektu Node jest typu Object ponieważ jest to klasa nadrzędna dla wszystkich pozostałych i przez to możemy w tym polu przechowywać obiekt dowolnej klasy(bo wszystkie dziedziczą z klasy Object) i w ten sposób nasza lista staje się uniwersalna, tak? Mam jednak z tym mały problem. No wiec jeśli przy pomocy metody setValue() zapisze w naszej liście obiekt klasy MojaKlasa to używając metody getValue() dostane z powrotem obiekt klasy Object i mogę korzystać tylko z metod tej klasy. Co trzeba zrobić, żeby móc skorzystać z metod klasy MojaKlasa. Udało mi się "odzyskać" obiekt klasy MojaKlasa i jego metody poprzez jawne rzutowanie tego co otrzymałem z metody getValue(), ale nie wydaje się to eleganckim rozwiązaniem. Istnieje może jakiś inny sposób na poradzenie sobie z tym problemem?

Slawek

Tak jest ładne rozwiązanie tego problemu - typy generyczne, polecam ten link: http://docs.oracle.com/javase/tutorial/java/generics/gentypes.html oraz tutaj wytłumaczone wszystkie haczyki z tym związane: http://www.angelikalanger.com/GenericsFAQ/FAQSections/ParameterizedTypes.html

matizBrave

Nie jestem jakimś specem, też się dopiero uczę, ale wydaje mi się, że wystarczy zamienić wszystkie elementy typu Obiect na typ MojaKlasa w implementacji listy. Jeśli się mylę to przepraszam i proszę o poprawkę.

matizBrave

Byłem w trakcie pisania, nim dodałeś odpowiedź. Proszę zatem o usunięcie wpisu, jeśli masz taką możliwość. Jeśli nie - trudno, zostanie offtop :)

Sebastian

Ok. Dzięki za szybką odpowiedz ;)

Cit

O co chodzi w plikach META-INF?

noname

public boolean delete(Object o){ if(head.getNext() == null) return false; if(head.getNext().getValue().equals(o)){ head.setNext(head.getNext().getNext()); return true; } czy tutaj przed return true; nie powinno być size-- ?

Bartek

Proszę mi to:<code>private Node head = new Node(null);</code> wytłumaczyć. Tworzysz głowę - head typu klasy Node, a co ma być w tej klasie?

Daniel

Wydaje mi się, że nie zauważyłeś klasy wewnętrznej Node dla klasy LinkedList

Daniel

W metodzie add() wkradł się istotny błąd. W momencie kiedy lista jest pusta i chcemy dodać jeden obiekt value to tak na prawdę dodawany jest on dwa razy (jak element pierwszy i jego następnik). Najprościej chyba będzie poprawić to dodając frazę else do pierwszego if i w niej umieścić resztę metody. Jedynie ++size należy zostawić na zewnątrz instrukcji if else.

Sławek Ludwiczak

Dzięki, faktycznie brakuje tam else.