Advanced

Data Structures

Implementing linked lists and stacks in LC-3.

Thinking in Data Structures

Even in assembly, we can implement classic data structures. The key is using memory addresses as pointers.

Stack (Using Memory)

We already saw the hardware stack with R6. Let's formalize it:

.ORIG x3000
LD R6, STKPTR    ; R6 = stack pointer = xFE00

; Push 5
AND R0, R0, #0
ADD R0, R0, #5
ADD R6, R6, #-1
STR R0, R6, #0

; Push 10
AND R0, R0, #0
ADD R0, R0, #10
ADD R6, R6, #-1
STR R0, R6, #0

; Pop into R1 (should be 10 — LIFO)
LDR R1, R6, #0
ADD R6, R6, #1

; Pop into R2 (should be 5)
LDR R2, R6, #0
ADD R6, R6, #1

HALT
STKPTR .FILL xFE00
.END

Linked List

A linked list node has two words: a value and a next pointer. A null pointer (0) marks the end.

.ORIG x3000
; Walk a linked list and sum all values
LEA R1, HEAD     ; R1 = pointer to first node
AND R0, R0, #0   ; R0 = sum

WALK
ADD R1, R1, #0   ; Check if null
BRz DONE
LDR R2, R1, #0   ; R2 = node.value
ADD R0, R0, R2   ; sum += value
LDR R1, R1, #1   ; R1 = node.next
BR WALK

DONE HALT

; Linked list: 3 -> 7 -> 5 -> null
HEAD .FILL #3        ; Node 1 value   (x3009)
     .FILL x300B     ; Node 1 next -> Node 2
     .FILL #7        ; Node 2 value   (x300B)
     .FILL x300D     ; Node 2 next -> Node 3
     .FILL #5        ; Node 3 value   (x300D)
     .FILL #0        ; Node 3 next -> null
.END

Lookup Table

A lookup table maps an index to a value. This is useful for digit-to-ASCII conversion, jump tables, and more:

.ORIG x3000
; Print the digit stored in R0 (0-9)
; Using a lookup table
AND R0, R0, #0
ADD R0, R0, #7    ; R0 = 7

LEA R1, TABLE     ; R1 = base of table
ADD R1, R1, R0    ; R1 = &TABLE[R0]
LDR R0, R1, #0   ; R0 = TABLE[R0] = ASCII '7'
OUT               ; Print it
HALT

TABLE .FILL #48   ; '0'
      .FILL #49   ; '1'
      .FILL #50   ; '2'
      .FILL #51   ; '3'
      .FILL #52   ; '4'
      .FILL #53   ; '5'
      .FILL #54   ; '6'
      .FILL #55   ; '7'
      .FILL #56   ; '8'
      .FILL #57   ; '9'
.END
Quiz

In a linked list implementation, how do you detect the end of the list?

← String ProcessingBit Manipulation →