C Data Structures Tutorial | Linked List, Stack, Queue

📖 What to learn on this page

✅ Must-know essentials

Linked list: each node points to the next
Stack: last-in first-out (LIFO)
Queue: first-in first-out (FIFO)

⭐ Read if you have time

Trees and hash tables
Complexity: O(n), O(1)
Comparison with STL / standard libraries

What is a Data Structure? — Designing How Data is Arranged

A data structure defines how data is laid out in memory and how it is manipulated. Arrays are themselves a data structure, but there are situations where arrays alone are inconvenient.

Limitations of arrays

Slow middle/front insertion

To insert near the front, all the later elements must be shifted. With a million items, that's a million shifts.

Fixed size

The size is fixed at declaration, which is awkward for data that grows and shrinks (malloc helps, but it's extra work).

Common data structures

Structure	Characteristic	Example use
Linked list	Nodes linked by pointers; fast insertion/deletion	Ordered data with frequent insert/remove
Stack	Last-in, first-out (LIFO)	Function calls, Undo history
Queue	First-in, first-out (FIFO)	Print queue, task scheduling

All of these are implemented with a combination of structs, pointers, and malloc. This lesson brings together everything we have learned so far!

Linked List — A Chain Connected by Pointers

A linked list is a sequence in which each element (node) contains data and a pointer to the next node.

Node definition

typedef struct Node {
  int data;              // the stored data
  struct Node *next;     // pointer to the next node
} Node;

Picture of memory

10
next→

→

20
next→

→

30
next→

→

NULL

Key operations

// (1) Create a node
Node* createNode(int val) {
  Node *n = malloc(sizeof(Node));
  n->data = val;
  n->next = NULL;
  return n;
}

// (2) Insert at the front (O(1) — fast!)
void pushFront(Node **head, int val) {
  Node *n = createNode(val);
  n->next = *head;     // new node's next = old head
  *head = n;           // head now points to new node
}

// (3) Print all elements
void printList(Node *head) {
  for (Node *p = head; p != NULL; p = p->next)
    printf("%d → ", p->data);
  printf("NULL\n");
}

// (4) Free the memory (forgetting leaks!)
void freeList(Node *head) {
  while (head) {
    Node *tmp = head->next;
    free(head);
    head = tmp;
  }
}

Front insertion

O(1) — very fast

O(n) — traverse from the head

Compared to arrays

No index access; random access is not its strength

Stack — Last In, First Out (LIFO)

A stack pops off the most recently pushed item first. Imagine stacking plates. Function calls are also managed on a stack.

Stack visualization

10

20

30

← TOP (items come off here)

// push: add to the top
void push(Node **top, int val) {
  Node *n = createNode(val);
  n->next = *top;
  *top = n;
}

// pop: remove from the top
int pop(Node **top) {
  if (*top == NULL) return -1;
  Node *tmp = *top;
  int val = tmp->data;
  *top = tmp->next;
  free(tmp);
  return val;
}

Everyday examples: the Back button in a browser, Ctrl+Z (Undo), and the call stack that tracks function calls — all of these use a stack.

Queue — First In, First Out (FIFO)

A queue removes items in the same order they were added — just like a checkout line.

Queue visualization

Out ←

10

20

30

→ In

// enqueue: add to the tail
void enqueue(Node **head, Node **tail, int val) {
  Node *n = createNode(val);
  if (*tail) (*tail)->next = n;
  else *head = n;
  *tail = n;
}

// dequeue: remove from the head
int dequeue(Node **head, Node **tail) {
  if (!*head) return -1;
  Node *tmp = *head;
  int val = tmp->data;
  *head = tmp->next;
  if (!*head) *tail = NULL;
  free(tmp);
  return val;
}

Everyday examples: printer queues, OS task schedulers, chat message ordering.

Array vs Linked List vs Stack vs Queue

Operation	Array	Linked list	Stack	Queue
Insert at front	O(n)	O(1)	—	—
Append at back	O(1)	O(1)*	O(1)	O(1)
Random access	O(1)	O(n)	—	—
Insert in middle	O(n)	O(1)†	—	—

* with a tail pointer. † when the insertion point is known.

Linked List Demo

Add and remove elements from a linked list with the buttons, and watch the structure update in real time.

List state:

(empty list)

Press a button to manipulate the list.

Quick Quiz

Check your understanding of this lesson.

Q1. What is an advantage of a linked list?

Fast random access

Efficient insertion and deletion

Uses less memory

Insertion/deletion in a linked list only requires re-pointing; arrays require shifting elements, which is slow.

Q2. In what order does a stack return items?

FIFO (first in, first out)

LIFO (last in, first out)

Random

A stack is LIFO (Last In, First Out): the most recently pushed item is the first to come off.

Q3. In what order does a queue return items?

FIFO (first in, first out)

LIFO (last in, first out)

Priority order

A queue is FIFO (First In, First Out), just like a line at a checkout.

What is a Data Structure? — Designing How Data is Arranged

Limitations of arrays

Common data structures

Linked List — A Chain Connected by Pointers

Node definition

Picture of memory

Key operations

Stack — Last In, First Out (LIFO)

Queue — First In, First Out (FIFO)

Array vs Linked List vs Stack vs Queue

Linked List Demo

Related lessons

Quick Quiz

Q1. What is an advantage of a linked list?

Q2. In what order does a stack return items?

Q3. In what order does a queue return items?