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

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

st nst. 25.04.09

Wyszukiwarka

Podobne podstrony:
5 listy wiązane
Wyklad 1 Wiazania
Wyklad 4 Wiazania chemiczne w cialach stalych
Wiązania chemiczne (II)
6 wykad WiĄzania chemiczne[F]
Chemia wyklad I i II (konfiguracja wiÄ…zania Pauling hybrydyzacja wiazania pi i sigma)
Wykład 1, budowa atomu, wiązania chemiczne
Enzymatyczna redukcja związków karbonylowych i zawierających wiązania C=C
listy zadan, rach3
FM listy id 178271 Nieznany
Listy o A. Lisowskim, W, Rozmaitości
Lk Gabinet zabiegowy, Listy-Kontrolne-DOC
LISTY PAWLA-NOWY TESTMENT, Staropolka

więcej podobnych podstron