What are Linked List Basics in C- C Programming Course For Engineering Students

🚀 Learn BLE on Linux (BlueZ) – Programming Part 1

Hands-on Bluetooth Low Energy course. Special price: ₹399

Enroll Now on Udemy →
💬 Need help or career guidance? Ask us!Contact Us →

Free C Programming Course · Structure and Union · Lecture 28

Linked List Basics in C

Understand nodes, the start pointer and the NULL terminator, and see when a linked list beats an array. Part of our free C tutorial and free embedded C course.

A linked list in C is a chain of small records, called nodes, where every node knows the address of the next one. It is the first dynamic data structure most students meet, and it appears constantly in embedded C programming: in RTOS kernels, in driver queues and in protocol stacks. In this lecture of our free C programming course you will build a three-node list by hand, read it back, and learn exactly why this structure exists.

What You Will Learn

  • The two problems with storing a list in an array
  • The anatomy of a node: information part and link part
  • Why a single start pointer controls the whole list
  • How an empty list and the last node are represented
  • How to create linked nodes with malloc() and release them with free()
  • A fair table comparing arrays and linked lists

Prerequisites

Read the previous lecture on self referential structures first, and be comfortable with malloc(), free() and pointer dereferencing from the Pointers chapter of this free C tutorial.

Why Not Just Use an Array?

An array is the simplest way to keep a collection, but it has two weaknesses that show up quickly in real projects.

  • Fixed capacity. You must choose the size in advance. If you reserve room for 100 entries and only 10 arrive, 90 slots of precious RAM sit idle. If 101 arrive, you have an overflow.
  • Costly insertion and deletion. To put a new element in the middle, every element after it must shift one place. Removing one means shifting the others back to close the gap.

A linked list attacks both problems. It allocates one node at a time, so memory use follows the real number of entries. And it inserts or removes a node by changing a couple of pointers, with no shifting of data at all.

Anatomy of a Node

Each node has two parts: the information part that carries your data, and the link part that carries the address of the next node. The link of the very last node is NULL, which tells every loop that the chain has ended.

struct node {
    int info;              /* the data we store */
    struct node *link;     /* address of the next node, or NULL */
};
A node has an information part and a link part
info = 7link→info = 14link→info = 21link = NULL

The Start Pointer: Your Only Handle

Nodes of a linked list are scattered through memory. They are not neighbours the way array elements are, so there is no array name to index from. Instead you keep one pointer, conventionally called start or head, that holds the address of the first node. Every operation begins there and follows links onward. If you lose this pointer without freeing the list, you lose the whole list and leak its memory.

struct node *start = NULL;   /* an empty list */

An empty list is simply start == NULL. There is no special “empty” node.

start leads to the first node; nodes need not be adjacent
start→node A→node B→node C→NULL
empty list: start = NULL

Building a List by Hand

Before writing helper functions, build a three-node list the slow way so every pointer movement is visible. We allocate each node with malloc(), fill in its data, then connect the nodes in order.

#include <stdio.h>
#include <stdlib.h>

struct node {
    int info;
    struct node *link;
};

int main(void)
{
    struct node *start = NULL;
    struct node *n1, *n2, *n3;

    printf("empty list? %s\n", start == NULL ? "yes" : "no");

    n1 = malloc(sizeof *n1);
    n2 = malloc(sizeof *n2);
    n3 = malloc(sizeof *n3);
    if (!n1 || !n2 || !n3) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }

    n1->info = 7;   n1->link = n2;
    n2->info = 14;  n2->link = n3;
    n3->info = 21;  n3->link = NULL;
    start = n1;

    printf("empty list? %s\n", start == NULL ? "yes" : "no");
    printf("first  = %d\n", start->info);
    printf("second = %d\n", start->link->info);
    printf("third  = %d\n", start->link->link->info);
    printf("third->link is %s\n",
           start->link->link->link == NULL ? "NULL" : "not NULL");

    free(n3);
    free(n2);
    free(n1);
    return 0;
}
$ gcc -Wall -Wextra -o list_basic list_basic.c
$ ./list_basic

Expected output:

empty list? yes
empty list? no
first  = 7
second = 14
third  = 21
third->link is NULL

Walking through the code

  1. malloc(sizeof *n1) asks for exactly one node. Using sizeof *n1 instead of sizeof(struct node) keeps the line correct even if you later rename the type.
  2. The checks for NULL matter. On a small microcontroller heap, malloc() can really fail.
  3. Each link is set to the next node, and the last one to NULL.
  4. start = n1 hands the list over to the single handle that represents it.
  5. start->link->info reads “the info of the node that start’s link points to”, which is the second node.
  6. We free the nodes at the end. Every malloc() needs a matching free().
Order of freeing matters in general. Here we hold separate pointers to every node, so any order is safe. In a real list you only hold start. Free a node before reading its link and you read freed memory. The correct pattern, shown in a later lecture, is to save the next pointer first.

Array Versus Linked List

FeatureArrayLinked list
SizeFixed at compile time (or at allocation)Grows and shrinks one node at a time
Memory layoutContiguous blockScattered nodes joined by pointers
Access element kInstant: a[k]Walk k links from the start
Insert or delete in the middleShift many elementsChange one or two pointers
Extra memory per elementNoneOne pointer per node
Cache friendlinessExcellentPoor, nodes may be far apart
Typical embedded useLookup tables, buffersQueues, task lists, event chains

Choose honestly

A linked list is not “better” than an array. If you know the size and mostly read by index, an array wins on speed and simplicity. Reach for a list when the count is unpredictable or when records are frequently inserted and removed.

Real-World Uses in Embedded Systems

  • RTOS scheduler. Ready tasks and blocked tasks are kept on lists so the kernel can move a task between them by relinking.
  • Protocol stacks. Network and Bluetooth buffers are chained so a packet can grow header by header without copying.
  • Linux kernel. Its core list type chains device and driver objects. Understanding plain linked lists makes that code readable later.
  • Event queues. Interrupt handlers append events that the main loop removes one by one.

Common Mistakes

  • Forgetting to set the last link to NULL. A garbage link makes your loop run off into random memory.
  • Losing start. Overwriting start before saving it leaves the nodes unreachable and leaked.
  • Not checking malloc. A NULL result dereferenced is an instant crash.
  • Using a node after free(). The memory may be reused by something else.
  • Casting malloc in C. Not needed in C and can hide a missing include. Plain malloc(sizeof *p) is cleaner.

Performance and Safety Notes

  • Each node costs the data plus one pointer, plus allocator overhead. On tiny heaps, overhead can be larger than your data.
  • Repeated allocation and release can fragment a small heap. Many embedded projects use a fixed pool of nodes instead.
  • If an interrupt and the main loop share a list, protect it. A half-finished pointer update seen by an interrupt can corrupt the chain.

Suggested Images for This Lecture

Image ideaALT text
Chain of nodes with start pointerlinked list in C start pointer and nodes free C programming course
Array versus linked list memory layoutarray vs linked list free embedded C course comparison
Terminal output of list_basicfree C tutorial linked list program output embedded C programming

Key Takeaways

  • A node = information part + link part; the last link is NULL.
  • One start pointer is the only way into the list; an empty list is start == NULL.
  • Lists grow node by node and insert without shifting data, but cannot jump to element k directly.
  • Always check malloc() and always free() what you allocate.

Conclusion

You now know what a linked list is, how a node is laid out, and why a single start pointer is enough to control the whole chain. You also have an honest picture of when to choose a list or an array in embedded C programming. In the next lecture of this free C programming course we will put that start pointer to work: walking every node, counting, summing and searching for a value.

Frequently Asked Questions

What is a linked list in C?

A linked list is a sequence of nodes, each holding data and a pointer to the next node, with the last pointer set to NULL.

Why do we need a start pointer?

Nodes are not stored side by side, so the only way to reach the list is through the address of its first node, which the start pointer holds.

How do I know a linked list is empty?

If the start pointer equals NULL, the list has no nodes.

Is a linked list faster than an array?

Not for reading by index; arrays are faster there. Lists are faster for inserting and removing in the middle because no data shifts.

Can I use linked lists without malloc on a microcontroller?

Yes. Link nodes taken from a static array or a fixed pool. The pointer logic is the same.

What happens if I forget to free the nodes?

The memory leaks. On a long-running embedded device this eventually exhausts the heap.

Next in the Free C Programming Course

Traverse the list, count nodes and search for a value.

💬 Need help or career guidance? Ask us!Contact Us →

1 Comment

Leave a Reply

Your email address will not be published. Required fields are marked *

×

🚀 BLE on Linux (BlueZ)

Hands-on course. Only ₹399

Enroll Now →