Creating a Linked List

To create a linked list, we need two things:

• A way to create a node and allocate it on the heap
• A head pointer that points to the first node

An empty linked list is simply a head pointer that points to nothing.

In C

// Creates a new node on the heap
Node *create_node(int data) {
    // Allocate memory for a new node
    Node *node = (Node *)malloc(sizeof(Node));

    // Set the data
    node->data = data;

    // Initially, the node doesn't point to anything
    node->next = NULL;

    return node;
}

// Start with head pointing to NULL
Node *head = NULL;

// Create three nodes
Node *a = create_node(1);
Node *b = create_node(2);
Node *c = create_node(3);

// Link them together
a->next = b;    // Node a points to node b
b->next = c;    // Node b points to node c
// c->next is already NULL, so c is the end of list

// Point head at the first node
head = a;

After linking, the linked list looks like this:

HEAD -> [1 | next] -> [2 | next] -> [3 | NULL]

Node *create_node(int data) takes an integer data and creates a new node on the heap with that data. It returns a pointer to the newly created node.

a->next = b links node a to node b by storing b's memory address in a's next pointer. Same goes with node b and node c.

head is just a pointer that points to node a.

WARNING

malloc can fail and return NULL if the system is out of memory. In production code we should always check if node is NULL before using it to avoid dereferencing a NULL pointer, which would crash the program.

In Rust

// Implement a constructor for Node that returns a heap allocated Box<Node>
impl Node {
    fn new(data: i32) -> Box<Node> {
        Box::new(Node { data, next: None })
    }
}

// Create three nodes
let mut a = Node::new(1);
let mut b = Node::new(2);
let c = Node::new(3);

// Link them together
b.next = Some(c);   // Node b points to node c
a.next = Some(b);   // Node a points to node b

// Point head at the first node
let head = Some(a);

After linking, the list looks like this:

HEAD -> [1 | SOME] -> [2 | SOME] -> [3 | NONE]

Notice that we link the nodes in reverse order (we wrote b.next = Some(c) before a.next = Some(b)). This is because of a concept in Rust known as ownership. Once we move b into a.next, we can no longer access b directly to set its next.

What is impl?

impl stands for "implementation". It lets us define methods (functions) that belong to a specific type.

In C, if we want functions for a Node, we write standalone functions like this:

Node *create_node(int data) { ... }
void insert_node(Node **head, int data) { ... }

In Rust, we can group these functions inside an impl block:

impl Node {
    fn new(data: i32) -> Box<Node> { ... }
    fn insert(&mut self, data: i32) { ... }
}

This makes it clear these functions "belong to" Node. Instead of calling create_node(data), we call Node::new(data). We could create standalone functions in Rust, but using impl is cleaner and more organized.

Key Difference

	C	Rust
Empty list	Node *head = NULL	let head: Option<Box<Node>> = None
Create node	create_node(data)	Node::new(data)
Allocate on heap	malloc(sizeof(Node))	Box::new(Node { ... })
Link nodes	a->next = b	a.next = Some(b)
Allocation failure	Returns NULL silently	Panics immediately
Free nodes	free() each manually	Automatic