Posts /

Linked Lists from Scratch

12 mins read ●
Twitter Facebook Google+
17 Sep 2017

I’m very excited today, not only because I’m posting after long but also because I’m posting about an exciting topic. For starters, third semester has started introducing me to an important, Data Structures and Algorithms, course. I had started 100 Algorithms series. I needed a break to settle in, now I’m back with something BIG.
My instructor started this course by introducing us to pointers. This made me think ‘wut?’, but after digging in, I found out that pointers are the most basic building block of Data Structures. So, now I’ll create Linked List data structure from scratch in C using pointers.

Pointers
Pointers are variables that point to some variable using memory addresses. By using pointers we have access to a variable’s memory and value which allows efficient programming with more control over memory management.
Read More: Pointers in C

Linked List

Linked List is a data structure similar to arrays. The difference is that, unlike arrays, linked lists don’t have indices which means we can’t access any arbitrary node from linked list. Instead, we have to traverse through all the nodes, from the head to required node. Nodes are structs which have their own value and a pointer to the next node. This allows dynamic (re)allocation of list on runtime. All these nodes are connected like a chain, where the first node is called the head and the last one is called the tail, which points to nothing.

Linked List  
Linked List Illustration

Why Linked List?

Because of more control over memory, Linked List are used where the data size is not pre-known. Linked List also makes some operations fast because of their structure. Their details are given below:

Operations
Indexing: Θ(n)
Insert/delete at the beginning: Θ(1)
Insert/delete at the end: Θ(n) (when the end is not known)
Insert/delete at the end: Θ(1) (when the end is known)
Indexing: Θ(n)

Linked List in C

I have made a try to implement basic Linked List data structure in C, using pointers. There might be some memory mis-management but I’m glad I’ve been able to do this much. Start a discussion thread () to share your ideas for better memory handling.
Now, let’s start rolling with pointers!

Structure

Linked Lists are composed of nodes. Each node contains its data, and points to the next node as well. So, for dual functionality, a node must be a struct. Here, it is important to typedef the struct as it points to the same kind of structure. Self referencing can be a hectic thing to handle in such situations. I define the Linked List as:

typedef struct node {
    int data; //value in a node
    struct node* next; //pointer to next node
} node;

Now that you can see what each node looks like, let’s go ahead and define basic functions to manipulate these nodes.

Creating a Node

Each node must be created according to the above defined structure to add it to the list. This makes create() the most fundamental function.
This function takes the value to put into the node, and pointer to the next node. On success, it returns a pointer to the node.

node* create(int value, node* next){

    //allocating memory for new node
    node* new_node = (node*)malloc(sizeof(node)); // handle with care

    //exception
    if(new_node == NULL){
        fprintf(stderr, "ERROR: while creating node");
        exit(1); //force terminate
    }

    //filling up
    new_node->data = value;
    new_node->next = next;

    return new_node;
}

After creating a node, we can add it to the front or back of the list; adding the node to list is shown in following functions.

Add Node to Front

This function takes an existing Linked List and adds a new node to its front. It takes a value for node, and pointer to the head of list as parameters. On success, it returns the pointer to the new node which is now the new head.

Note: Head is an important entity here which you need to take care of. If you lose the pointer to head, you lose the whole list!

node* add(int value, node* head){
    //create a new node, which is to be added
    node* new_node = create(value, head);

    //make the new node head
    head = new_node;

    return head;
}

Append a Node

Most of you must be aware of the append operation. It adds a new item at the end of an existing sequence. This append() function will do exactly the same.

Note: When moving pointers to point to different items, make sure to keep track of all the items. With that, you won’t lose a reference to any of the items. Be vigilant in these situation, otherwise you can cause a memory leak.

Here’s my append function:

node* append(int value, node* head){

    node* pointer = head; // pointer to head, which will move forward to point to all nodes 1-by-1

    //keep moving until reach the end
    /*NOTE: I'm making use of the fact that the last node points to nothing!*/
    while(pointer->next != NULL)
        pointer = pointer->next;

    //on reaching the end
    node* new_node = create(value, NULL); //last one points to nothing
    pointer->next = new_node; //attach to end

    return head; //node added at the end, head remains the same
}

I have mentioned above that the Linked List is used as a building block for more complex data structures. The following functions will demonstrate how!

Chop

Like in Queue data structure in which elements are removed from the front only, this function helps to implement the FIFO structure.
As the head is chopped, we ought to select a new head. Carefully set the next node as head to avoid memory leak.

node* chop(node* head){

    if(head == NULL)
        return NULL;

    node* new_head = head->next; //make the next node, the head
    head->next = NULL; //old head points to nothing now
    free(head); //free existing head, chop it!

    return new_head;
}

Pop

Similarly, in a Stack elements are always removed from the back. This makes it a LIFO structure. This pop() function support this idea.

node* pop(node* head){

    if(head == NULL || head->next == NULL) //if list is empty or has only one node
        return NULL;
    node* pointer = head; //a pointer like other functions
    node* prev = NULL; //previous node

    while(pointer->next != NULL){
        //current one becomes previous, a new one comes up
        prev = pointer;
        pointer = pointer->next;
    }
    prev->next = NULL; //making the second last pointer to nothing; aka last node
    free(pointer); //emptying the last node

    return head;//head unchanged
}

Till now, you have witnessed me define some functions for populating Linked List and removing the unwanted items. For interaction with the list, I have these two functions:

Search the List

All the nodes are connected in a chain but only in one direction; ‘There’s no going back!’. We can iterate over all nodes one-by-one to see if any of the nodes has a specific value. search() function takes a value to be search and the list head, and returns 0 for false and 1 for true.

int search(int value, node* head){
    node* pointer = head; //a pointer to point different nodes 1-by-1

    while(pointer != NULL){ //until end is reached
        if(pointer->data == value)
            return 1;
        pointer = pointer->next; //next one up to be checked
    }
    return 0;
}

As all the values are associated with their nodes, printf() can’t print the values from list. This function is inspired from Java’s toString() of Obj Class.

void toString(node* head){
    node* pointer = head;
    printf("[ ");
    while(pointer != NULL){ //until reached the end
        printf("%d ", pointer->data); //display data in the node
        pointer = pointer->next; //move to next node
    }
    printf("]\n");
}

Dump It!

When we are involving memory directly in our program, there’s a lot at stake. It’s a good idea to free the memory if it’s not needed anymore. For this reason, I’ve made this destroy() function which clears each node from memory when the List is not needed.

Note: Most of the memory problems are likely to arise in this phase.

void destroy(node** head){
    node* current = *head;
    node* next = current->next;

    while (next != NULL){
        destroy(&next);
    }
    *head = NULL;
}

All these functions are combined in LinkedList.c.
This implementation of Linked List is tested in this file.

Output

Linked List Test  
Output of LinkedList Test

Play with it and comment below if there’s something about it that you want to discuss.


You may also like...


Twitter Facebook Google+