Liste

Le liste sono composte da Nodi.

Nodo

Il nodo è composto da due campi:

• val: contiene il dato effettivo
• next: contiene un riferimento al prossimo elemento in lista (nil se è l’ultimo)

Primitive

1. new_list(): crea una nuova lista - $\Theta (1)$
2. is_empty_list(L): ritorna true se la lista è vuota - $\Theta (1)$
3. insert_head(L, e): inserisce un elemento e in testa - $\Theta (1)$
4. insert_next(p, e): inserisce l’elemento e dopo l’elemento p - $\Theta (1)$
5. search(L, i): cerca l’elemento in posizione i - $\Theta (i)$
6. insert_pos(L, e, i): inserisce l’elemento e in posizione i - $\Theta (i)$
7. delete(L, p): elimina l’elemento p dalla lista - $\Theta (n)$

search(L, i):
	p := L
	j := 0
	while j < i AND p != nil do
		j := j+1
		p := p.next
	return p

insert_pod(L, e, i):
	q := search(L, i - 1)
	if q != nil then
		insert_next(q, e)

delete(L, p):
	if p == L then
		L := L.next
	else
		tmp := L
		while tmp.next != p AND tmp != nil do
			tmp := tmp.next
		if tmp != nil then
			tmp.next := p.next

asd_16