Implementing a Linked List in Assembly
A linked list is about the simplest data structure that involves dynamic allocation and pointer manipulation. In C, you reach for structs and malloc. Here we'll rebuild it in raw x86-64 assembly, hand-rolling every pointer and every byte. The result: a clear-eyed look at what your C linked list actually compiles to.
The C Version for Reference
Here's the C linked list we're going to replicate in assembly:
#include <stdio.h>#include <stdlib.h>
struct Node { int data; // offset 0, 4 bytes // 4 bytes padding struct Node *next; // offset 8, 8 bytes};// Total: 16 bytes per node
struct Node *head = NULL;
void push_front(int value) { struct Node *new_node = malloc(sizeof(struct Node)); new_node->data = value; new_node->next = head; head = new_node;}
void print_list() { struct Node *curr = head; while (curr != NULL) { printf("%d -> ", curr->data); curr = curr->next; } printf("NULL\n");}
void free_list() { struct Node *curr = head; while (curr != NULL) { struct Node *next = curr->next; free(curr); curr = next; } head = NULL;}Node Layout in Memory
Each node is 16 bytes:
Offset 0: [data (4 bytes)] [padding (4 bytes)]Offset 8: [next pointer (8 bytes)]The padding exists because next has to be 8-byte aligned. The compiler quietly drops 4 bytes of dead space between data and next.
In assembly we'll use these constants:
NODE_SIZE equ 16 ; sizeof(struct Node)DATA_OFFSET equ 0 ; offsetof(struct Node, data)NEXT_OFFSET equ 8 ; offsetof(struct Node, next)Memory Allocation Without malloc
No libc means no malloc, so we need our own allocator. Cheapest approach: ask the kernel for pages via mmap.
section .data heap_ptr: dq 0 ; Current position in our heap heap_end: dq 0 ; End of allocated heap
section .text
; alloc: allocate n bytes from our simple heap; Input: rdi = number of bytes; Output: rax = pointer to allocated memoryalloc: push rbx mov rbx, rdi ; Save requested size
; Check if we have enough space mov rax, [rel heap_ptr] test rax, rax jz .need_more_memory ; First call - no heap yet
add rax, rbx cmp rax, [rel heap_end] ja .need_more_memory ; Not enough space (unsigned: addresses)
; Bump allocator: return current pointer, advance it mov rax, [rel heap_ptr] add QWORD [rel heap_ptr], rbx pop rbx ret
.need_more_memory: ; mmap syscall to get a new page mov rax, 9 ; syscall: mmap xor rdi, rdi ; addr: NULL (let kernel choose) mov rsi, 4096 ; length: one page mov rdx, 3 ; prot: PROT_READ | PROT_WRITE mov r10, 0x22 ; flags: MAP_PRIVATE | MAP_ANONYMOUS mov r8, -1 ; fd: -1 (no file) xor r9, r9 ; offset: 0 syscall ; Returns pointer in rax
mov [rel heap_ptr], rax lea rcx, [rax+4096] mov [rel heap_end], rcx
; Now allocate from the fresh page add QWORD [rel heap_ptr], rbx pop rbx retThis is a "bump allocator" — about as basic as allocators get. Hand out memory sequentially from a page, never free anything. The bounds check uses ja rather than jg because addresses are unsigned: a signed comparison would go wrong for any pointer with the top bit set. Real allocators (glibc's ptmalloc, jemalloc) are orders of magnitude more involved, with free lists, coalescing, and thread-local caches.
push_front in Assembly
section .data head: dq 0 ; struct Node *head = NULL
section .text
; push_front: add a new node at the front of the list; Input: edi = value to insertpush_front: push rbx push r12 mov r12d, edi ; Save value
; Allocate a new node mov rdi, NODE_SIZE ; 16 bytes call alloc ; rax = new node pointer mov rbx, rax ; rbx = new_node
; new_node->data = value mov DWORD [rbx+DATA_OFFSET], r12d
; new_node->next = head mov rax, [rel head] mov QWORD [rbx+NEXT_OFFSET], rax
; head = new_node mov [rel head], rbx
pop r12 pop rbx retCompare this directly to the C version. Hover a line on either side to see its partner. new_node->next = head costs two instructions because x86 has no memory-to-memory mov, so head takes a detour through rax.
push_front: C vs hand-written assembly
x86-64Hover over code lines or mapping badges to see correspondences
Almost a line-for-line mapping. Every C operation has a tidy assembly counterpart. Struct field access (->data, ->next) is nothing but a constant offset added to the pointer.
Traversal and Printing
; print_list: traverse the list and print each node's dataprint_list: push rbx mov rbx, [rel head] ; curr = head
.loop: test rbx, rbx ; curr == NULL? jz .print_null ; If yes, print "NULL\n" and return
; Print curr->data mov edi, DWORD [rbx+DATA_OFFSET] call print_int_no_newline ; Print the integer
; Print " -> " mov rax, 1 ; syscall: write mov rdi, 1 ; fd: stdout lea rsi, [rel arrow_str] mov rdx, 4 ; " -> " is 4 bytes syscall
; curr = curr->next mov rbx, QWORD [rbx+NEXT_OFFSET] jmp .loop
.print_null: mov rax, 1 mov rdi, 1 lea rsi, [rel null_str] mov rdx, 5 ; "NULL\n" is 5 bytes syscall
pop rbx ret
section .data arrow_str: db " -> " null_str: db "NULL", 10print_int_no_newline uses the same divide-by-ten idea as the previous lesson's print_uint, minus the trailing newline. It handles non-negative values only, which is all this list stores:
section .text
; print_int_no_newline: write edi (unsigned) to stdout, no newlineprint_int_no_newline: sub rsp, 16 ; room for up to 10 digits mov eax, edi lea rsi, [rsp+16] ; fill the buffer backwards mov ecx, 10.digit: xor edx, edx div ecx ; eax = eax / 10, edx = eax % 10 add dl, '0' dec rsi mov [rsi], dl test eax, eax jnz .digit
lea rdx, [rsp+16] sub rdx, rsi ; length = end - first digit mov rax, 1 ; syscall: write mov rdi, 1 ; fd: stdout syscall add rsp, 16 retThe traversal loop mirrors the C while loop exactly:
- Load the current pointer
- Check if it's NULL (
test rbx, rbx) - If NULL, exit
- Process the current node
- Advance to the next node (
mov rbx, [rbx+8]) - Jump back to step 2
That mov rbx, QWORD [rbx+NEXT_OFFSET] is the pointer follow: it loads the 8 bytes at rbx + 8 (the next field) back into rbx. One instruction. The whole essence of linked-list traversal.
Insertion in the Middle
Inserting after a given node requires manipulating two pointers:
void insert_after(struct Node *node, int value) { struct Node *new_node = malloc(sizeof(struct Node)); new_node->data = value; new_node->next = node->next; node->next = new_node;}; insert_after: insert a new node after the given node; Input: rdi = pointer to existing node, esi = valueinsert_after: push rbx push r12 push r13 mov r12, rdi ; Save node pointer mov r13d, esi ; Save value
; Allocate new node mov rdi, NODE_SIZE call alloc mov rbx, rax ; rbx = new_node
; new_node->data = value mov DWORD [rbx+DATA_OFFSET], r13d
; new_node->next = node->next mov rax, QWORD [r12+NEXT_OFFSET] mov QWORD [rbx+NEXT_OFFSET], rax
; node->next = new_node mov QWORD [r12+NEXT_OFFSET], rbx
pop r13 pop r12 pop rbx retTwo mov instructions of pointer surgery:
- Copy
node->nextintonew_node->next— the new node inherits the old "next" - Point
node->nextat the new node
Deletion
Deleting a node requires finding its predecessor:
; delete_node: remove the first node with the given value; Input: edi = value to deletedelete_node: push rbx push r12 mov r12d, edi ; Save target value
; Special case: deleting the head mov rbx, [rel head] test rbx, rbx jz .not_found cmp DWORD [rbx+DATA_OFFSET], r12d jne .search
; head = head->next mov rax, QWORD [rbx+NEXT_OFFSET] mov [rel head], rax ; The bump allocator has no free, so the old head simply leaks pop r12 pop rbx ret
.search: ; rbx = current node, check if rbx->next has our value mov rax, QWORD [rbx+NEXT_OFFSET] ; rax = next node test rax, rax jz .not_found
cmp DWORD [rax+DATA_OFFSET], r12d je .found
mov rbx, rax ; Advance: curr = next jmp .search
.found: ; rbx->next = rbx->next->next mov rcx, QWORD [rax+NEXT_OFFSET] ; rcx = node_to_delete->next mov QWORD [rbx+NEXT_OFFSET], rcx ; prev->next = deleted->next ; No free here either: the unlinked node leaks
.not_found: pop r12 pop rbx retBecause alloc is a bump allocator, deletion only unlinks: the node's 16 bytes stay allocated until the process exits. That's fine for a demo. A long-running program would need a free list (keep unlinked nodes in a chain and hand them back out from alloc) or a real allocator.
Running It
None of these functions runs on its own, because there's no _start yet. Put this entry point at the top of a file called list.asm, then paste every block from this lesson underneath it in the order they appear (the constants first). print_list switches to .data for its two strings, and the section .text at the top of print_int_no_newline switches back, so the code after it stays executable.
section .text global _start
_start: mov edi, 3 call push_front mov edi, 2 call push_front mov edi, 1 call push_front call print_list ; 1 -> 2 -> 3 -> NULL
mov rdi, [rel head] ; insert 9 after the first node mov esi, 9 call insert_after call print_list ; 1 -> 9 -> 2 -> 3 -> NULL
mov edi, 2 ; a node in the middle call delete_node mov edi, 1 ; the head call delete_node call print_list ; 9 -> 3 -> NULL
mov eax, 60 ; exit(0) xor edi, edi syscallBuild it with nasm -f elf64 list.asm -o list.o && ld list.o -o list on a Linux x86-64 machine. Leave out that section .text line in print_int_no_newline and the program segfaults on its first call to it, because the function lands in the data section, which isn't executable. Worth seeing once on purpose.
What This Teaches You
Hand-writing the assembly version surfaces a few truths about your C:
-
Struct access is free. The
->operator is a constant addition. No lookup, no hash, no indirection beyond a single pointer follow. -
malloc is the expensive part. The pointer choreography itself (3-4
movinstructions per insertion) is trivial. The allocator swallows the cost. -
NULL checks are cheap. Testing a register against zero (
test rbx, rbx) is a one-cycle instruction. The branch predictor gets it right most of the time too. -
Pointers are just 8-byte values. Nothing mystical about them in assembly. Integers that happen to be used as addresses.
-
Cache behaviour beats instruction count. Linked list nodes drift across memory; array elements sit contiguous. Each
mov rbx, [rbx+8]is a potential cache miss if the next node is on a cold line. This is why arrays often crush linked lists in practice, even with "worse" Big-O for insertions.