5_listy_wi¹zane

Algorytmy i struktury danych - wykład 5. strona: 1

Wykład 5. Listy wiązane

Lista wiązana (ang. linked list) stanowi uniwersalny mechanizm, który moŜe

mieć zastosowanie w wielu algorytmach. W szczególności moŜe zastąpić tablicę jako

podstawę implementacji innych struktur danych, takich jak stosy i kolejki.

W ogólności moŜemy uŜyć listy wiązanej w bardzo wielu sytuacjach, w których

uŜylibyśmy tablicy, o ile nie jest wymagany częsty i szybki dostęp do elementów przy

pomocy indeksów.

W liście wiązanej dostęp bezpośredni jest jedynie do elementu pierwszego, do

pozostałych elementów mamy dostęp sekwencyjny, tzn. aby pobrać informację o

danym elemencie naleŜy go odszukać na liście podąŜając łańcuchem kolejnych

połączeń.

Implementacja listy wiązanej

Lista wiązana uwalnia nas od wady struktur statycznych – tablic: kopiowania

fragmentów tablicy, w przypadku operacji wstawiania lub usuwania elementu ze

środka listy.

Lista wiązana jest reprezentowana jako ciąg obiektów typu

Link

, kaŜdy obiekt

zawiera:

•

element listy - pole o nazwie

info

typu np. int, long lub inny

•

referencję do następnej komórki w liście – pole o nazwie

next

•

adres w ostatnim obiekcie ma wartość do nikąd: null

•

adres do komórki zawierającej pierwszy element listy przechowywany w zmiennej

First typu referencyjnego do

Link

First

null

Przykładowa lista wiązana.

Warunek:

First != null oznacza Ŝe lista jest niepusta (zawiera co najmniej jedną

komórkę).

Algorytmy i struktury danych - wykład 5. strona: 2

Definicja klasy Link.

class Link{

public int info; // dane

public Link next; // referencja do następnego elementu

…

}

PoniŜej przedstawione zostaną podstawowe algorytmy działające na liście wiązanej.

Algorytm przeglądu listy wiązanej:

p = First ;

// ustawiamy się na początku listy

while (p != null) {

p.visit() ; // jakaś operacja na elemencie listy

p = p.next;

// przejście do następnego

}

// teraz p jest równe null (wartość

next

z ostatniej komórki)

Algorytm wyszukiwania w liście - operacja LOCATE:

Link Locate (int searchKey){

// szukany element o wartości v

p = First ; // ustawiamy się na początku listy

while ( p != null && p.info != searchKey)

p = p.next;

// teraz wystarcza sprawdzić czy p niepusty

if ( p != null )

return p; // zachodzi p.info = searchKey

else

return null; // wyszliśmy poza listę, nie znalazłszy searchKey

}

Algorytmy i struktury danych - wykład 5. strona: 3

Algorytm wstawiania do listy wiązanej na dowolną pozycję

Dana jest referencja

, wskazujący na pewną komórkę w liście wiązanej, oraz

wartość

dana

Zadanie:

•

utworzyć komórkę zawierającą wartość

dana

w polu

info

•

wstawić tę komórkę do listy tak aby

dana

był następnym elementem w liście po

elemencie zawartym w komórce wskazywanej przez

Tworzenie komórki.

•

W języku Java: wywołanie operatora

new

przydzielającej pamięć operacyjną

dla nowo kreowanego obiektu (elementu listy):

q = new Link(dana);

•

A teraz wstawienie komórki do listy:

q.next = p. next; // [1]

p. next = q ; // [2]

First

null

[1]

[2]

Ilustracja wstawiania elementu na zadaną referencję

W przypadku wstawiania nowego elementu na początek listy naleŜy wykonać

następujące operacje:

q = new Link(dana);

q.next = First;

First = q ;

Algorytmy i struktury danych - wykład 5. strona: 4

Algorytm usuwania zadanego elementu listy

Dana jest referencja

do pewnej komórki w liście. Aby usunąć komórkę następną

(zakładamy, Ŝe istnieje) po tej wskazywanej przez

, naleŜy:

q = p.next; // zapamiętać referencję do elementu następnego

p.next = q. next; // jako następną po

przyjąć następną po

// (komórka juŜ jest odłączona od listy)

First

null

MoŜna było, nie uŜywając zmiennej roboczej

, wykonać tylko:

p. next = p.next.next;

W przypadku usuwania pierwszego elementu listy naleŜy wykonać następującą

instrukcję:

First = First.next;

W Javie pamięć dla usuwanych elementów nie musi być zwalniana przez

uŜytkownika, poniewaŜ stosuje się proces odzyskiwania pamięci (ang. garbage

collector), czyli pamięć dla usuniętego elementu będzie odzyskana w przyszłości.

Problem: usunąć element listy o podanej wartości

Rozwiązanie: odszukać komórkę zawierającą ten element i odłączyć ją od listy

(załóŜmy, Ŝe istnieje dokładnie jedna taka komórka).

Trudność:

aby odłączyć wskazaną komórkę trzeba mieć adres komórki

POPRZEDZAJĄCEJ.

Trzeba uwzględnić szczególny przypadek: usuwanie pierwszej komórki w

liście.

Algorytmy i struktury danych - wykład 5. strona: 5

Delete (int v ) {

p = First; // aktualna pozycja w trakcie przeglądu

prev = null;

// adres komórki poprzedzającej

while (p != null) && (p.info != v) {

prev = p ;

p = p.next;

}

if (p != null)

// znaleziono - usuń

if (prev = null)

// usuwamy pierwszy z listy

First = p.next;

else

prev. next = p. next;

} //koniec Delete

Dodatkowe techniki usprawniające dla list wiązanych

Lista z nagłówkiem

nagłówek to dodatkowa komórka (head) na początku listy, jej pole

info

jest

puste, a pole

next

wskazuje na realny pierwszy element listy.

Referencja First wskazuje na nagłówek.

Warunek pustości listy:

First.next = null

First

null

head

Zaleta:

uproszczone algorytmy wstawiania i usuwania – zawsze istnieje niepusty

poprzednik. Np. operacja LOCATE ustawiająca aktualny referencję na obiekcie

bezpośrednio poprzedzającym obiekt z szukanym elementem x.

Algorytmy i struktury danych - wykład 5. strona: 6

Link Locate (int v) {

// First jest referencją do nagłówka

p = First; // aktualna pozycja w trakcie przeglądu

while (p.next != null) {

if (p.next.info == v) return p;

else p = p.next

return null // not found

} // koniec Locate

First

null

Head

Lista po wykonaniu Locate(50)

Delete (int v ) {

p = Locate(v);

// pozycja szukanego elementu w trakcie przeglądu

if (p.next != null)

p.next = p.next.next;

} // koniec Delete

•

Lista podwójnie wiązana (dwukierunkowa)

KaŜdy element listy zawiera nie jeden a dwie referencje:

do komórki następnej

next

oraz

do poprzedniej

prev

Początek i koniec listy wskazuje odpowiednio First i Last.

First

null

Last

Lista podwójnie wiązana

Algorytmy i struktury danych - wykład 5. strona: 7

Zaleta:

podczas usuwania komórki z listy wystarcza referencja tylko do niej. Ma to

szczególnie duŜe znaczenie gdy lista jest fragmentem większej struktury, w której do

komórek listy moŜna się dostać inaczej niŜ przeglądając listę od początku.

PoniŜej przedstawiono algorytm usuwania elementu z listy podwójnie wiązanej

First

null

Last

[2]

[1]

Delete(int v ) {

p = Locate(v); // pozycja szukanego elementu w trakcie przeglądu

if (p != null) {

p.prev.next = p.next; // [1]

p.next.prev = p.prev; // [2]

}

} //koniec Delete

•

Lista zamknięta (cykliczna)

W ostatniej komórce referencja

next

jest adresem pierwszej komórki listy

(nagłówka, jeśli wersja z nagłówkiem).

First

Przydatne w sytuacjach gdy lista przeglądana jest w całości, ale niekoniecznie od

początku. Zamiast testu

p != null

naleŜy zastosować test

p != s

, gdzie

jest

referencją komórki, od której zaczęliśmy przegląd listy

Algorytmy i struktury danych - wykład 5. strona: 8

Przykład: Algorytm usuwania elementu o podanej wartości z listy wiązanej (pola:

info, next

) z nagłówkiem, cyklicznej:

First

Head

Ilustracja operacji Delete(50)

Delete (int v ) {

p = Head;

while (p.next != Head && p.next.info != v )

p = p.next;

if ( p.next != Head ) // znaleźliśmy komórkę zaw. v

p.next = p.next.next; // usunięcie z listy wiązanej

} // koniec Delete

Efektywność list wiązanych

Wstawianie i usuwanie elementów z początku listy wiązanej wymagają zmiany

jednej lub dwóch referencji, więc działają w czasie stałym O(1).

Wyszukiwanie, usuwanie lub wstawianie po elemencie o określonym kluczu

wymaga sprawdzenia średnio połowy elementów w liście. Potrzebne jest zatem O(N)

porównań, analogicznie jak w przypadku tablicy, ale lista wiązana jest zwykle

bardziej efektywna, gdyŜ nie wymaga przesuwania elementów podczas wstawiania

czy usuwania.

Zwiększenie efektywności moŜe być zauwaŜalne szczególnie w przypadku, gdy

kopiowanie jest duŜo bardziej kosztowne czasowo niŜ porównanie, np. gdy

elementami listy są struktury.

Dodatkową zaletą list wiązanych w stosunku do tablic jest elastyczniejsze

wykorzystanie pamięci. Lista wiązana zawiera dokładnie tyle pamięci, ile potrzeba

(pewien narzut pamięci powoduje co prawda konieczność pamiętania w kaŜdym

Algorytmy i struktury danych - wykład 5. strona: 9

elemencie referencji do następnego elementu, ale jest on rekompensowany przez

inne korzyści) i moŜe być łatwo rozszerzalna.

Rozmiar tablicy jest ustalany w momencie tworzenia, powoduje to zwykle

nieefektywne wykorzystanie pamięci, gdy tablicy jest zbyt duŜa lub przepełnienie,

gdy jest zbyt mała.

Implementacja stosu przy uŜyciu listy wiązanej.

Lista wiązana jest bardzo efektywną realizacją stosu, przy czym elementem

wierzchołkowym jest pierwszy element listy. Operacje wstawiania

push(x)

usuwania

pop()

polegają na wstawianiu lub usuwaniu pierwszego elementu listy

wiązanej.

top

null

Przykład. Plik linkStack.java

// linkStack.java
// demonstruje stos zaimplementowany przy u

yciu listy powi

zanej

class Link{
   public long info;             // dane
   public Link next;             // nast

pny element listy

// -------------------------------------------------------------
   public Link(long dd)           // konstruktor
      { info = dd; }
// -------------------------------------------------------------
   public void displayLink()      // wypisanie klucza elementu
      { System.out.print(info + "->"); }
   }  // koniec klasy Link

class LinkStack
   {
   private Link top;          // referencja do pierwszego elementu
// -------------------------------------------------------------
   public LinkStack()              // konstruktor
      { top = null; }           // na razie brak elementów
// -------------------------------------------------------------
   public boolean isEmpty()// zwraca true, je

eli lista jest pusta

{ return (top == null); }
// -------------------------------------------------------------

Algorytmy i struktury danych - wykład 5. strona: 10

public void push(long v) // wstawienie na pocz

tek listy

      {                           // tworzymy nowy element
      Link newLink = new Link(v);
      newLink.next = top;       // newLink -> poprzedni pierwszy
      top = newLink;            // top -> newLink
      }
// -------------------------------------------------------------
   public long pop()            // usuni

cie pierwszego elementu

{ // (zakładamy,

e lista nie jest pusta)

Link temp = top; // zapisujemy referencj

do usuwanego

// elementu
top = top.next; // usuni

cie: top->poprzedni drugi

return temp.info; // zwracamy usuni

ty element

      }
// -------------------------------------------------------------
   public void displayStack()
      {
      System.out.print("Top->");
      Link tmp = top;         // rozpoczynamy na pocz

tku listy

      while(tmp != null)      // dopóki nie koniec...
         {
         tmp.displayLink();   // ...wypisujemy dane...
         tmp = tmp.next;      // ...i przechodzimy do nast

pnego

         }
      System.out.println("null");
      }
}
//----koniec klasy LinkStack -----------------------------------

class LinkStackApp
   {
   public static void main(String[] args)
      {
      LinkStack theStack = new LinkStack(); // tworzymy stos

      System.out.println("Wstawianie");
      theStack.push(20);                    // odkładamy elementy
      theStack.displayStack();
      theStack.push(40);
      theStack.displayStack();       // wypisujemy zawarto

ść

stosu

      theStack.push(60);                    // odkładamy elementy
      theStack.displayStack();
      theStack.push(80);
      theStack.displayStack();       // wypisujemy zawarto

ść

stosu

      System.out.println("--------------------------");
      System.out.println("Usuwanie");
      theStack.pop();                       // zdejmujemy elementy
      theStack.displayStack();
      theStack.pop();
      theStack.displayStack();       // wypisujemy zawarto

ść

stosu

} // koniec main()
}
// koniec klasy LinkStackApp

Algorytmy i struktury danych - wykład 5. strona: 11

Implementacja kolejki przy uŜyciu listy wiązanej z nagłówkiem

Do implementacji kolejki lepiej jest uŜyć listy wiązanej z nagłówkiem. Dzięki liście

z nagłówkiem otrzymamy uproszczone algorytmy wstawiania i usuwania (nie trzeba

rozwaŜać przypadków szczególnych, np. wstawiania elementu do kolejki pustej, czy

usuwania ostatniego elementu z kolejki).

front

null

head

rear

Kolejka w liście wiązanej

Po utworzeniu kolejki pustej, metoda wstawiania na koniec kolejki będzie

modyfikować jedynie referencję rear:

enQueue(long dd) // wstawienie na koniec listy

{

Link newLink = new Link(v); // tworzymy nowy element

rear.next = newLink; // poprzednio ostatni -> newLink

rear = newLink; // rear -> newLink

}

front

null

head

rear

Ilustracja wstawienia elementu 40 do kolejki

Podobnie podczas operacji usuwania z początku kolejki, faktycznie usuwany będzie

nagłówek listy a nie pierwszy elementu. Po usunięciu pierwszy element kolejki będzie

nowym nagłówkiem w liście.

Algorytmy i struktury danych - wykład 5. strona: 12

Oznacza to, Ŝe metoda usuwania elementu z kolejki modyfikuje jedynie referencję

front.

long deQueue() { // usunięcie pierwszego elementu

long tmp = front.next.info; // zapamiętujemy usuwany element

front = front.next; // front -> poprzednio pierwszy element

return tmp;

}

front

null

head

rear

Ilustracja usuwania elementu z kolejki

Przykład. Plik linkQueue.java

// linkQueue.java
// demonstruje kolejk

zaimplementowan

przy u

yciu

// listy wi

zanej z nagłówkiem

class Link{
public long info; // dane
public Link next; // nast

pny element listy

// -------------------------------------------------------------
   public Link(long v)           // konstruktor
      { info = v; }
// -------------------------------------------------------------
   public void displayLink()      // wypisanie klucza elementu
      { System.out.print(info + "->"); }
   }
// ---- koniec klasy Link --------------------------------------

class LinkQueue
   {
   private Link front;          // referencja do pierwszego elementu
   private Link rear;           // referencja do ostatniego elementu
// -------------------------------------------------------------
   public LinkQueue(long v)         // konstruktor
      {
      front = new Link(v);       // lista zawiera jedynie nagłówek
      rear = front;
      }
// -------------------------------------------------------------
   public boolean isEmpty()// zwraca true, je

eli kolejka jest pusta

{ return front==rear; }
// -------------------------------------------------------------

Algorytmy i struktury danych - wykład 5. strona: 13

   public void enQueue(long v)   // wstawienie na koniec listy
      {
      Link newLink = new Link(v);   // tworzymy nowy element

      rear.next = newLink;         // poprzednio ostatni -> newLink
      rear = newLink;              // rear -> newLink
      }
// -------------------------------------------------------------
   public long deQueue()         // usuni

cie pierwszego elementu

{ // (zakładamy,

e lista nie jest pusta)

      long tmp = front.next.info;

      front = front.next;    // front -> poprzednio pierwszy element
      return tmp;
      }
// -------------------------------------------------------------
   public void displayQueue()
      {
      Link tmp = front;          // zaczynamy od pocz

tku

      while(tmp.next != null)    // dopóki nie koniec kolejki...
         {
         tmp.next.displayLink(); // ...wypisujemy zawarto

ść

// lementu...
tmp = tmp.next; // ...i przechodzimy do nast

pnego

         }
      System.out.println("null");
      }
}
// ----- koniec klasy LinkQueue------------------------------------

class LinkQueueApp
   {
   public static void main(String[] args)
      {
      LinkQueue theQueue = new LinkQueue(-1);// utworzenie kolejki
                                             // z nagłówkiem

      System.out.println("Wstawianie");
      theQueue.enQueue(20);                 // wstawiamy elementy
      theQueue.displayQueue();
      theQueue.enQueue(40);
      theQueue.displayQueue();
      theQueue.enQueue(60);
      theQueue.displayQueue();       // wypisujemy zawarto

ść

kolejki

      theQueue.enQueue(80);          // wstawiamy elementy
      theQueue.displayQueue();

      System.out.println("--------------------------------");
      System.out.println("Usuwanie");
      theQueue.deQueue();                   // usuwamy elementy
      theQueue.displayQueue();
      theQueue.deQueue();
      theQueue.displayQueue();       // wypisujemy zawarto

ść

kolejki

} // koniec main()
}
// koniec klasy LinkQueueApp