Journey into Data Structures · Part 1 of 1

Aug 25, 2026

Linked Lists

Required knowledge

Arrays
Pointers

What are Linked Lists?

Linked Lists are a data structure that feel similar to a normal array. You can loop from start to end. In a Doubly Linked List, you could even loop in reverse order. They are 0(n) for a complete traversal. Instead of using pointer math to find the next item, it uses references to other items in the data structure. So each item (or Node) has a next and/or prev reference for the next/prev nodes in the list and traversal is essentially just following the breadcrumb trails each Node provides.

Why do Linked Lists have a bad reputation?

It all comes down to speed and performance. They just do not compete with arrays and other data structures. We’ll dive deeper into why later (hint: it has to do with caching). For now lets look at how to build and use them. Later we’ll touch more on why we should avoid them but the techniques you’ll learn building and using Linked Lists will come in handy for future data structures.

Key Technical Advantages

Fast Insertions and Deletions:

Adding or removing a node requires only updating pointer references. This takes O(1) time if you already have a reference to that position.

Cheap List Splitting and Merging:

You can split one list into two, or glue two lists together, in O(1) constant time. This is heavily utilized in complex systems like the Linux kernel and Redis.

Memory Fragmentation Resistance:

They can utilize scattered, non-contiguous pockets of free memory. This makes them highly effective in low-level systems or embedded environments.

Linked List demonstration

Before we jump into the code, here is fun little visual illustration on how linked lists work.

head

tail

Add or remove a node to see the pointers change.

head → 1, tail → 3, size = 3
node 1: prev → NULL, next → 2
node 2: prev → 1, next → 3
node 3: prev → 2, next → NULL

The Code

The structs are pretty simple. Each node will track what is next and previous of its location in the list so we can traverse forward and backwards. I also added an enum LinkedListError for specific errors that could occur that I want to report to the caller.

linked-list.h


typedef enum {
  LINKED_LIST_OK,
  LINKED_LIST_ERROR_NO_MEMORY,
  LINKED_LIST_ERROR_OUT_OF_RANGE,
  LINKED_LIST_ERROR_NULL_ARG,
  LINKED_LIST_ERROR_NOT_FOUND,
} LinkedListError;

typedef struct LLNode {
  void *item;
  struct LLNode *next; // for forward traversal
  struct LLNode *prev; // for reverse traversal
} LLNode;

typedef struct LinkedList {
  LLNode *head; // for the first item in the list
  LLNode *tail; // for the last item in the list
  int size; // total number of nodes
} LinkedList;

Lets declare some functions in our header file.

linked-list.h

LinkedList *ll_create(void);
void ll_destroy(LinkedList *list);

LinkedListError ll_prepend(LinkedList *list, void *item);
LinkedListError ll_append(LinkedList *list, void *item);

LinkedListError ll_remove_front(LinkedList *list, void **out_item);
LinkedListError ll_remove_back(LinkedList *list, void **out_item);
LinkedListError ll_remove_at(LinkedList *list, int index, void **out_item);

LinkedListError ll_get(LinkedList *list, int index, void **out_item);

Creating a list is pretty simple. We are creating memory for our list and initializing all bits to zero, then returning the pointer to that list.

linked-list.c

LinkedList *ll_create(void) {
  LinkedList *list = calloc(1, sizeof *list);
  return list;
}

The next thing we want to do is add a node item to our list. I have 3 functions for this:

node_create (static)
ll_prepend
ll_append

node_create just creates the node struct with no references to the next or previous node. We’ll let ll_prepend and ll_append manage that part.

linked-list.c

static LLNode *node_create(void *item) {
  LLNode *node = malloc(sizeof *node);
  if (node == NULL) {
    return NULL;
  }
  node->item = item;
  node->next = NULL;
  node->prev = NULL;
  return node;
}

For appending an item to the list, we need to reference the lists head and tail references. By default head and tail should be NULL for an empty list. If tail is NULL we can assume the list is empty because there should always be a tail if one or more items exist in list. If thats the case, just set the head and tail pointers to the node you are appending. Since its the first item in the list, that item will be both the start and end of the list.

If there is a tail then we know the list is not empty and since we are appending to the list, we need to update the references at the tail end. One thing to keep in mind for how we update the list is one node references another going in one direction with its next pointer. If we want to go in the opposite direction, we need to update a prev pointer as well. Since this list is going to support both forward and backward traversal we need to update both directions. So the update goes in this order:

Current tail’s next reference, which should be NULL, will point to our new node
Our new node will have its prev point to the current tail node.
Update the tail to be our new node
…and of course, increase the size to keep track of how many items are in the list

linked-list.c

LinkedListError ll_append(LinkedList *list, void *item) {
  if (list == NULL) {
    return LINKED_LIST_ERROR_NULL_ARG;
  }

  LLNode *node = node_create(item);
  if (node == NULL) {
    return LINKED_LIST_ERROR_NO_MEMORY;
  }

  if (list->tail == NULL) {
    list->head = node;
    list->tail = node;
  } else {
    node->prev = list->tail;
    list->tail->next = node;
    list->tail = node;
  }

  list->size++;
  return LINKED_LIST_OK;
}

For adding at the beginning of the list, its a similar concept as appending:

Current head’s prev reference, which should be NULL, will now point to our new node
Our new node’s next reference will point to the current head
The head will now point to our new node
increase the size

linked-list.c

LinkedListError ll_prepend(LinkedList *list, void *item) {
  if (list == NULL) {
    return LINKED_LIST_ERROR_NULL_ARG;
  }

  LLNode *node = node_create(item);
  if (node == NULL) {
    return LINKED_LIST_ERROR_NO_MEMORY;
  }

  node->next = list->head;
  if (list->head != NULL) {
    list->head->prev = node;
  } else {
    list->tail = node;
  }
  list->head = node;

  list->size++;
  return LINKED_LIST_OK;
}

Important note

Just want to inject something important here. The order of operations matters here. If you were to set the tail or head reference to the new node before setting the old references next or prev first, you will lose that reference for good and could be left with a memory leak. That is, that piece of dynamically allocated memory has no reference anymore. So always be careful when managing pointers to dynamic blocks of memory.

Ok, so thats appending and prepending. So, what if we need to get a node in the list at a specific index? Lets think about that for a second. If its the first or last index, thats easy. Just return the head or the tail. No need to add a fancy function for that scenario. Getting anything in the middle is not so simple. Well it is, but its not exactly as performant as an array. You will have to traverse the array until you get to the index you are looking for. YIKES! Some of the warts of a linked list are starting to show. Lets add a naive implementation for getting a node by its index. I’m using a static helper called node_get that hands back the node itself instead of the item. That will pay off in a minute when we need to remove from the middle of the list:

linked-list.c

static LinkedListError node_get(LinkedList *list, int index, LLNode **out_node) {
  if (index < 0 || index >= list->size) {
    return LINKED_LIST_ERROR_OUT_OF_RANGE;
  }

  LLNode *current = list->head;
  for (int i = 0; i < index; i++) {
    current = current->next;
  }

  *out_node = current;
  return LINKED_LIST_OK;
}

As you can see, getting an item by its index is pretty costly in a linked list. It is O(n) whereas an Array is O(1). A pretty simple loop so far but we can optimize this a bit better. Since we can traverse forwards and backwards, we can determine if the index falls in the first half of the size or the second half. So if a list has 10 items, and you need the third item. It would be faster to start from the head position. However, if you were to try get the seventh item, you may want to start from the tail and work your way backwards.

Lets update our code to do this a little better:

linked-list.c

static LinkedListError node_get(LinkedList *list, int index, LLNode **out_node) {
  if (index < 0 || index >= list->size) {
    return LINKED_LIST_ERROR_OUT_OF_RANGE;
  }

  LLNode *current;
  if (index < list->size / 2) {
    current = list->head;
    for (int i = 0; i < index; i++) {
      current = current->next;
    }
  } else {
    current = list->tail;
    for (int i = list->size - 1; i > index; i--) {
      current = current->prev;
    }
  }

  *out_node = current;
  return LINKED_LIST_OK;
}

There, much better. Still slow, but less slow now.

The public ll_get is just a thin wrapper around node_get. Notice the item comes back through an out_item parameter instead of the return value. The return value is reserved for the LinkedListError. Why? Because NULL is a perfectly valid item to store in a list. If ll_get returned the item directly, you could never tell the difference between “the item is NULL” and “that index doesn’t exist”.

linked-list.c

LinkedListError ll_get(LinkedList *list, int index, void **out_item) {
  if (list == NULL || out_item == NULL) {
    return LINKED_LIST_ERROR_NULL_ARG;
  }

  LLNode *node = NULL;
  LinkedListError err = node_get(list, index, &node);
  if (err != LINKED_LIST_OK) {
    return err;
  }

  *out_item = node->item;
  return LINKED_LIST_OK;
}

Next, we need to be able to remove items from our list. We have 3 functions we can start to implement now:

ll_remove_front
ll_remove_back
ll_remove_at

Removing an item from the front or back is pretty simple. Some things to think about when removing anything in a linked list:

Whether its from the front/back, the head/tail will need to be updated
You need to decrease the size after removal
Its good practice to return the item in case you need a reference to it since we are removing the reference in the linked list. If we didn’t, then we most likely could be introducing a memory leak. We are going to leave the decision to free the memory for the item on the caller so returning the item is crucial for this step.

There is one more rule about ownership worth stating clearly: the list owns the nodes, the caller owns the items. Removing something from the list frees the node but never the item. That’s why every remove function takes a void **out_item. The removed item gets written to *out_item so you can decide what to do with it (use it, free it, put it in another list). If you don’t care about it, pass NULL and the item is simply discarded. If something goes wrong, *out_item is left untouched.

Here is the interesting part. Removing from the front, the back, or the middle are all the same operation: take a node, and stitch its neighbours together so nothing points at it anymore. So instead of writing that three times, we write it once in a static helper called node_unlink.

There are 4 things it needs to handle:

If the node has no prev, it was the head, so the head becomes the node’s next. Otherwise, the previous node’s next skips over our node.
If the node has no next, it was the tail, so the tail becomes the node’s prev. Otherwise, the next node’s prev skips over our node.
Hand the item to the caller (if they asked for it)
Free the node and decrease the size

linked-list.c

static void node_unlink(LinkedList *list, LLNode *node, void **out_item) {
  if (node->prev == NULL) {
    list->head = node->next;
  } else {
    node->prev->next = node->next;
  }

  if (node->next == NULL) {
    list->tail = node->prev;
  } else {
    node->next->prev = node->prev;
  }

  if (out_item != NULL) {
    *out_item = node->item;
  }

  free(node);
  list->size--;
}

Watch the order again

We copy node->item into out_item before calling free(node). Reading anything from a node after it has been freed is a use-after-free bug.

Notice how this handles the edge cases for free. Removing the only node in the list? It has no prev and no next, so both head and tail become NULL, which is exactly what an empty list looks like. No special case needed.

With node_unlink doing the heavy lifting, ll_remove_front and ll_remove_back are just a couple of checks. A NULL list is a LINKED_LIST_ERROR_NULL_ARG and an empty list has nothing to remove, so we report LINKED_LIST_ERROR_NOT_FOUND.

linked-list.c

LinkedListError ll_remove_front(LinkedList *list, void **out_item) {
  if (list == NULL) {
    return LINKED_LIST_ERROR_NULL_ARG;
  }
  if (list->head == NULL) {
    return LINKED_LIST_ERROR_NOT_FOUND;
  }

  node_unlink(list, list->head, out_item);
  return LINKED_LIST_OK;
}

LinkedListError ll_remove_back(LinkedList *list, void **out_item) {
  if (list == NULL) {
    return LINKED_LIST_ERROR_NULL_ARG;
  }
  if (list->tail == NULL) {
    return LINKED_LIST_ERROR_NOT_FOUND;
  }

  node_unlink(list, list->tail, out_item);
  return LINKED_LIST_OK;
}

Now ll_remove_at pays off our earlier decision to split out node_get. Find the node, then unlink it. Two different error codes are possible here: an empty list is NOT_FOUND (there is nothing to find), while a bad index on a list that has items is OUT_OF_RANGE.

linked-list.c

LinkedListError ll_remove_at(LinkedList *list, int index, void **out_item) {
  if (list == NULL) {
    return LINKED_LIST_ERROR_NULL_ARG;
  }
  if (list->head == NULL) {
    return LINKED_LIST_ERROR_NOT_FOUND;
  }

  LLNode *node = NULL;
  LinkedListError err = node_get(list, index, &node);
  if (err != LINKED_LIST_OK) {
    return err;
  }

  node_unlink(list, node, out_item);
  return LINKED_LIST_OK;
}

The last function is ll_destroy. Since we allocated every node on the heap, we need to give them back. Walk the list from the head and free each node. The important detail: grab the next pointer before freeing the current node, otherwise you’ve just freed the very thing you needed to find the next node. Finally free the list itself. Remember, this only frees the nodes and not the items. If your items were allocated on the heap, pop them off with the remove functions and free them first.

linked-list.c

void ll_destroy(LinkedList *list) {
  if (list == NULL) {
    return;
  }

  LLNode *current = list->head;
  while (current != NULL) {
    LLNode *next = current->next;
    free(current);
    current = next;
  }

  free(list);
}

Testing it

Linked lists are easy to get subtly wrong. A single prev pointer that doesn’t get updated will go unnoticed until you traverse backwards. So the tests I wrote lean on one helper that checks everything at once. assert_list_matches walks the list forward and backward, comparing each item against what we expect, and verifies that every next/prev pair agrees with each other. It also checks that an empty list has a NULL head and tail.

linked-list.test.c

static void assert_list_matches(LinkedList *list, int **expected, int n) {
  assert(list->size == n);

  if (n == 0) {
    assert(list->head == NULL);
    assert(list->tail == NULL);
    return;
  }

  assert(list->head->prev == NULL);
  assert(list->tail->next == NULL);

  int i = 0;
  for (LLNode *node = list->head; node != NULL; node = node->next, i++) {
    assert(i < n);
    assert(node->item == expected[i]);
    if (node->next != NULL) {
      assert(node->next->prev == node);
    }
  }
  assert(i == n);

  i = n - 1;
  for (LLNode *node = list->tail; node != NULL; node = node->prev, i--) {
    assert(i >= 0);
    assert(node->item == expected[i]);
  }
  assert(i == -1);
}

With that in place, each test is short. Build a list, do something to it, and assert the result:

linked-list.test.c

static void test_ll_mixed_prepend_and_append(void) {
  LinkedList *list = ll_create();
  int a = 1, b = 2, c = 3, d = 4;

  ll_append(list, &b);
  ll_prepend(list, &a);
  ll_append(list, &c);
  ll_prepend(list, &d);

  int *expected[] = {&d, &a, &b, &c};
  assert_list_matches(list, expected, 4);
  ll_destroy(list);
}

static void test_ll_remove_at_middle(void) {
  int items[5];
  LinkedList *list = make_list(items, 5);
  void *out = NULL;

  assert(ll_remove_at(list, 2, &out) == LINKED_LIST_OK);
  assert(out == &items[2]);

  int *expected[] = {&items[0], &items[1], &items[3], &items[4]};
  assert_list_matches(list, expected, 4);
  ll_destroy(list);
}

A few of the edge cases I made sure to cover, since this is where linked list bugs love to hide:

Removing the only element, which must leave both head and tail NULL
Removing the head and tail through ll_remove_at, not just the dedicated functions
Tail-side traversal, picking an index in the second half of the list so node_get walks backwards
Errors leave things alone: a bad index must not modify the list or touch *out_item
A stored NULL is a valid item, and ll_get can tell it apart from an error
The caller owns the item: after a remove, a heap allocated item is still valid and can be freed by the caller
Reusing a drained list, since stale head/tail pointers would show up here

Wrapping up

That’s a complete doubly linked list. The pointer wiring is the whole trick: every insertion or removal is a handful of pointer updates, and the only expensive operation is finding a node by index. That is a cost of walking the breadcrumb trail, which is why ll_get and ll_remove_at are O(n) while the front and back operations are O(1).

The habits from this one carry over to nearly every pointer-based structure we will build later: update pointers in the right order, handle the empty and single-element cases, and be explicit about who owns the memory.

So if a linked list is this straightforward, why do people steer clear of them? Next up, we’ll compare them against arrays and see exactly where the time goes.