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 p, 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 p.

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

[2]

[1]

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 p do pewnej komórki w liście. Aby usunąć komórkę następną (zakładamy, że istnieje) po tej wskazywanej przez p, należy:

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

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

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

First

null

Można było, nie używając zmiennej roboczej q, 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 v.

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ść:

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

POPRZEDZAJĄCEJ.

2. 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

Head

First

null

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:

1. do komórki następnej next oraz

2. do poprzedniej prev.

3. 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

[1]

Last

First

null

[2]

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 s 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) i 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).

head

front

null

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

}

head

front

rear

null

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;

}

head

front

null

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

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

st nst. 25.04.09