Informatica I - ADT la struttura dati catena

Catena (linkedlist)

Catena: è un insieme ordinato di nodi.

Vantaggi di una catena

• Non esiste il problema di "catena piena", quindi non è mai necessario "ridimensionarla".
• Non c'è spazio di memoria sprecato (come negli array "riempiti solo in parte").
• Un nodo occupa però più spazio di una cella di array, almeno il doppio (contiene due riferimenti anziché uno).

public class ListNode {
    // costruttori
    public ListNode() {
        element = null;
        next = null;
    }
    public ListNode(Object e, ListNode n) {
        element = e;
        next = n;
    }

    // metodi pubblici
    public Object getElement() {
        return element;
    }
    public ListNode getNext() {
        return next;
    }
    public void setElement(Object e) {
        element = e;
    }
    public void setNext(ListNode n) {
        next = n;
    }

    // campi di esemplare
    private Object element;
    private ListNode next;
}

Classe LinkedList

public class LinkedList implements Container {
    // campi di esemplare
    private ListNode head, tail;

    // costruttore
    public LinkedList() {
        head = tail = new ListNode();
    }

    // metodi pubblici di Container
    public void size() {
        ListNode temp = head.getNext();
        int size = 0;
        while (temp != null) {
            size++;
            temp = temp.getNext();
        }
        return size;
    }
    
    public boolean isEmpty() {
        return (head == tail);
    }
    
    public Object getFirst() { // operazione O(1)
        if (isEmpty())
            throw new EmptyLinkedListException();
        return head.getNext().getElement();
    }
    
    public Object getLast() { // operazione O(1)
        if (isEmpty())
            throw new EmptyLinkedListException();
        return tail.getElement();
    }

    // vanno scritti i metodi addFirst, addLast, removeFirst, removeLast
}

// Eccezione per lista vuota
class EmptyLinkedListException extends RuntimeException { }

Per accedere in sequenza a tutti i nodi della catena si parte dal riferimento head e si seguono i riferimenti contenuti nel campo next di ciascun nodo. Non è possibile scorrere la lista in senso inverso e la scansione termina quando si trova il nodo con il valore null nel campo next.