Linked Lists

A linked list is a data structure that is similar to an array in that both can be used for data that is a sequential list of elements.
A linked list is a collection of elements, or nodes. Each node contains a pointer to the next node and thus the nodes need not be adjacent in memory.
image.png

Adding a Node

Empty List
  1. ; initiate
  2.         LD        R2, NEW_ITEM
  3.         LD        R1, LISTHEAD
  5. ; insert
  6.         STR        R2, R0, #0
  7.         STR        R1, R2, #0

Not Empty List
  1. ; R2 is the node to insert
  2. ; R1 is the current pointer, R0 is the previous pointer
  4. ; initiate
  5.             LD        R2, NEW_ITEM
  6.             LD        R1, LISTHEAD
  8. ; compare, to sort by NAMEs
  9. LOOP        ...
  10.             BRp        INSERT
  11.             BRn        MOVE_PTR
  12.             BRz        LOOP
  14. ; move pointer
  15. MOVE_PTR    ADD        R0, R1, #0
  16.             LDR        R1, R1, #0
  18. ; insert
  19. INSERT        STR        R2, R0, #0
  20.             STR        R1, R2, #0

image.pngimage.png

Delete a Node