C DSA Linked Lists

What is a Linked List?

A linked list stores items in nodes. Each node holds two things:

• data - the value
• next - a pointer to the next node

The first node is called the head. The last node points to NULL, which means "this is the end of the list".

Linked Lists vs. Arrays

A linked list is similar to an array, but it stores its values in a different way.

Both store many values. But they are good at different things:

Create a Node

In C, a node is a structure with a value and a pointer:

struct Node {
  int data;
  struct Node *next;
};

A structure that points to its own type might look strange at first. It just means: "a node knows where the next node is".

Link Nodes Together

Let's create three nodes and link them. Then we "walk" through the list and print each value:

#include <stdio.h>

struct Node {
  int data;
  struct Node *next;
};

int main() {
  // Create three nodes
  struct Node a, b, c;
  a.data = 10;
  b.data = 20;
  c.data = 30;

  // Link them together
  a.next = &b;
  b.next = &c;
  c.next = NULL; // The last node points to NULL

  // Walk through the list and print each value
  struct Node *current = &a;
  while (current != NULL) {
    printf("%d -> ", current->data);
    current = current->next;
  }
  printf("NULL\n");

  return 0;
}

10 -> 20 -> 30 -> NULL

Example Explained

• &b is the memory address of node b. So a.next = &b; makes a point to b.
• current is a pointer that starts at the first node.
• current->data reads the value of the node that current points to (see Structs and Pointers).
• current = current->next; moves to the next node. When current is NULL, the loop stops.

Visiting every node, one by one, is called traversing the list.

Insert a Node in the Middle

Here is where linked lists shine. To put a new node between two others, you only change two pointers. Nothing else moves!

We also put the printing loop in a function, printList(), so we can use it again:

#include <stdio.h>

struct Node {
  int data;
  struct Node *next;
};

void printList(struct Node *head) {
  struct Node *current = head;
  while (current != NULL) {
    printf("%d -> ", current->data);
    current = current->next;
  }
  printf("NULL\n");
}

int main() {
  struct Node a, b, c;
  a.data = 10;
  b.data = 20;
  c.data = 30;
  a.next = &b;
  b.next = &c;
  c.next = NULL;

  printList(&a);

  // Put a new node (15) between 10 and 20
  struct Node d;
  d.data = 15;
  d.next = &b; // 15 points to 20
  a.next = &d; // 10 points to 15

  printList(&a);

  return 0;
}

10 -> 20 -> 30 -> NULL
10 -> 15 -> 20 -> 30 -> NULL

With an array, you would have to move 20 and 30 one step to the right to make room. With a linked list, you just "hook in" the new node.

Run the simulation below to see how the code above works, one step at a time. The green arrow is the pointer that just changed:

Summary

• A linked list stores items in nodes. Each node has a value and a pointer to the next node.
• The first node is the head. The last node points to NULL.
• To visit every node, start at the head and follow the next pointers.
• Adding a node only changes pointers. No other items need to move.

So far, our nodes are fixed variables in main(). In the next chapter, you will create nodes while the program runs, and learn to insert and delete them.