Lista powiązana - własna implementacja

Lista powiązana (ang. linked list) to struktura dynamiczna, której każdy element tak zwany węzeł (ang. node) posiada określoną wartość (lub wartości) oraz referencję do kolejnego węzła. Chcemy napisać prostą listę przechowującą wartości typu String (łańcuchy tekstowe). Pierwszą czynnością jest napisanie odpowiedniej klasy, na podstawie której będziemy tworzyć węzły.

/**
 * Węzeł - element listy 
 * @author kodatnik.blogspot.com
 */
class Wezel {
 // łańcuch tekstowy
 private String napis;
 // referencja do kolejnego elementu/węzła
 private Wezel nastepny;
 
 // konstruktor domyślny, "zerujemy" pola
 public Wezel() {
  this(null, null);
 }
 
 // konstruktor dwuparametrowy
 public Wezel(String napis, Wezel nastepny) {
  // przypisujemy polu napis wartość parametru
  this.napis = napis;
  // przypisujemy polu nastepny wartość parametru  
  this.nastepny = nastepny;
 }
 
 // metoda zwraca pole nastepny (dostępowa)
 public Wezel pobierzNastepny() {
  return nastepny;
 }
 
 // metoda ustawia pole nastepny (modyfikująca)
 public void ustawNastepny(Wezel nastepny) {
  this.nastepny = nastepny;
 }
 
 // metoda zwraca pole napis (dostępowa)
 public String pobierzNapis() {
  return napis;
 }

 // metoda ustawia pole napis (modyfikująca)
 public void ustawNapis(String napis) {
  this.napis = napis;
 } 
  
 // zwraca "węzeł" w formie łańucha tekstowego (pole napis)
 public String toString() {
  return napis;
 }
}

Mając gotową klasę dla węzłów, tworzymy klasę odpowiedzialną za prawidłowe funkcjonowanie listy. Nasza lista będzie listą jednostronną (dostęp możliwy tylko z jednego miejsca - początku listy).

/**
 * Lista powiązana 
 * Przykład listy jednostronnej, jednokierunkowej, 
 * przechowującej łańcuchy tekstowe 
 * @author kodatnik.blogspot.com
 */
public class ListaPowiazana {

 // początek listy
 private Wezel poczatek;
 // liczba elementów
 private int rozmiar;
 
 // konstruktor domyślny, "zerujemy" pola
 public ListaPowiazana () {
  poczatek = null;
  rozmiar = 0;
 }
 
 // metoda wstawia na początek listy nowy węzeł z wartością przekazaną jako parametr
 public void wstawNaPoczatek(String napis) {
  // tworzymy nowy węzeł oraz zmieniamy referencję początku listy
  poczatek = new Wezel(napis, poczatek);
  // zwiększamy rozmiar listy (liczbę elementów)
  rozmiar++;
 }
 
 // metoda usuwa i zwraca węzeł znajdujący się na początku listy
 public Wezel usunZPoczatku() {
  // jeśli lista jest pusta zwracamy null
  if(czyPusta()) return null;

  // zapamiętujemy referencję początku listy
  Wezel temp = poczatek;
  // zmieniamy referencję początku listy na następny węzeł
  poczatek = poczatek.pobierzNastepny();
  // zmniejszamy rozmiar listy
  rozmiar--;
  // zwracamy zapamiętany początek listy (usunięty węzeł)
  return temp; 
 }
 
 // metoda sprawdza czy lista jest pusta
 public boolean czyPusta() {
  // zwracamy prawdę lub fałsz
  return (poczatek == null);
 }
 
 // metoda czyści listę "zerując" pola
 public void wyczysc() {
  poczatek = null;
  rozmiar = 0;
 }
 
 // metoda zwraca rozmiar listy (liczbę jej elementów)
 public int pobierzRozmiar() {
  return rozmiar;
 }
 
 // metoda wyświetla zawartość listy
 public void wyswietl() {
  //zapamiętujemy początek listy
  Wezel temp = poczatek;
  // wyświetlamy komunikat
  System.out.print ("Początek -> ");
  // dopóki referencja jest różna od null
  while( temp != null ) {
   // wyświetlamy węzeł (zadziała metoda toString() z klasy Wezel)
   System.out.print (temp + " -> ");
   // przechodzimy do następnego węzła
   temp = temp.pobierzNastepny();
  }
  // wyświetlamy null (dla oznaczenia końca listy)
  System.out.println(temp);
 }
 
 // metoda zwraca listę w formie łańcucha tekstowego
 // inny sposób wyświetlenia listy
 public String toString() {
  // tworzymy zmienną przechowującą łańcuch wyjściowy
  String wyjscie = "";
  //zapamiętujemy początek listy
  Wezel temp = poczatek;
  // dopóki referencja jest różna od null  
  while( temp != null ) {
   // dodajemy zawartość węzła (zadziała metoda toString() z klasy Wezel) do zmiennej
   wyjscie +=  temp + " ";
   // przechodzimy do następnego węzła
   temp = temp.pobierzNastepny();
  }
  // zwracamy łańcuch tekstowy
  return wyjscie;
 }
}

Sprawdźmy działanie listy dodając do niej przykładowe elementy.

public class TestListyPowiazanej {
 public static void main(String args[]) {
    
  // tworzymy listę powiązaną
  ListaPowiazana lista = new ListaPowiazana();
 
  // dodajemy elementy do listy
  lista.wstawNaPoczatek("Kasia");
  lista.wstawNaPoczatek("Marek");  
  lista.wstawNaPoczatek("Dorota");   
  lista.wstawNaPoczatek("Olga");   
  // wyświetlamy listę
  lista.wyswietl();
  // wyświetlamy rozmiar listy
  System.out.println ("Liczba elementów listy: " + lista.pobierzRozmiar());
  // usuwamy jeden element
  System.out.println ("Usuwamy element: " + lista.usunZPoczatku());
  // wyświetlamy listę  
  lista.wyswietl();  
 }
}

Uruchomiona aplikacja:

Początek -> Olga -> Dorota -> Marek -> Kasia -> null
Liczba elementów listy: 4
Usuwamy element: Olga
Początek -> Dorota -> Marek -> Kasia -> null

Powyższą klasę możemy z powodzeniem wykorzystać do implementacji w pełni dynamicznego stosu. Rozwiązane z wykorzystaniem tablic przedstawiłem w poście: Stos - implementacja tablicowa.