What are Insert Nodes in Linked Lists- Embedded C Programming Training In Hyderabad

🚀 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 30

Insert Nodes in Linked Lists

Create nodes with malloc and insert them at the beginning, at the end or after a chosen node. Includes a quiz and interview questions. Free C tutorial for embedded C programming.

So far you have built lists by hand and walked them. Real programs need to insert a node in a linked list in C while they run: a new packet arrives, a new device connects, a new task is created. This lecture of our free C programming course and free embedded C course shows the three standard insertions, step by step, with a program you can compile, and finishes with a quiz and interview questions you can use to test yourself.

What You Will Learn

  • How to allocate and initialise a new node safely
  • Insertion at the beginning of a list
  • Insertion at the end of a list
  • Insertion after a node holding a given value
  • The correct order of pointer updates, and why order matters
  • How to free a whole list without reading freed memory
  • A quiz and interview questions on linked lists

Prerequisites

You need the node structure, the start pointer, traversal and malloc() and free(). Lectures 27 to 29 of this free C tutorial cover them.

Step Zero: Make a Node

Every insertion starts the same way: ask the heap for one node, put the data in it, and set its link to NULL so it never carries a garbage pointer. We put this in one function so the three insert functions can share it.

static struct node *new_node(int data)
{
    struct node *tmp = malloc(sizeof *tmp);

    if (tmp != NULL) {
        tmp->info = data;
        tmp->link = NULL;
    }
    return tmp;
}

The function returns NULL if the heap is exhausted, and callers must deal with that. On an embedded device with a few kilobytes of heap this is not a theoretical case.

Insertion at the Beginning

This is the simplest and fastest insertion because it does not need to walk the list. Two steps:

  1. Make the new node’s link point to the current first node (the old start).
  2. Make start point to the new node.
static struct node *insert_begin(struct node *start, int data)
{
    struct node *tmp = new_node(data);

    if (tmp == NULL)
        return start;
    tmp->link = start;
    return tmp;
}
Insert 10 at the beginning
beforestart→20→NULL
step 1: new.link = start10→20
step 2: start = newstart→10→20→NULL
Why return the new start? The function receives a copy of the caller’s start. Changing the copy would not update the caller. Returning the new head and letting the caller write start = insert_begin(start, 10); is the simplest correct approach. The same code works for an empty list: start is NULL, so the new node’s link becomes NULL.

Insertion at the End

To append, we must find the last node, which is the one whose link is NULL. Then we point that link at the new node. An empty list is a special case: there is no last node, so the new node simply becomes the head.

static struct node *insert_end(struct node *start, int data)
{
    struct node *tmp = new_node(data);
    struct node *p;

    if (tmp == NULL)
        return start;
    if (start == NULL)
        return tmp;
    for (p = start; p->link != NULL; p = p->link)
        ;
    p->link = tmp;
    return start;
}
Append 40 at the end
walk until p.link is NULL10→20(p here)
p.link = new node10→20→40→NULL

Note the loop condition: p->link != NULL, not p != NULL. We want to stop on the last node, not after it. This is one of the few places where looking one node ahead is exactly right.

Insertion After a Given Node

Here we find the node holding a key, then splice the new node in right after it. The order of the two pointer updates is critical.

static int insert_after(struct node *start, int key, int data)
{
    struct node *p = start;
    struct node *tmp;

    while (p != NULL && p->info != key)
        p = p->link;
    if (p == NULL)
        return -1;
    tmp = new_node(data);
    if (tmp == NULL)
        return -1;
    tmp->link = p->link;   /* 1: new node takes over the rest of the list */
    p->link = tmp;         /* 2: key node now points to the new node */
    return 0;
}

The order rule

Always connect the new node to the rest of the list first, then connect the earlier node to the new node. If you do it the other way round, p->link = tmp overwrites the only pointer that remembered the rest of the list, and everything after p is lost and leaked.

Insert 30 after the node holding 20
before10→20→40→NULL
1: new.link = 20.link30→40
2: 20.link = new10→20→30→40→NULL

Freeing the Whole List

When you are done, release every node. The trap is reading p->link after free(p). Save the next pointer first.

static void list_free(struct node *p)
{
    struct node *next;

    while (p != NULL) {
        next = p->link;   /* save before freeing */
        free(p);
        p = next;
    }
}

Complete Program: Build and Run

Save the following as list_insert.c.

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

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

static struct node *new_node(int data)
{
    struct node *tmp = malloc(sizeof *tmp);
    if (tmp != NULL) { tmp->info = data; tmp->link = NULL; }
    return tmp;
}

static struct node *insert_begin(struct node *start, int data)
{
    struct node *tmp = new_node(data);
    if (tmp == NULL) return start;
    tmp->link = start;
    return tmp;
}

static struct node *insert_end(struct node *start, int data)
{
    struct node *tmp = new_node(data);
    struct node *p;
    if (tmp == NULL) return start;
    if (start == NULL) return tmp;
    for (p = start; p->link != NULL; p = p->link)
        ;
    p->link = tmp;
    return start;
}

static int insert_after(struct node *start, int key, int data)
{
    struct node *p = start;
    struct node *tmp;
    while (p != NULL && p->info != key)
        p = p->link;
    if (p == NULL) return -1;
    tmp = new_node(data);
    if (tmp == NULL) return -1;
    tmp->link = p->link;
    p->link = tmp;
    return 0;
}

static void list_print(const struct node *p)
{
    for (; p != NULL; p = p->link)
        printf("%d -> ", p->info);
    printf("NULL\n");
}

static void list_free(struct node *p)
{
    struct node *next;
    while (p != NULL) { next = p->link; free(p); p = next; }
}

int main(void)
{
    struct node *start = NULL;

    start = insert_begin(start, 20);
    list_print(start);
    start = insert_begin(start, 10);
    list_print(start);
    start = insert_end(start, 40);
    list_print(start);

    if (insert_after(start, 20, 30) == 0)
        list_print(start);

    if (insert_after(start, 99, 1) != 0)
        printf("key 99 not in list, nothing inserted\n");

    list_free(start);
    return 0;
}
$ gcc -Wall -Wextra -fsanitize=address,undefined -g -o list_insert list_insert.c
$ ./list_insert

Expected output:

20 -> NULL
10 -> 20 -> NULL
10 -> 20 -> 40 -> NULL
10 -> 20 -> 30 -> 40 -> NULL
key 99 not in list, nothing inserted

Compiling with -fsanitize=address makes the program report leaks and invalid memory use. Our program frees everything, so it runs silently. Try removing the list_free() call and watch the leak report appear. It is a free, powerful teacher.

Comparing the Three Insertions

InsertionNeeds traversal?Changes start?Special case
At beginningNoYes, alwaysnone, works for empty list
At endYes, to last nodeOnly if list was emptyempty list
After a keyYes, to find keyNokey not found

Common Mistakes

  • Wrong pointer order in insert-after, which loses the tail of the list.
  • Not handling the empty list in insert-at-end, causing a NULL dereference.
  • Ignoring a failed malloc and then writing through NULL.
  • Forgetting to return or update start after inserting at the beginning, so the caller never sees the new node.
  • Reading a node after free(). Save the next pointer first.
  • Memory leaks from never freeing the list on exit paths.

Best Practices, Performance and Safety

  • Insert at the beginning when order does not matter: it takes constant time.
  • Keep a second tail pointer if you append often; then append no longer needs a walk.
  • On systems that forbid heap use, take nodes from a static pool and keep a free list.
  • Protect lists shared between an interrupt and the main loop with a critical section.
  • Test with sanitizers on a PC before moving the code to the target.

Quiz: Test Yourself

Try each question first, then open the answer.

Multiple Choice

Q1. What does the link part of the last node of a singly linked list contain?

A) 0 as an integer, B) the address of the first node, C) NULL, D) garbage. Answer: C. NULL marks the end of the list.

Q2. A list is empty when:

A) start->link is NULL, B) start is NULL, C) count is 1, D) start is 0 bytes. Answer: B. With no nodes there is nothing for start to point to.

Q3. Which insertion never needs to walk the list?

A) at the end, B) after a key, C) at the beginning, D) before the last node. Answer: C.

Q4. In insert-after, which line must run first?

A) p->link = tmp, B) tmp->link = p->link, C) free(p), D) start = tmp. Answer: B. Otherwise the rest of the list is lost.

Q5. Why does the loop in insert_end test p->link != NULL?

A) to skip the first node, B) to stop on the last node instead of after it, C) to count nodes, D) it is a mistake. Answer: B.

Q6. What is wrong with this code: free(p); p = p->link;

A) nothing, B) it reads a node after freeing it, C) it leaks memory, D) it frees twice. Answer: B. Save the next pointer before freeing.

Output Prediction

Q7. What does this print? start = insert_begin(start, 1); start = insert_begin(start, 2); start = insert_begin(start, 3); list_print(start); (start begins as NULL)

Answer: 3 -> 2 -> 1 -> NULL. Each new value goes in front, so the list is reversed relative to the insertion order.

Q8. What does this print? start = insert_end(start, 1); start = insert_end(start, 2); start = insert_end(start, 3); list_print(start);

Answer: 1 -> 2 -> 3 -> NULL. Appending preserves insertion order.

Programming Challenges

  • Write list_free() from memory and test it with the sanitizer build.
  • Write insert_before(start, key, data). Hint: you will need to remember the node before the match, or special-case the first node.
  • Add a tail pointer so that appending takes constant time.
  • Write a function that returns the largest value in the list, and returns an error indicator for an empty list.

Interview Questions on Linked Lists

1. What is a linked list and why use it instead of an array?

A linked list is a chain of nodes joined by pointers. Use it when the number of items is unknown or changes, and when inserting or removing in the middle is common, since no elements need to shift.

2. What is a self referential structure?

A structure containing a pointer to its own type. It cannot contain itself directly because its size would be infinite, but a pointer has a fixed size.

3. How do you detect an empty list?

Check whether the head pointer is NULL.

4. Why do insert functions often return the head pointer?

Because C passes pointers by value. A function cannot change the caller’s head variable unless you return the new head or pass the address of the head pointer.

5. What is the time complexity of inserting at the head, and at the tail?

Head insertion is constant time. Tail insertion is linear without a tail pointer and constant with one.

6. How do you free a linked list correctly?

Loop through it, save the next pointer, free the current node, then move to the saved pointer.

7. What are the disadvantages of a linked list?

No direct indexing, extra memory for pointers, poor cache behaviour, and the risk of leaks and dangling pointers.

8. How would you use linked lists in a system with no malloc?

Preallocate a static array of nodes and manage a free list of unused ones. Linking and unlinking work exactly as with heap nodes.

9. How can you detect a loop in a linked list?

Use two pointers, one moving one step and the other two steps. If they ever meet, the list has a cycle.

10. What bugs appear when an interrupt and main code share a list?

A half-completed pointer update can be seen by the other context, corrupting the chain. Protect updates with a critical section or lock.

Suggested Images for This Lecture

Image ideaALT text
Two-step pointer diagram for head insertioninsert node in linked list in C at beginning free C programming course
Before and after splice for insert after a keylinked list insertion pointer order free C tutorial embedded C programming
Sanitizer terminal output with no leaksfree embedded C course linked list malloc free address sanitizer output
Interview question checklistlinked list interview questions embedded C free C programming course

Key Takeaways

  • Create nodes with a helper that checks malloc() and sets link to NULL.
  • Head insertion: link the new node to the old head, then move the head.
  • Tail insertion: walk to the last node; handle the empty list separately.
  • Insert after a key: connect the new node to the tail first, then connect the key node to it.
  • Free a list by saving the next pointer before each free().

Conclusion

You can now build a linked list that grows while your program runs, which is a big step in embedded C programming. The three insertions you practised are the same moves used inside RTOS kernels, protocol stacks and driver queues. Deleting nodes, reversing a list and building a list from user input are the natural next steps, and they follow the same careful habit: decide the pointer order, test for NULL, and free what you allocate. Thank you for following this free C programming course. Keep practising with the challenges above, and continue with the next lecture when you are ready.

Frequently Asked Questions

How do I insert a node at the beginning of a linked list in C?

Allocate the node, set its link to the current head, and make the head point to the new node.

Why must I handle the empty list when inserting at the end?

An empty list has no last node to attach to, so the new node itself must become the head.

What is the correct pointer order when inserting after a node?

Set the new node’s link to the target node’s link first, then set the target node’s link to the new node.

How do I avoid memory leaks with linked lists?

Free every node you allocate, saving the next pointer before each free, and use a sanitizer or Valgrind during testing.

Can insertion fail?

Yes. malloc can return NULL when the heap is exhausted, so always check the result.

Is this part of a free embedded systems course?

Yes. It is part of the EmbeddedPathashala free C programming course, written for students learning embedded C.

Keep Learning With the Free C Programming Course

Practise the challenges, then continue to deleting nodes and reversing lists.

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

2 Comments

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 →