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...
    public void addFirst(Object e) {
        head.setElement(e);
        head = new ListNode(null, head);
        L'operazione è O(1).
    }
}

Il metodo removeFirst

public class LinkedList {
    ...
    public Object removeFirst() {
        Object e = getFirst(); // Delega a getFirst il controllo di lista vuota
        head = head.getNext(); // Aggiorno lo header
        head.setElement(null);
        return e;
    }
    ...
    L'operazione è O(1).
}

Il metodo addLast

public class LinkedList {
    ...
    public void addLast(Object e) {
        tail.setNext(new ListNode(e, null));
        tail = tail.getNext(); // Aggiorno il tail
    }
    ...
    L'operazione è O(1).
}