Liste concatenate - INTRANETdemarco/sd/lezioni/lezione03.pdf · Liste concatenate Collezione...

Liste concatenateListe concatenate

Collezione ordinata di nodi

ciascun nodo contiene due riferimenti:

- un riferimento "element" a un elemento- un riferimento "next" ad un altro nodo

head

Anna

next next next next

element element element element

Carlo Paolo Simona

tail

Strutture Dati

...

0 21 N-1

somiglianze: ordinamento lineare

differenze:la lista concatenata non ha bisogno di una taglia fissata a priori come accade per l'array (pu usare uno spazio propozionale al numero dei suoi elementi)

Lista concatenata

array

Strutture Dati

Liste concatenateListe concatenate

La classe NodoLa classe NodoImplementazione Java Implementazione Java

public class Node {private E element;private Node next;public Node(E e, Node n){

element = e;next = n;

}public Node(){

this(null,null);}public E getElement(){

return element;}public Node getNext(){

return next;}public void setElement(E newElem) {

element = newElem;}public void setNext(Node newNext){

next = newNext;}

}

element

next

Strutture Dati

Liste concatenateListe concatenateImplementazione della pila con liste concatenateImplementazione della pila con liste concatenate

lelemento in cima alla pila memorizzato nel primo nodo della lista

head (cima della pila)

ay x v

Strutture Dati

inserimento di un nuovo elemento e nella pila (push(e))




ay x v

Strutture Dati

- creiamo un nuovo nodo




ay x v


Strutture Dati





ay x v


- definiamo il riferimento all'elemento e

e

Strutture Dati





ay x v



e

- definiamo il riferimento al nodo successivo

Strutture Dati




ay x v



e

- definiamo il riferimento al nodo successivo- aggiorniamo il riferimento al nodo cima della pila

Strutture Dati


package stack;

import linkedList.Node;//linkedList e` il pacchetto dove abbiamo inserito la classe Node

public class NodeStack implements Stack{protected Node top;protected int size;public NodeStack(){

top = null;size = 0;

}public int size() {

return size;}public boolean isEmpty() {

return (size == 0); }...}

Strutture Dati


public class NodeStack implements Stack{...

public E top() throws EmptyStackException {if (isEmpty()) throw new EmptyStackException("Lo stack e` vuoto.");return top.getElement();

}public void push(E element) {

Node v = new Node(element,top);top = v;size++;

}

public E pop() throws EmptyStackException {if (isEmpty()) throw new EmptyStackException("Lo stack e` vuoto.");E temp = top.getElement();top = top.getNext();size--;return temp;

}

...}

Strutture Dati


aye x v

head (front della coda) tail (rear della coda)

il front della coda memorizzato nel primo nodo (head) della lista

il rear della coda memorizzato nellultimo nodo (tail) della lista

Liste concatenateListe concatenateImplementazione della coda con liste concatenateImplementazione della coda con liste concatenate

Strutture Dati

Vantaggi:

- non si deve specificare a priori un limite superiore alla taglia della pila o della coda (una pila o una coda di n elementi richieder sempre uno spazio di dimensione O(n))

- tutte le operazioni richiedono tempo O(1)

Svantaggi:

- l'implementazione leggermente meno semplice di quella con array

- lo spazio di memoria richiesto da ciascun elemento un po' maggiore rispetto alla soluzione con array

Liste concatenateListe concatenateImplementazione della pila e della codaImplementazione della pila e della coda

Strutture Dati

La struttura dati Coda Doppia La struttura dati Coda Doppia (Deque)(Deque)

E` un'estensione della struttura dati Coda

in

out

in

out

- cancellazioni e inserimenti sono possibili da entrambe le estremit (front e rear)

Strutture Dati

Il tipo astratto di dati dequeIl tipo astratto di dati deque

Dati: oggetti arbitrari

Operazioni:- void addFirst(E e): inserisce un nuovo elemento e all'inizio di D

- void addLast(E e): inserisce un nuovo elemento e alla fine di D

- EremoveFirst(): restituisce e rimuove il primo elemento di D

- E removeLast(): restituisce e rimuove l'ultimo elemento di D

- E getFirst(): restituisce il primo elemento di D

- E getLast(): restituisce l'ultimo elemento di D

- Integer size(): restituisce il numero di elementi di D

- Boolean isEmpty(): vero se D vuota, falso altrimenti

Tipo di dati e operazioniTipo di dati e operazioni

Strutture Dati

Si verifica una EmptyDequeExceptionquando si invoca uno dei seguenti metodi su una deque vuota.

- E removeFirst()

- E removeLast()

- E getFirst()

- E getLast()

Le eccezioni Le eccezioni Il tipo astratto di dati dequeIl tipo astratto di dati deque

Strutture Dati

Implementazione dequeImplementazione dequeL'interfaccia L'interfaccia

public interface Deque {

public int size();

public boolean isEmpty();

public E getFirst() throws EmptyDequeException;

public E getLast() throws EmptyDequeException;

public void addFirst (E element);

public void addLast (E element);

public E removeFirst() throws EmptyDequeException;

public E removeLast() throws EmptyDequeException;}

Strutture Dati

Implementazione dequeImplementazione dequeSoluzione con liste concatenateSoluzione con liste concatenate

headtail

Strutture Dati


headtail

come facciamo una removeLast()?

Strutture Dati

headtail


Strutture Dati


headtail


Strutture Dati


headtail


Strutture Dati


headtail


Strutture Dati


headtail

questa soluzione inefficiente perch removeLast() richiederebbe tempo O(n), dove n il numero di elementi nella deque

tempo necessario per aggiornare il riferimento next dell'ultimo nodo e il riferimento al nodo tail

Strutture Dati


header trailer

Ciascun nodo contiene un riferimento (next) al nodo successivo e un riferimento (prev) al nodo precedente;

Per semplificare la programmazione si usano due nodi speciali detti nodi sentinella: nodo header - next contiene un riferimento al primo nodo della deque - prev contiene null nodo trailer - prev contiene un riferimento all'ultimo nodo della deque - next contiene null

nextprev

Strutture Dati


Inserimento in testa di un nuovo elemento

Tizio

CaioSempronio

header trailer

Strutture Dati


Tizio

CaioSempronio


header trailer

Strutture Dati


Tizio

CaioSempronio


header trailer

Strutture Dati


Liste doppiamente concatenateListe doppiamente concatenateLa classe DLNodeLa classe DLNode

public class DLNode {

private E element; private DLNode next, prev;

public DLNode() { this(null, null, null); } public DLNode(E e, DLNode p, DLNode n) { element = e; next = n; prev = p; }

public void setElement(E newElem) { element = newElem; } public void setNext(DLNode newNext) { next = newNext; } public void setPrev(DLNode newPrev) { prev = newPrev; } public E getElement() { return element; } public DLNode getNext() { return next; } public DLNode getPrev() { return prev; }}

element

nextprev

Strutture Dati

La struttura dati array listLa struttura dati array list

E` un contenitore di elementi organizzati secondo unordinamento lineare:

primo elemento, secondo elemento, ...

Strutture Dati

cancellazioni e inserimenti sono possibili in posti arbitrari



Strutture Dati





inserimento di un nuovo oggetto

Strutture Dati





cancellazione di un oggetto

Strutture Dati





cancellazione di un oggetto

Strutture Dati


L'accesso agli elementi avviene per mezzo del loro indice

Dato un array list S di n elementi,possiamo riferirci univocamente a ciascun elemento di S attraverso il suo indice:

l'ndice di un elemento e in S il numero di elementi che precedono e in S

S

elemento di indice 3


L'indice di un elemento e rappresenta la posizione di e all'interno dell' ordinamento lineare della struttura:

l'elemento i-esimo ha indice i - 1

Strutture Dati


S



Naturalmente:

l'indice di un elemento e si pu modificare in seguito a inserimenti e cancellazioni

Prima

Strutture Dati


SInserimento

Strutture Dati


Naturalmente:


S



Dopo

Strutture Dati


Naturalmente:


Il tipo astratto di dati array listIl tipo astratto di dati array listTipo di dati e operazioniTipo di dati e operazioni

Dati: oggetti arbitrari

Operazioni:- get(i): restituisce l'elemento di indice i

- set(i, e): restituisce e rimpiazza l'elemento di indice i con lelemento e

- add(i, e): inserisce un nuovo elemento e di indice i - remove(i): restituisce e rimuove l'elemento di indice i

- size()

- isEmpty()

Strutture Dati

Dato un array list S di n elementi, si verifica una eccezione nei seguenti casi:

get(i) con i < 0 oppure i > n - 1

set(i, e) con i < 0 oppure i > n - 1

remove(i) con i < 0 oppure i > n 1

add(i, e) con i < 0 oppure i > n

Le eccezioni Le eccezioni Il tipo astratto di dati array listIl tipo astratto di dati array list

0 21 i n - 1

... ...S

Strutture Dati

L'interfacciaL'interfacciaImplementazione array listImplementazione array list

public interface IndexList {

public int size();

public boolean isEmpty();

public void add(int i, E e) throws IndexOutOfBoundsException;

public E get(int i) throws IndexOutOfBoundsException;

public E remove(int i) throws IndexOutOfBoundsException;

public E set(int i, E e) throws IndexOutOfBoundsException;

}

Strutture Dati

Una semplice soluzione basata su arrayUna semplice soluzione basata su arrayImplementazione array listImplementazione array list

N-1

L'array list viene implementato con un array A di N elementi e una variabile n < N che indica il numero di elementi nell'array list

A[i] mantiene un riferimento all'elemento di indice i

0 21 i n - 1

... ...

Strutture Dati


N-1



0 21 i n - 1

... ...

Algorithm get(i):if i < 0 or i > n-1 then

throw BoundaryViolationExceptionreturn A[i]

Strutture Dati

N-1



0 21 i n - 1

... ...

Algorithm remove(i):if i < 0 or i > n-1 then

throw BoundaryViolationException e A[i]

for j = i, i+1, ..., n - 2 do A[j] A[j+1] n n - 1return e

e

Strutture Dati


N-1



0 21 i n - 1

... ...

tempo di esecuzione: (n) nel caso pessimo (quando i=0)

Algorithm remove(i):if i < 0 or i > n-1 then

throw BoundaryViolationException e A[i]

for j = i, i+1, ..., n - 2 do A[j] A[j+1] n n - 1return e

Strutture Dati


N-1



0 21 i n - 1

... ...

Algorithm add(i, e):if i < 0 or i > n then

throw BoundaryViolationExceptionfor j = n - 1, n - 2, ..., i do A[j+1] A[j] // fa spazio al nuovo elementoA[i] en n+1

Strutture Dati


N-1



0 21 i n - 1

... ...

Algorithm add(i, e):if i < 0 or i > n then

throw BoundaryViolationExceptionfor j = n - 1, n - 2, ..., i do A[j+1] A[j] // fa spazio al nuovo elementoA[i] en n+1

tempo di esecuzione: (n) nel caso pessimo (quando i=0)

e

Strutture Dati


Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Implementazione coda con array Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47

Liste concatenate - INTRANETdemarco/sd/lezioni/lezione03.pdf · Liste concatenate Collezione...

Documents

Transcript of Liste concatenate - INTRANETdemarco/sd/lezioni/lezione03.pdf · Liste concatenate Collezione...