Linked Lists

Finding a Node

When finding an element, a linked list cannot locate it quickly by index as an array can. It can only start from the head and inspect nodes one by one.

Data in a linked list can only be accessed sequentially, with a worst-case time complexity of $O(n)$.

T singly_linked_list_get(singly_linked_list_t *list, int index) {
    if (list == NULL) {
        exit(1);
    }

    if (index < 0 || index >= list->size) {
        fprintf(stderr, "Error: index out of bound.\n");
        exit(1);
    }

    if (index == list->size - 1) {
        return list->tail->data;
    }

    node_t *node = list->head;
    for (int i = 0; i < index; i++) {
        node = node->next;
    }
    return node->data;
}

A singly linked list can only search forward from head through next. A doubly linked list can search forward from head or backward from tail through prev. A circular list cannot use NULL as its stopping condition; returning to the starting node means every node has been checked.