60% OFF ON EVERYTHING! | get full lifetime access now
Ends in: ...
Creating A Linked List In C
Low Level Programming

Creating A Linked List In C

A linked list is a linear collection of data elements, or rather a sequence of nodes each pointing to the next. Linked lists are invaluable in applications in which you need to process an unknown number of data items, you could be getting input from the user, and you wouldn't know upfront how many items the user is going to type in. Unlike conventional arrays, linked lists are dynamic, they can increase or decrease as desired. The only limiting factor is the amount of memory installed on the running machine.

Linked lists are among the simplest and most common data structures. Implementing a linked list is a skill that aspiring computer programmers must acquire. Am not going to stress the importance, but i know you already have gotten something from everything already said. There is just in some situation where conventional arrays would not work, for they are fixed, once defined, they can't grow or shrink, that's where linked lists come in.  

This article shows how to implement our own linked list data structure. Basic assumptions are, you already know The C Programming Language, because the code is written in C. Implementing a linked list is simple, all you have to do first is define a C structure with 2 items, the data the node holds, and a pointer to the next node.

After a node is defined, we can chain them together to create a sequence, for each node points to the next. That sequence of nodes is what creates a linked list with the last node being null marking the end of the list.

The first thing in creating a list, it will be empty initially, then it will need to be populated with data. Once we add the data, other operations follow, searching the list for an item, removing an item from the list, calculating the number of items contained in the list, and lastly, freeing up space used by the list to prevent memory leak. All the algorithms are easy to follow, but if not, and it's your first time, do not despair, i will leave a link to a C data structure and algorithms course down below.

The simple implementation of a linked list is as follows:

#include <stdio.h>

#include <stdlib.h> /* for malloc */


/* error values */

#define UNINITIALIZED_LIST - 999

#define INDEX_OUT_OF_BOUNDS - 888

/* typedef is for preventing the need for using 'struct list_node' on every declaration of list_node, but, just 'list_node' instead. Not strictly required but looks cleaner */

typedef struct list_node

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

list_node * list_create() /* create empty list */

{

    list_node * list = (list_node * ) malloc(sizeof(list_node));

    list -> next = NULL;

    return list;

}

void list_add(list_node * list, int item) /* add item to list */

{

    if (list == NULL)

        return;

    list_node * current = list;

    /* skipping over non empty slots */

    while (current -> next != NULL) current = current -> next;

    current -> data = item;

    current -> next = (list_node * ) malloc(sizeof(list_node));

    current = current -> next;

    current -> next = NULL; /* mark end of list */

}

int list_length(list_node * list) /* getting list length */

{

    if (list == NULL)

        return -1;

    list_node * current = list;

    int count = 0;

    while (current -> next != NULL)

    {

        ++count;

        current = current -> next;

    }

    return count;

}

int list_get(list_node * list, int index) /* getting item at specified position */

{

    if (list == NULL)

        return UNINITIALIZED_LIST; /* error, querying an uninitialized list */

    int len = list_length(list);

    if (index < 0 || index >= len)

        return INDEX_OUT_OF_BOUNDS; /* index out of bounds error */

    list_node * current = list;

    while (index > 0)

    {

        --index;

        current = current -> next;

    }

    return current -> data;

}

int list_contains(list_node * list,
    const int item) /* searching for an item within a list */

{

    if (list == NULL)

        return -1;

    int i = 0;

    int len = list_length(list);

    for (; i < len; ++i)

    {

        if (list_get(list, i) == item)

            return i;

    }

    return -1;

}

int list_remove(list_node * list,
    const int item) /* removing an item from the list */

{

    if (list == NULL || list_contains(list, item) < 0)
        return -1;

    list_node * current = list;
    list_node * prev = current;
    while (current -> data != item) {
        prev = current;
        current = current -> next;
    }
    prev -> next = current -> next;
    free(current);
    current = NULL;
    return item;
}

void list_destroy(list_node * list) /* freeing up space */ {

    if (list == NULL)
        return;

    list_node * prev = NULL;
    while (list != NULL) {
        prev = list;
        list = list -> next;
        free(prev);
        prev = NULL;
    }

}

int main() {

    int len = 0; /* holds length of the list */
    int i = 0; /* loop variable */
    int item = 0; /* data item to search for in the list */
    int item_index = 0; /* index at which item is stored */

    list_node * list = list_create(); /* create list */

    /* adding items to the list */
    list_add(list, 100);
    list_add(list, 200);
    list_add(list, 300);
    list_add(list, 400);
    list_add(list, 500);
    list_add(list, 600);
    list_add(list, 700);
    list_add(list, 800);
    list_add(list, 900);
    list_add(list, 1000);

    /* get the number of elements in the list before deletion */
    len = list_length(list);

    /* printing list elements before deletion */

    puts("Elements before deletion:");

    for (i = 0; i < len; ++i)

        printf("%d\r\n", list_get(list, i));

    /* expected output: 10 */

    printf("Length before deletion: %d\r\n", len);

    /* delete 2 items from the list */

    list_remove(list, 300);
    list_remove(list, 700);

    /* get the number of elements in the list after deletion */

    len = list_length(list);

    /* printing list elements after deletion */

    puts("\r\n\r\nElements after deletion:");

    for (i = 0; i < len; ++i)

        printf("%d\r\n", list_get(list, i));

    /* expected output: 8 */

    printf("Length after deletion: %d\r\n\r\n", len);

    /* searching for an item in the list */

    item = 900;

    if ((item_index = list_contains(list, item)) >= 0)

    {
        /* contains returns the index at which the item is stored if present */

        printf("%d found at index %d\r\n", item, item_index);

    }

    /* free up memory used by the list, preventing memory leak... */

    list_destroy(list);

    return 0;

}

That's it. If you are interested, and have liked what you have seen, you can learn more here:

https://dragonzap.com/course/c-programming-in-windows

https://dragonzap.com/course/data-structures-in-c

 

 

  • Share

Previous Post

Creating A X86 Bootloader From Scratch

Comments

No Profile Photo

Edward

Very good article


Leave a comment