Linked list

C

src/c/data-structure/linked-list.c

#include <stdio.h>  // printf
#include <stdlib.h> // malloc
#include <string.h> // strcpy, strcmp
#include <assert.h> // assert

typedef struct todo_list
{
    char item_name[100];
    int number_of_item;
    int is_important; // no boolean type in C, use 0/1 for false/true
    struct todo_list *next;
} todo_list;

todo_list *create_new_item(char item_name[], int number_of_item, int is_important)
{
    todo_list *list;
    list = malloc(sizeof(todo_list));
    assert(list);
    strcpy(list->item_name, item_name);
    list->number_of_item = number_of_item;
    list->is_important = is_important;
    list->next = NULL;
    return list;
}

void print_item(todo_list *list)
{
    if (list == NULL)
    {
        return;
    }
    else
    {
        printf("Item name: %s\n", list->item_name);
        printf("Number of items: %d\n", list->number_of_item);

        if (list->is_important == 0)
        {
            printf("Is important: false\n");
        }
        else
        {
            printf("Is important: true\n");
        }
    }
}

void print_list(todo_list *list)
{
    if (list == NULL)
    {
        return;
    }
    else
    {
        print_item(list);

        if (list->next == NULL)
        {
            return;
        }
        else
        {
            printf("\n");
            print_list(list->next);
        }
    }
}

void insert_head(todo_list **list, todo_list *todo_item)
{
    todo_item->next = *list;
    *list = todo_item;
}

todo_list *search_list(todo_list *list, char item_name[])
// returns pointer to the todo item
{
    if (list == NULL)
    {
        return NULL;
    }

    if (strcmp(list->item_name, item_name) == 0)
    {
        return list;
    }
    else
    {
        return search_list(list->next, item_name);
        // if program arrives here it must return
    }
}

todo_list *item_ahead(todo_list *list, char item_name[])
{
    if ((list == NULL) || (list->next == NULL))
    {
        return (NULL);
    }

    if (strcmp(list->item_name, item_name) == 0)
    {
        return (list->next);
    }
    else
    {
        return (item_ahead(list->next, item_name));
    }
}

void delete_head(todo_list **list)
{
    if ((*list) != NULL)
    {
        todo_list *head;
        head = (*list)->next;
        free(*list);
        *list = head;
    }
}

void delete_list(todo_list **list)
{
    while ((*list) != NULL)
    {
        delete_head(list);
    }
}

int main()
{
    todo_list *my_list = create_new_item("bread", 2, 0);
    todo_list *milk = create_new_item("milk", 3, 1);
    insert_head(&my_list, milk);

    print_list(my_list);

    // search
    char item[] = "bread";
    todo_list *my_item = search_list(my_list, item);

    if (my_item == NULL)
    {
        printf("\n%s is not included in my list.\n", item);
    }
    else
    {
        printf("\n%s is included in my list.\n", item);
    }

    // item ahead
    todo_list *next_item;
    next_item = item_ahead(my_list, "milk");
    printf("next time: %s\n", next_item->item_name);

    printf("\n+++ Delete head +++\n");
    delete_head(&my_list);
    print_list(my_list);

    printf("\n+++ Insert milk again +++\n");
    milk = create_new_item("milk", 5, 0);
    insert_head(&my_list, milk);
    print_list(my_list);

    printf("\n+++ Delete all +++\n");
    delete_list(&my_list);
    print_list(my_list);

    return 0;
}

C++

src/cpp/data-structure/linked-list.cpp

// linked lists are dynamic collection
// adding new item has O(1) complexity, while searching items in the list has
// O(N) cost. In comparison, inserting item in a regular array is O(N) while
// array search is O(1). If we use dynamic array instead of static array, we
// start with a specific size of the array, once we run out of space, we
// allocate a new array with double the previous size of array. We copy the
// first half of the array from previous array, and add the new element. In this
// we need to double about log(N) time for N item, so half of the item is copied
// once, quarter of item is moved twice, and so on, we will see that this is
// still a O(N) complexity to build such array.
// linked lists are used where the array size is not known compile time, and
// we do not need random access to the items in it.
// Use cases: list of navigational nodes (going from one point to another in a
// map), list of items in a shopping cart

#include <iostream>
#include <string>
using namespace std;

// this is the data structure we are going to store in our list
struct LinkedList
{
    string item_name;
    int number_of_item;
    LinkedList *next;
};

// inserting new element to the head i.e., the new element becomes head
void add_to_head(LinkedList *&head, string new_item_name, int new_number_of_item)
{
    LinkedList *new_ptr;
    new_ptr = new LinkedList;
    new_ptr->item_name = new_item_name;
    new_ptr->number_of_item = new_number_of_item;
    new_ptr->next = head;

    head = new_ptr;
}

void print_linked_list(LinkedList *head)
{
    LinkedList *ref_ptr = head;
    cout << "List items: \n";

    while (true)
    {
        cout << ref_ptr->item_name << " (" << ref_ptr->number_of_item << " pcs.)"
             << endl;
        ref_ptr = ref_ptr->next;

        if (!ref_ptr)
        {
            break;
        }
    }
}

int length_linked_list(LinkedList *head)
{
    int len = 0;
    LinkedList *ref_ptr = head;

    while (true)
    {
        len += 1;
        ref_ptr = ref_ptr->next;

        if (!ref_ptr)
        {
            break;
        }
    }

    return len;
}

void delete_head(LinkedList *&head)
// in order to delete and modify pointer we need pass by reference
{
    if (head)
    {
        LinkedList *tmp_ptr;
        tmp_ptr = head->next;
        delete head;
        head = tmp_ptr;
    }
}

int main()
{
    // let's define our head pointer first
    // head pointer points to the first element of the linked list
    // head pointer also used to refer to the linked list as a whole
    LinkedList *head;
    head = new LinkedList;
    // assign the first element of the linked list
    // two ways of accessing struct members via pointer dereferencing
    head->item_name = "bread"; // (*head).item_name = "bread";
    head->number_of_item = 3;
    // if our list has only one item, the next pointer points to NULL
    // in case the head pointer points to nullptr, the list is empty
    // head = nullptr; // refers to empty linked list
    head->next = nullptr;

    cout << "Length of list = " << length_linked_list(head) << endl;

    // let's add new item to the head
    add_to_head(head, "water bottle", 5);

    print_linked_list(head);

    // add another item and print
    add_to_head(head, "tissue roll", 2);
    print_linked_list(head);
    cout << "Length of list = " << length_linked_list(head) << endl;

    delete_head(head);
    print_linked_list(head);

    return 0;
}