[CS fundamentals] Linked List Creation & Insertion explained in C.

---

Introduction

In this article, we will look at fundamentals of linked lists. Linked list is a really powerful data structure especially when you deal with insertion and deletion. Imagine an array with 10,000 elements. If you want to insert a single element into that array in its index 5,000, you may need to shift all elements from 5,000 to 10,000 and then insert an element. This is very inefficient and time/memory-consuming. However, when retrieving a value with specific index, array does better job. So, we really need to understand and be able to distinguish between those two. I will be presenting creating a node in Linked List and insertion in this article. We will be covering deletion and reversing (which is more advanced in the next article). Code is written with C in this post. So, let's get started.

---

Creating Linked List

Let's say we have a list where each node contains two elements:

1. data

2. pointer to next node

Then, we have struct that looks like below.

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

In order to create a new node, the first thing we should do is allocating memory space in our heap memory so that our new node fits in there. Heap memory is the memory space where "we" manipulate the data whereas the stack memory is manipulated by the computer.

// Create a new node
static *node create_node(int new_data) {
    // malloc new memory for our new node.
    struct node *new_node = malloc(sizeof(struct node));

    // set the data of our new node as the function's     parameter.
    // let our next point to NULL.
    new_node->data = new_data;
    new_node->next = NULL;

    // return newly created node so that we can use it later.
    return new_node;
}

There are three key steps to create a new node.

• Mallocing (Memory allocation)

  • Note: sizeof(struct node) will give us the exact size that is needed for a single node.

• Initializing the variables of a new node.

• Returning the new node.

---

Traversing Linked List

In order to do something with the array, it is so important to master how we traverse 1D/2D arrays to get/delete the elements. For array, we traverse it using index and loops (eg. while/for).

In linked list, where insertion and deletion is powerful, it is so important to master traversing. However, it is often more complicated compared to array because we have to deal with NULL values, and we also do not want to lose the head of the linked list.

This is the procedure we can use to traverse linked lists.

1. Check if the head is NULL so that we can prevent NULL->next.

2. We never want to lose our head, so we create a new variable called current and assign our head.

3. We want to loop until current is NULL because current = NULL means we have reached the end.

4. current = current->next is equivalent to i++ in for loop. This allows you to move to the next node of the list.

// Given a head, traverse linked list.
// We are using the same struct we defined in the previous section.

void traverse_linked_list(struct node *head) {
    if (head == NULL) {
        // Pass it.
        ;
    } else {
        // We don't want to lose our head.
        // Make sure to create a copy, conventionally, current.
        struct node *current = head;

        while (current != NULL) {
            // do something here.

            // Move to the next element. 
            current = current->next;
        }
    }
}

---

Insertion (Head, nth Position, Tail)

Now, more complicated things coming up. We will look into insertion. There are so many different circumstances where we can be given about where to insert, but mainly, we will look at three situations.

1. Head

2. Nth position (this n will be given as a parameter)

3. Tail

Head Insertion:

struct node *insert_head(struct node *head, int new_data) {
    // Create a new node to insert
    struct node *new_node = create_node(new_data);

    // If head is NULL, set our new node as head.
    if (head == NULL) {
        head = new_node;
        return head;
    } else {
        // Else, let the head point to our new node so that it can be the head now.
        new_node->next = head;
        head = new_node;
        return head;
    }
}

There are a few things to notice here. Since we want to insert a new node, call create_node function and assign its return value to new_node.

Now, as we want to insert a new node in the head (very first) of our list, if head is NULL, we can just set the new node as our head.

If head is not NULL we enter else statement and do the following:

• ** Suppose that we have a list 2-3-4, and we want to insert 1 in the head.

• Set new_node's next as current head.

  • new_node->next = head will attach new_node to the very first element, which is 2, so we obtain 1-2-3-4.

  • But, our head is still 2, which is now the second element of the list, so set head as new_node.

Tail Insertion:

struct node *insert_tail(struct node *head, int new_data) {
    struct node *new_node = create_node(new_data);
    
    if (head == NULL) {
        head = new_node;
        return head;
    } else {
        struct node *current = head;

        // Loop until we reach the last node.
        while (current->next != NULL) {
            current = current->next;
        }

        // Current is at the last node, so we can insert here!
        current->next = new_node;
        return head;
    }
}

The difference here is that now we traverse the list to get to the last node because we want to insert in the tail. Let's visualize this.

Suppose that we have 1 - 2 - 3 in our list, and our new_node is holding a value of 4. So, at the end, we want 1 - 2 - 3 - 4. To do this, we go to 3, and insert 4 after 3.

It is important to note that we are using current->next != NULL, not current != NULL because the latter will loop until the very end, which means it results in NULL->next. This is a technique that is used for deletion and insertion in nth node as well.

As long as we have reached to the end, it is easy. We just make our last node point to the node new, so basically making 3 pointing to 4, so we obtain 1 - 2 - 3 - 4.

Nth Insertion

struct node *insert_nth(struct node *head, int new_data, int n) {
    struct node *new_node = create_node(new_data);

    // If n is 0 or head is NULL, we can insert in head.
    if (n == 0 || head == NULL) {
        new_node->next = head;
        return new_node; 
    }

    // Else, set current and count.
    // count is initialized here so that we can know when to stop looping.
    struct node *current = head;
    int count = 0;

    // While loop will stop in either condition
    // 1. current-> next == NULL
    // 2. count >= n - 1
    while (current->next != NULL && count < n - 1) {
        count++;
        current = current->next;
    }
    
    // Insert after current node.
    new_node->next = current->next;
    current->next = new_node;

    return head;
}

It seems like so many things are going on, so let's look at each step individually.

1. Create node (just like we did before)

2. We first want to check if we want to insert in head. If yes, do it and end the program by returning.

3. Now, we have reached the point where we want to loop until the desired position n - 1. We can do this by setting a count variable that keeps track of where we are, and compare it by count < n - 1.

4. After looping, the loop was finished because of one of the two conditions. Either current->next == NULL or count >= n - 1. However, we don't really need to care about it here because

   new_node->next = current->next;
   current->next = new_node;
   

will do the job for you. So, what is going on with the above code?

1. If the loop ended due to current->next == NULL, then new_node->next becomes NULL, and current->next will point to the new_node, so this is the same as tail insertion.

2. Assume that we have 1 - 2 - 4 - 5, and we want new_node = 3 to be inserted between 2 and 4. Then, we move to current = 2, and we also have current->next = 4. Now, new node's next is 4, and current's next is new node, this allows us to obtain 1 - 2 - 3 - 4 - 5.