After arrays, the second most popular data structure is Linked List. A linked list is a linear data structure, made of a chain of nodes in which each node contains a value and a pointer to the next node in the chain. In this article, let’s see how to implement a linked list in C.

What is Linked List in C?

A Linked List is a linear data structure. Every linked list has two parts, the data section and the address section that holds the address of the next element in the list, which is called a node.

The size of the linked list is not fixed, and data items can be added at any locations in the list. The disadvantage is that to get to a node, we must traverse to all the way from the first node to the node that we require. The Linked List is like an array but unlike an array, it is not stored sequentially in the memory.

Memory Representation of Linked List

Let's say we assign values to each node

head->data = 10;
middle->data = 20;
last->data = 30;

Below is the image of memory of the linked list

Why Linked List?

Arrays can be used to store linear data of similar types, but arrays have the following limitations.

1. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.

2. Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted but in Linked list if we have the head node then we can traverse to any node through it and insert new node at the required position.

Advantages over arrays

1. Dynamic size
2. Ease of insertion/deletion

Representation in Linked List

A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then the value of the head points to NULL. Each node in a list consists of at least two parts:

1. data (we can store integer, strings or any type of data).
2. Pointer (Or Reference) to the next node (connects one node to another)

Uses of Linked List

1. The list is not required to be contiguously present in the memory. The node can reside any where in the memory and linked together to make a list. This achieves optimized utilization of space.

2. list size is limited to the memory size and doesn't need to be declared in advance.

3. Empty node can not be present in the linked list.

4. We can store values of primitive types or objects in the singly linked list.

Operations of Linked List

Iterating over a list

Let's build a function that prints out all the items of a list. To do this, we need to use a current pointer that will keep track of the node we are currently printing. After printing the value of the node, we set the current pointer to the next node, and print again, until we've reached the end of the list (the next node is NULL).

void print_list(node_t * head) {
    node_t * current = head;

    while (current != NULL) {
        printf("%d\n", current->val);
        current = current->next;
    }
}

Adding an item to the end of the list

To iterate over all the members of the linked list, we use a pointer called current. We set it to start from the head and then in each step, we advance the pointer to the next item in the list, until we reach the last item.

void push(node_t * head, int val) {
    node_t * current = head;
    while (current->next != NULL) {
        current = current->next;
    }

    /* now we can add a new variable */
    current->next = (node_t *) malloc(sizeof(node_t));
    current->next->val = val;
    current->next->next = NULL;
}

Adding an item to the beginning of the list (pushing to the list)

To add to the beginning of the list, we will need to do the following:
1. Create a new item and set its value
2. Link the new item to point to the head of the list
3. Set the head of the list to be our new item

This will effectively create a new head to the list with a new value, and keep the rest of the list linked to it.
Since we use a function to do this operation, we want to be able to modify the head variable. To do this, we must pass a pointer to the pointer variable (a double pointer) so we will be able to modify the pointer itself.

void push(node_t ** head, int val) {
    node_t * new_node;
    new_node = (node_t *) malloc(sizeof(node_t));

    new_node->val = val;
    new_node->next = *head;
    *head = new_node;
}

Removing the first item (popping from the list)

To pop a variable, we will need to reverse this action:
1. Take the next item that the head points to and save it
2. Free the head item
3. Set the head to be the next item that we've stored on the side

int pop(node_t ** head) {
    int retval = -1;
    node_t * next_node = NULL;

    if (*head == NULL) {
        return -1;
    }

    next_node = (*head)->next;
    retval = (*head)->val;
    free(*head);
    *head = next_node;

    return retval;
}

Time & Space Complexity Analysis

Space Complexity: The Space Complexity of the above Linked List operations is O(1). This is because we do not need extra space beyond a fixed number of variables. For some operations, you may need extra space of the order of O(N). For example, sorting a Linked List using a sorting algorithm that is not in-place.

With this article at Logicmojo, you must have the complete idea of analyzing Linked List and it's operations.

Good Luck & Happy Learning!!