Implementação de Lista Autorreferenciada em C#

Listas Autorreferenciadas

Exemplo de implementação de uma lista autorreferenciada (lista simplesmente encadeada) em C# utilizando nó sentinela (cabeça):

public class ListaRef {
    private class Celula {
        public Object item;
        public Celula prox;
    }

    private Celula primeiro, ultimo, pos;

    // Operações
    public ListaRef() { // Cria uma Lista vazia
        this.primeiro = new Celula();
        this.pos = this.primeiro;
        this.ultimo = this.primeiro;
        this.primeiro.prox = null;
    }

    public Object pesquisa(Object chave) {
        if (this.vazia() || chave == null)
            return null;

        Celula aux = this.primeiro;
        while (aux.prox != null) {
            if (aux.prox.item.Equals(chave))
                return aux.prox.item;
            aux = aux.prox;
        }
        return null;
    }

    public void insere(Object x) {
        this.ultimo.prox = new Celula();
        this.ultimo = this.ultimo.prox;
        this.ultimo.item = x;
        this.ultimo.prox = null;
    }

    public Object retira(Object chave) {
        if (this.vazia() || (chave == null))
            throw new Exception("Erro: Lista vazia ou chave inválida");

        Celula aux = this.primeiro;
        while (aux.prox != null && !aux.prox.item.Equals(chave))
            aux = aux.prox;

        if (aux.prox == null)
            return null; // não encontrada

        Celula q = aux.prox;
        Object item = q.item;
        aux.prox = q.prox;

        if (aux.prox == null)
            this.ultimo = aux;

        return item;
    }

    public Object retiraPrimeiro() {
        if (this.vazia())
            throw new Exception("Erro: Lista vazia");

        Celula aux = this.primeiro;
        Celula q = aux.prox;
        Object item = q.item;
        aux.prox = q.prox;

        if (aux.prox == null)
            this.ultimo = aux;

        return item;
    }

    public Object Primeiro() {
        this.pos = primeiro;
        return proximo();
    }

    public Object proximo() {
        this.pos = this.pos.prox;
        if (this.pos == null)
            return null;
        else
            return this.pos.item;
    }

    public bool vazia() {
        return (this.primeiro == this.ultimo);
    }

    public void imprime() {
        Celula aux = this.primeiro.prox;
        while (aux != null) {
            Console.Write(aux.item.ToString() + " ");
            aux = aux.prox;
        }
    }
}