Informatica I - i metodi pubblici di una catena

Metodi pubblici di una catena

I metodi pubblici di una catena sono:

• addFirst per inserire un oggetto all'inizio della catena
• addLast per inserire un oggetto alla fine della catena
• removeFirst per eliminare il primo oggetto della catena
• removeLast per eliminare l'ultimo oggetto della catena
• getFirst per esaminare il primo oggetto
• getLast per esaminare l'ultimo oggetto
• IsEmpty e size (la catena è un contenitore)

Non vengono mai restituiti o ricevuti riferimenti ai nodi, ma sempre ai dati contenuti nei nodi.

Il metodo addFirst

public class LinkedList ...{ ...

public void addFirst(Object e){ //inserisco dato nello header attuale

head.setElement(e);// creo un nuovo nodo con due riferimenti null

ListNode n = new ListNode();// collego il nuovo nodo allo header attuale

n.setNext(head);// il nuovo nodo diventa lo header della catena

head = n;// tail non viene modificato}

OPPURE... pu

public void addFirst(Object e)} { head.setElement(e);

head = new ListNode(null, head);

L'operazione

è O(1). }IL METODO removeFirstpublic class LinkedList ...{ ...public Object removeFirst(){ Object e = getFirst(); // delega a getFirst il controllo di lista vuotahead = head.getNext(); // aggiorno lo headerhead.setElement(null);return e;}...}L’operazione è O(1).IL METODO addLastpublic class LinkedList ...{ ...public void addLast(Object e){ tail.setNext(new ListNode(e, null));tail = tail.getNext(); //aggiorno il tail}...} L’operazione è O(1).