# Author: Pablo Pastor Martín

#Estructura representando el nodo de una lista simplemente enlazada
Node = Struct.new(:value, :next)

#Clase que representa una lista simplemente enlazada
class Lista
    attr_reader :head
    
    def initialize
        @head = Node.new
    end
    
    #Inserta un valor al comienzo de la lista
    def push(x)
        if @head[:value] == nil
            @head[:value]=x
        else
            aux= @head.clone
            @head = Node.new(x,aux)
        end
        @head[:value]
    end
    
    #Devuelve el numero de elementos de la lista
    def size
        count = 0
        if @head[:value] != nil then
            count=1
        end
        aux= @head
        until aux[:next] == nil do
            count+=1
            aux=aux[:next]
        end
        count
    end
    
    #Extrae por el comienzo de la lista
    def pop
        if @head!= nil then
            aux = @head[:value]
            @head = @head[:next]
        else
            aux=nil
        end
        if @head ==nil then 
            @head = Node.new
        end
        aux
    end
    
end

#Representa un nodo de una lista doblemente enlazada
Node2 = Struct.new(:value, :next, :prev)

#Representa una lista doblemente enlazada
class ListaDoblementeEnlazada
    include Enumerable
    
    attr_reader :head, :tail
    
    def initialize
        @head = Node2.new
        @tail = @head
    end
    
    #Inserta al comienzo
    def push(x)
        if @head[:value] == nil
            @head[:value]=x
            @tail=@head
        else
            aux= @head
            @head = Node2.new(x,aux)
            @head[:next][:prev]=@head
        end
        @head[:value]
    end
    
    #Inserta al final de la lista
    def insert_back(x)
        if @head[:value] == nil
            @head[:value]=x
        else 
            old_tail = @tail
            @tail = Node2.new(x, nil, old_tail)
            old_tail[:next] = @tail
        end 
        
        @tail[:value]
    end
    
    #Extrae el ultimo elemento de la lista
    def get_back
        aux = nil
        if @tail[:value]==nil
            aux=nil
        else
            aux = @tail[:value]
            @tail = @tail[:prev]
            @tail[:next]=nil
        end
        if @tail==nil
            @tail = Node2.new
            @head = @tail
        end
        aux
    end
    
    #Devuelve el tamaño de la lista
    def size
        count = 0
        if @head[:value] != nil then
            count=1
        end
        aux= @head
        until aux[:next] == nil do
            count+=1
            aux=aux[:next]
        end
        count
    end
    
    #Extrae el primer elemento
    def pop
        if @head!= nil then
            aux = @head[:value]
            @head = @head[:next]
        else
            aux=nil
        end
        if @head ==nil then 
            @head = Node2.new
        end
        aux
    end
    
    #Hace un yield con cada elemento de la lista
    def each
        aux= @head
        until aux[:next] == nil do
            yield aux[:value]
            aux=aux[:next]
        end
        if aux[:value] != nil then
            yield aux[:value]
        end
    end
end