Linked lists in C

A linked list is a custom data structure which can be created in C and other programming languages, designed for lists which may need to have elements added or removed from them at runtime, without knowing how big the list will need to be when it is initialised. A linked list is similar to an array, but has some important differences:

When an array is initialised, the size of the array must be declared, and all of the memory for the array is allocated with a single command. With a linked list, memory is allocated/freed dynamically every time a new element is added or removed from the list
Once an array is created, there is no safe and efficient way of adding or removing elements from the array, whereas a linked list is designed to have elements added and removed at runtime
When an array is created, all the memory is allocated in a single command, and the memory addresses for each element are created next to each other, making it easy to access the element at any position in the list in constant time using pointer arithmetic (see my Gist about pointers). With a linked list, memory for each element can be allocated anywhere on the heap, and to access the element at any position in the list, it is necessary to follow the links from each element in the list in order (see example below), requiring time complexity which is linear in the index which is being accessed

In practise, a linked list in C is implemented using a struct which contains a pointer to a different struct of the same type (IE the next element in the list), and new elements are added to the list at runtime using malloc ("Memory ALLOCate"), and released using free. Below is a minimal(ish) example of linked lists in C, showing how to define the struct, and write functions to create new elements (including allocating dynamic memory on the heap), retrieve an element at a particular position, iterate through each element and displays its contents, iterate through each element releasing its memory, and write a main function which parses inputs from stdin (which in this case has been redirected from a text file floyd.txt) and stores each string as part of an element in the linked list.

`linkedlist.c`

/* Compile and run using:
gcc linkedlist.c -o linkedlist && linkedlist < floyd.txt
*/

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

const int MAX_STR_SIZE = 64;

typedef struct elem {
    char* text;
    struct elem* next;
} elem;

elem* create(char* buffer) {
    elem* new_elem = (elem*) malloc(sizeof(elem));
    new_elem->text = (char*) malloc(sizeof(char) * (strlen(buffer) + 1));
    strcpy(new_elem->text, buffer);
    new_elem->next = NULL;
    return new_elem;
}

elem* get_elem(elem* start, int idx) {
    elem* e = start;
    for (int i = 0; i < idx; i++) e = e->next;
    return e;
}

void display_all(elem* e) {
    int i = 1;
    while (e != NULL) {
        printf("%i. %s\n", i, e->text);
        e = e->next;
        i++;
    }
}

void release(elem* start) {
    elem *current = start, *next;
    
    while (current != NULL) {
        next = current->next; // store pointer to next element
        free(current->text); // release the memory used for the string
        free(current); // release the memory used for the struct
        current = next; // next iteration, release the next element
    }
}

int main() {

    char buffer[MAX_STR_SIZE];
    elem *start = NULL, *prev_elem = NULL, *new_elem;

    while(fgets(buffer, MAX_STR_SIZE, stdin) != NULL) {
        buffer[strcspn(buffer, "\n")] = '\0'; // remove newline
        new_elem = create(buffer); // create new element
        if (start == NULL) start = new_elem; // first iteration
        if (prev_elem != NULL) prev_elem->next = new_elem; // subsequent ones
        prev_elem = new_elem; // store pointer to previous element
    }

    display_all(start);
    printf("\nlist[5] = %s\n", get_elem(start, 5)->text);
    release(start);
}

`floyd.txt`

Speak To Me
Breathe
On The Run
Time
The Great Gig In The Sky
Money
Us And Them
Any Colour You Like
Brain Damage
Eclipse

Console output

>gcc linkedlist.c -o linkedlist && linkedlist < floyd.txt
1. Speak To Me
2. Breathe
3. On The Run
4. Time
5. The Great Gig In The Sky
6. Money
7. Us And Them
8. Any Colour You Like
9. Brain Damage
10. Eclipse

jakelevi1996/Linked lists in C.md

Select an option