Listas Enlazadas en MIPS: Implementación de Nodos, Inserción e Impresión

Listas enlazadas en ensamblador MIPS

A continuación se muestra la implementación de una lista enlazada de caracteres en ensamblador MIPS. El programa crea un primer nodo, solicita al usuario caracteres hasta que pulse Enter ('\n'), inserta cada carácter en un nuevo nodo al final de la lista y, finalmente, imprime toda la lista.

Parte I: Creación del primer nodo

li $a0, '>'        # Crear el primer nodo, inicializado con el carácter '>'
jal create
move $s0, $v0        # $s0 debe apuntar al primer nodo
move $a0, $s0        # Imprimir el nodo aislado
jal print_node

Parte II: Lectura de caracteres

Se piden caracteres al usuario hasta recibir '\n' (tecla Enter).

loop_input:
li $v0, 12           # Pedir carácter al usuario (read_char)
syscall
li $t0, '\n'
beq $v0, $t0, fin_input

# No es ENTER: insertar el carácter en un nodo nuevo
move $a0, $s0        # Para respetar el convenio, $a0 se inicializa con $s0
move $a1, $v0
jal insert_node

# Tras una llamada a subrutina, los registros temporales se consideran indefinidos (convenio)
b loop_input

fin_input:
move $a0, $s0
jal print
li $v0, 10           # Terminar
syscall

Subrutina create

Reserva memoria para un nodo. Cada nodo ocupa 2 palabras (8 bytes): el carácter en el primer campo y el puntero al siguiente nodo en el segundo.

create:
# No es necesario crear la pila porque no hay llamadas a otras subrutinas
# Para no perder $a0 lo guardamos en un registro temporal ($t0)
move $t0, $a0
li $a0, 8            # Cantidad de bytes a reservar (2 palabras)
li $v0, 9            # Servicio: sbrk
syscall
sw $t0, 0($v0)       # Campo dato
sw $zero, 4($v0)     # Puntero al siguiente nodo = NULL
jr $ra

Subrutina insert_node

Recorre la lista hasta el último nodo y enlaza allí un nuevo nodo que contiene el carácter recibido en $a1.

insert_node:
addi $sp, $sp, -32   # Crear la pila
sw $ra, 20($sp)
sw $fp, 16($sp)
addi $fp, $sp, 28

loop1:
lw $t0, 4($a0)      # Siguiente nodo
beq $t0, $zero, fin_lista
move $a0, $t0
b loop1

fin_lista:
# Para respetar el convenio, guardamos $a0 en la pila, ya que se necesitará después
sw $a0, 0($fp)
move $a0, $a1
jal create
lw $a0, 0($fp)
sw $v0, 4($a0)      # Enlazar el nuevo nodo al final
move $a0, $v0

lw $ra, 20($sp)
lw $fp, 16($sp)
addi $sp, $sp, 32
jr $ra

Subrutinas print_node y print

print_node imprime el carácter de un nodo. print recorre toda la lista e invoca a print_node para cada elemento.

print_node:
lw $a0, 0($a0)
li $v0, 11           # Servicio: print_char
syscall
jr $ra

print:
addi $sp, $sp, -32
sw $ra, 20($sp)
sw $fp, 16($sp)
addi $fp, $sp, 28

loop2:
beq $a0, $zero, fin_print   # Si hemos llegado al final, se termina
sw $a0, 0($fp)
jal print_node
lw $a0, 0($fp)
lw $t0, 4($a0)
move $a0, $t0
b loop2

fin_print:
lw $ra, 20($sp)     # Recuperar la pila
lw $fp, 16($sp)
addi $sp, $sp, 32
jr $ra              # Retornar