Skip to main content
Be Bitwise
CAssembly Equivalents of C Patterns

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:

c
#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:

c
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:

asm
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.

asm
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 memory
alloc:
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
ret

This 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

asm
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 insert
push_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
ret

Compare 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-64
C Source
1void push_front(int value) {
2 struct Node *new_node = malloc(sizeof(struct Node));
3 new_node->data = value;
4 new_node->next = head;
5 head = new_node;
6}
Assembly
1push_front:
2 push rbx
3 push r12
4 mov r12d, edi
5 mov rdi, NODE_SIZE
6 call alloc
7 mov rbx, rax
8 mov DWORD [rbx+DATA_OFFSET], r12d
9 mov rax, [rel head]
10 mov QWORD [rbx+NEXT_OFFSET], rax
11 mov [rel head], rbx
12 pop r12
13 pop rbx
14 ret

Hover 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

asm
; print_list: traverse the list and print each node's data
print_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", 10

print_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:

asm
section .text
; print_int_no_newline: write edi (unsigned) to stdout, no newline
print_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
ret

The traversal loop mirrors the C while loop exactly:

  1. Load the current pointer
  2. Check if it's NULL (test rbx, rbx)
  3. If NULL, exit
  4. Process the current node
  5. Advance to the next node (mov rbx, [rbx+8])
  6. 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:

c
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;
}
asm
; insert_after: insert a new node after the given node
; Input: rdi = pointer to existing node, esi = value
insert_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
ret

Two mov instructions of pointer surgery:

  1. Copy node->next into new_node->next — the new node inherits the old "next"
  2. Point node->next at the new node

Deletion

Deleting a node requires finding its predecessor:

asm
; delete_node: remove the first node with the given value
; Input: edi = value to delete
delete_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
ret

Because 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.

asm
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
syscall

Build 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:

  1. Struct access is free. The -> operator is a constant addition. No lookup, no hash, no indirection beyond a single pointer follow.

  2. malloc is the expensive part. The pointer choreography itself (3-4 mov instructions per insertion) is trivial. The allocator swallows the cost.

  3. 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.

  4. Pointers are just 8-byte values. Nothing mystical about them in assembly. Integers that happen to be used as addresses.

  5. 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.