Listy z dowiązaniami

Porządek na liście liniowy, określony przez wskaźniki związane z każdym elementem listy.

Lista dwukierunkowa - key, next, prev + ew. inne dane

prev[x] = nil x nie ma poprzednika x głowa listy (1 elem.)

next[x] = nil x nie ma następnika x ogon listy (ost.elem.)

head[L] - wskazuje na 1-szy element listy

head[L] = nil lista pusta

Wyszukiwanie na liscie z dowiązaniami

search_l (L, k);

x:=head[L];

while x ≠ nil and key[x] ≠ k do x:=next[x];

Wstawianie do listy z dowiązaniami ( na początek listy)

insert_l (L, x); {wskaźnik do x znany}

next[x] := head [L];

if head[L] ≠ nil then prev[head[L]] := x

head [L] := x; prev[x]:=nil;

{jeżeli dany tylko klucz x , to najpierw search(L, x)}

Usuwanie z listy z dowiązaniami

delete_l (L, x);

if prev[x] ≠ nil then next[prev[x]] := next[x]

else head[L] := next[x];

if next[x] ≠ nil then prev[next[x]] := prev[x]

Wartownicy

Wartownik - sztuczny element (nil [L])pozwalający uprościć warunki brzegowe.

Wartownik jest rekordem o takich samych polach jak pozostałe elementy listy.

Wystąpienia nil zamienione na wskażnik do wartownika nil[L].

next[nil[L]] na głowę listy

prev[nil[L]] na ogon listy

zwykła lista dwukierunkowa lista cykliczna

next[ogon listy] nil[L]

prev[głowa listy] nil[L]

zamiast head[L] - next[nil[L]]

Lista pusta (z wartownikiem)

Procedury dla listy z wartownikiem

Wyszukiwanie na liscie z dowiązaniami (prawie b/z)

search_lw (L, k);

x:=next [nil [L]];

while x ≠ nil [L] and key[x] ≠ k do x:=next[x];

Wstawianie do listy z dowiązaniami ( na początek listy)

insert_lw (L, x); {wskaźnik do x znany}

prev[next [nil [L]]] := x;

next [nil [L]] := x;

prev[x]:=nil [L];

Usuwanie z listy z dowiązaniami

delete_lw (L, x);

next[prev[x]] := next[x]

prev[next[x]] := prev[x]

Reprezentacja tablicowa listy

1

2

LIsty z dowiązaniami s

head [L]

/

9

1

prev

4

16

/

25

w

2

3

a

head [L]

/

a

4

key

next

5

1

7

L

8

7

6

5

4

3

2

Lista po usunięciu elementu z kluczem 4

key

next

/

16

4

/

1

9

head [L]

/

/

9

16

7

1

25

/

head [L]

1

16

9

5

2

nil [L]

/

prev

16

4

1

9

head [L]

nil [L]

x

Lista dwukierunkowa [ / - nil ]

Lista po wstawieniu na początek elementu z kluczem 25

b

-/

x

#

---