W05 struktury wiazane

IIUJ Metody programowania Strona: 1

Wykład 5.

Struktury wiązane

Struktura wiązana (ang. linked structure) 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 listy, 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 tablic statycznych, 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 prosta wiązana.

IIUJ Metody programowania Strona: 2

Warunek:

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

komórkę).

Definicja klasy Link.

class Link{

public int info; // dane, w tym przypadku - typu int

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:

Operacja Locate(searchKey) zwraca referencję do pierwszego wystąpienia

szukanego elementu w liście wiązanej, przy czym, jeśli element nie występuje na

liście – zwraca null.

Link Locate (int searchKey) { // szukany element o wartości searchKey

p = First ;

// ustawiamy się na początku listy

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

p = p.next;

return p; // p == null lub p.info == searchKey

}

IIUJ Metody programowania Strona: 3

Algorytm wstawiania do listy wiązanej

Dana jest referencja - p, wskazująca na pewną komórkę w liście wiązanej, oraz

wartość - dana.

Przy zadanej referencji p, aby efektywnie (bez przeglądania listy) wstawić element

do listy należy:

• utworzyć komórkę zawierającą wartość dana w polu info

• wstawić tę komórkę do listy tak, aby element zawierający wartość dana był

następnym elementem w liście po elemencie listy wskazywanym 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

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 ; }

IIUJ Metody programowania Strona: 4

Algorytm usuwania elementu listy

Dana jest referencja - p do pewnej komórki w liście.

Podobnie jak poprzednio, gdy zadana jest referencja p, efektywna realizacja

usuwania elementu z listy wiązanej polega na usunięciu elementu następnego

(zakładamy, że istnieje) po elemencie wskazanym przez p.

Operacja ta wykonywana jest w dwóch krokach:

1. q = p.next; // w q jest referencją do elementu następnego po p

// to ten element usuwamy

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

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

użytkownika, ponieważ zrobi to interpreter kodu maszyny wirtualnej w czasie

procesu odzyskiwania pamięci (ang. garbage collector).

Zatem usuwanie elementu następnego po elemencie wskazanym przez p

można zapisać prościej:

p. next = p.next.next;

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

instrukcję:

First = First.next;

IIUJ Metody programowania Strona: 5

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

Rozwiązanie: odszukać komórkę zawierającą podaną wartość 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.

void 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; // prev.next == p

}

// p.info == v lub p ==null

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

1. Lista dwustronna

Lista dwustronna jest bardzo podobna do zwykłej listy wiązanej, ale

przechowuje dodatkową informację: referencję last do ostatniego elementu.

Posiadanie tej referencji pozwala bezpośrednio wstawić element na koniec

listy bez przechodzenia całej listy. Przy pomocy list dwustronnych będzie

IIUJ Metody programowania Strona: 6

można implementować kolejkę zwykłą.

2. Lista z głową (z nagłówkiem)

Głowa (head) - to dodatkowa komórka na początku listy, jej pole info jest

nieokreślone, a pole next wskazuje na realny pierwszy element listy.

Referencja First wskazuje na głowę.

Warunek pustości listy:

First.next == null

First

. . .

null

Lista wiązana z głową

Lista wiązana z głową jest efektywną implementacją struktury ADT Lista,

postaci: a1, a2, ..., an. w której jako pozycję elementu a i , przyjmujemy referencję

do elementu a i-1 ( bezpośrednio poprzedzającego a i). Pozycją elementu a 1 jest referencja do głowy listy.

Zaleta:

Uproszczone algorytmy wstawiania i usuwania – zawsze istnieje niepusty

poprzednik. Np. operacja Locate(searchKey) - zwraca referencję do obiektu

bezpośrednio poprzedzającego obiekt o wartości searchKey.

Uwaga:

W algorytmach badających, czy nie osiągnięto koniec listy, np., instrukcję

while(p !=End() ) ... wygodniej zastąpić instrukcją while(p.next != null) ....

Link Locate (int v) { // First jest referencją do nagłówka

p = First;

// aktualna pozycja w trakcie przeglądu

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

p = p.next ;

return p ;

} // koniec Locate

IIUJ Metody programowania Strona: 7

First

null

Lista po wykonaniu Locate(50)

Przyjmując tak wprowadzone pojęcie pozycji elementu w ADT Lista w implementacji listy

wiązanej z głową, operacje usuwania elementu z zadanej pozycji - Delete(p) oraz wstawiania elementu na zadaną pozycję Insert(x, p) mają następującą postać:

void Delete ( Link p ) { // zakładamy, że referencja p jest pozycją na liście

if (p.next != null) // nie usuwa elementu za ostatnim

p.next = p.next.next;

} // koniec Delete

First

null

Po wykonaniu operacji Delete(p)

void Insert(int x, Link p) { // wstawienie na po elemencie p listy

Link q = new Link(x); // tworzy nowy element

// tworzymy nowe połączenia

q.next = p.next; // q .next -> następny po p element [1]

p.next = q; // p.next -> q [2]

}

IIUJ Metody programowania Strona: 8

First

null

[2]

[1]

Po wykonaniu operacji Insert(40, p)

Przykład.

Klasa linkHeadList ilustruje działanie listy wiązanej z nagłówkiem

class Link

{

public int info; // dana typu np. int

public Link next; // referencja do następnego połączenia

// oba pola publiczne

// -------------------------------------------------------------

public Link(int id) // konstruktor

{

info = id; // inicjalizacja danych

// (pole next ma automatycznie wartosc null)

}

// -------------------------------------------------------------

public void displayLink() // wypisuje wartosc pól obiektu Link

{

System.out.print(info + "->" );

}

} // koniec klasy Link

//==============================================================

class LinkHeadList

{

public Link first; // referencja do pierwszego elementu listy

// -------------------------------------------------------------

public LinkHeadList() // konstruktor listy z nagłówkiem

{

first = new Link(-1); // tworzenie nagłówka listy

first.next = null; // lista nie ma jeszcze elementów

}

// -------------------------------------------------------------

public boolean isEmpty() // zwraca true, jeżeli lista jest pusta

{

return (first.next==null);

}

// -------------------------------------------------------------

public void insert(int x, Link p)// wstawienie na po elemencie p listy

{

Link q = new Link(x); // tworzy nowy element

IIUJ Metody programowania Strona: 9

// tworzymy nowe połączenie

q.next = p.next; // q --> następny po p element

p.next = q; // p.next --> q

}

// -------------------------------------------------------------

public void delete(Link p) // usuwanie elementu po p

{ // zakładamy, że p jest referencja

// do listy

if (p.next != null)

p.next = p.nex.next; // usuwamy go z listy: p.next--

}

// -------------------------------------------------------------

public Link locate(int search) // wyszukuje na liscie zadany element

{

Link curr = first; // zaczynamy na początku listy

while(curr.next != null && curr.next.info != search)

// dopóki nie koniec listy...

{ // i nie znaleziono

curr = curr.next; // ...przechodzimy do następnego elementu

}

return curr; // jesli znaleziono zwraca referencje do elementu

// poprzedziającego

// jesli nie znaleziono zwraca referencje do ostatniego

// elementu

}

// -------------------------------------------------------------

public void displayList()

{

System.out.print("Lista: ");

Link curr = first; // zaczynamy na poczatku listy

while(curr != null) // dopóki nie koniec listy...

{

curr.displayLink(); // ...wypisujemy dane i...

curr = curr.next; // ...przechodzimy do następnego elementu.

}

System.out.println("null");

}

// -------------------------------------------------------------

} // koniec klasy LinkHeadList

3. Lista podwójnie wiązana (dwukierunkowa)

Lista dwukierunkowa daje możliwość poruszania się równie łatwo naprzód jak i

wstecz. Lista dwukierunkowa nie musi mieć referencji do ostatniego elementu ale

dostęp do końca listy jest przydatny, więc w naszym przykładzie lista dwukierunkowa

jest jednocześnie listą dwustronną.

IIUJ Metody programowania Strona: 10

Zatem zakładamy, że lista zawiera dwie referencje: First i Last, które

wskazują odpowiednio początek i koniec listy.

First

null

Last

Lista podwójnie wiązana

Każdy element listy, oprócz pola info, zawiera dwie referencje:

do komórki następnej - next oraz

do poprzedniej - prev.

Tak więc klasa Link, używana przez listę dwukierunkową ma postać:

class Link{

public long info;

public Link next;

public Link prev;

….

}

Na liście dwukierunkowej wykonywane są następujące operacje:

1. makeNull() – tworzy listę pustą

2. displayForward() – wypisuje elementy listy od początku do końca

3. displayBackward() – wypisuje elementy od końca do początku

4. insertFirst(x) – wstawia element na początek listy

5. insertLast(x) – wstawia element na koniec listy

6. insertAfter(x, key) – wstawia element po określonym kluczu

7. deleteFirst() – usuwa pierwszy element na liście

8. deleteLast() – usuwa ostatni element na liście

9. deleteKey(key) –usuwa element o podanym kluczu

10. locate (key) – wyszukuje pozycje zadanego elementu.

IIUJ Metody programowania Strona: 11

Zalety:

Podczas usuwania komórki z listy dwukierunkowej wystarcza referencja

tylko do komórki usuwanej. 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.

Wady:

Podczas wstawiania elementu do listy wykonywane są cztery operacje

na referencjach. Musimy zmieniać dwie referencje do następnego elementu i

dwie do następnego. Oprócz tego, każdy element listy dwukierunkowej

zajmuje więcej pamięci niż w liście prostej (o rozmiar dodatkowej referencji).

Poniżej przedstawiono algorytm usuwania elementu o zadanej wartości z listy

podwójnie wiązanej:

[1]

First

null

Last

[2]

void deleteKey( 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

Operacja insertAfter( x, klucz) wstawia nowy element x jako następnik

elementu o podanym kluczu.

IIUJ Metody programowania Strona: 12

W tej metodzie najpierw odnajdujemy element o podanym kluczu - niech p jest

referencją do znalezionego elementu. Następnie tworzymy i wstawiamy nowy

element po elemencie wskazanym przez p (musimy wykonać cztery operacje na

referencjach).

Operację wstawiania insertAfter(x, klucz) ilustruje poniższy rysunek.

Last

First

[4]

null

[2]

[1]

[3]

newLink

void InsertAfter(int x, int key) {

p = Locate(key);

// pozycja szukanego elementu w trakcie przeglądu

newLink = new Link(x); // tworzy nowy element

if( p == last ) { // wstawiania na końcu, za ostatnim

newLink.next = null;

last = newLink;

} else {

newLink.next = p.next; [1]

p.next.prev = newLink; [2]

}

newLink.prev = p; [3]

p.next = newLink; [4]

}

Operacja insertFirst(int v), realizuje wstawianie na początek listy i jeżeli lista

nie jest pusta zmienia pole prev w dotychczasowym pierwszym elemencie, tak aby

wskazywało na nowy element, a pole next nowego elementu przypisuje referencję do

dotychczas pierwszego elementu.

Następnie referencję do nowego elementu kopiuje do pola first.

IIUJ Metody programowania Strona: 13

Jeżeli lista jest pusta, zamiast pola first.prev modyfikujemy pole last.

Operację wstawiania insertFirst( int v) ilustruje poniższy rysunek:

First

null

[1]

Last

[2]

[3]

newLink

null

Oto przykład kodu:

void InsertFirst( int v) {

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

if ( isEmpty () ) Last = newLink;

else

First.prev = newLink; [1]

newLink.next = First; [2]

First = newLink; [3]

}

Operacja wstawiania na koniec jest symetryczna i pozostawiam ją oraz pozostałe

operacje na liście dwukierunkowej, jako ćwiczenie.

3. Lista prosta zamknięta (cykliczna)

W ostatniej komórce referencja next jest adresem pierwszej komórki listy (lub

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

IIUJ Metody programowania Strona: 14

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

Przykład:

Algorytm usuwania elementu o podanej wartości z listy wiązanej cyklicznej z

nagłówkiem (pola: info, next):

First

Ilustracja operacji delete(50)

void delete (int v ) {

p = First;

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

p = p.next;

if ( p.next != First ) // znaleźliśmy komórkę zawierająca v

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

} // koniec delete

IIUJ Metody programowania Strona: 15

Porównanie efektywności list wiązanych i tablicowych

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.

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

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 bez nagłówka jest bardzo efektywną realizacją stosu. Zmienna

top wskazuje wierzchołek stosu, który jest na początku listy, zatem - operacje

wstawiania push(x) i usuwania pop() polegają na wstawianiu lub usuwaniu

pierwszego elementu listy wiązanej.

top

null

wierzchoek

stosu

IIUJ Metody programowania Strona: 16

Poniższej zdefiniowano klasę LinkStack:

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); }

// -------------------------------------------------------------

public void push(long v) // wstawienie na początek listy

{ // tworzymy nowy element

Link newLink = new Link(v);

newLink.next = top; // newLink -> poprzednio 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-> poprzednio 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 -----------------------------------

IIUJ Metody programowania Strona: 17

Implementacja kolejki prostej przy użyciu listy wiązanej dwustronnej

Do implementacji kolejki wygodniej jest użyć listy wiązanej dwustronnej 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).

Zmienna front wskazuje głowę listy a zmienna rear – ostatni element w kolejce.

front

null

rear

Kolejka prosta jako lista dwustronna

Warunek pustości kolejki:

front == rear; front.next == null

;

Po utworzeniu kolejki pustej, metoda enQueue(long x) - wstawia nowy element na

koniec kolejki, przy czym będzie modyfikowana jedynie referencja - rear:

void enQueue(long x) // wstawienie na koniec listy

{

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

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

rear = newLink; // rear -> newLink

}

IIUJ Metody programowania Strona: 18

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 element. Po usunięciu - pierwszy element kolejki

będzie nowym nagłówkiem w liście.

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

Napisanie pełnej implementacji prostej kolejki wiązanej pozostawiam jako ćwiczenie.