Decked Out Linked List – C Programming

There’s already hundreds of linked list implementations out there for C developers on the web. So what makes this one stand out? Well simply put, its decked out. It’s got everything you could ever ask for in a linked list, each of it’s methods fine tuned straight out of the box. In-fact, given a small bit of refactoring, this could be a production level linked list. 

So what exactly can this thing do? Well, for starters it’s got all the groundwork that you would expect from any linked list implementation. 

It’s got a method to insert nodes into the front of the list and another to insert them into the back of the list:


/* insertFront: appends a node which contains string
void insertFront(Node **head, char *s){
    Node *temp = malloc(sizeof(Node));
    temp->item = s;
    temp->next = *head;
    *head = temp;
}
/* insertEnd: appends a node which contains string s to the end of the list */
void insertEnd(Node **head, char *s){
    Node *to_insert = malloc(sizeof(Node));
    Node *temp = get_tail(*head);
    temp->next = to_insert;
    to_insert->item = s;
    to_insert->next = NULL;
}

There’s a method to search the list for a string and another for removing elements from the list:

Node *searchList(Node *head, char* item){
    if (head == NULL) return NULL;

    while(head->next != NULL){
        head = head->next;
        if(str_cmp(head->item, item) == 0){
            return head;
        }
    }
    return NULL;
}
void deleteNode(Node **head, char *s){
    Node *temp;
    Node *pred;

    temp = searchList(*head, s);
    if(temp != NULL){
        pred = predecessorNode(*head, s);
        if (pred == NULL){
            *head = temp->next;
        }
        else{
            pred->next = temp->next;
        }
        free(temp);
    }

}

Finally, there are a few auxiliary methods that aid other processes:

/* predecessorNode: returns a pointer to the node before the node that contains string s */
Node *predecessorNode(Node *head, char *s){
    if((head == NULL) || (head->next == NULL)){
        printf("Error: predecessor sought on null list\n");
        return(NULL);
    }
    if(str_cmp((head->next)->item, s) == 0){
        return head;
    }
    else{
        return(predecessorNode((head->next), s));
    }
}
/* get_tail: returns a pointer to the last node in the list */
Node *get_tail(Node *cur){
    while(cur != NULL && cur->next != NULL){
        cur = cur->next;
    }
    return cur;
}
void print_list(Node *head){
    while(head->next != NULL){
        printf("%s\n", head->item);
        head = head->next;
    }
    printf("%s", head->item);
}

And of-course we can’t have a linked list without a Node structure:

typedef struct Node{
    char* item;
    struct Node *next;
}Node;

Now that the ground work is out of the way lets jump into the juicy stuff. First, the sorting function. Most readily available linked lists use some variant of selection sort or insertion sort as they are the most simple to implement. However, what such functions offer in simplicity they pay for many times over in efficiency. Both selection and insertion sort have a time complexity of O(n^2) on an input of size n. Whereas the sorting function employed by our linked list is a variant of Quicksort, an algorithm that has a time complexity of O(n log(n)) which is a huge improvement from selection and insertion sort. To see this, imagine you are sorting a linked list that has one hundred nodes. On such a list the O(n^2) sorting algorithms yield 100^2 = 10,000, whereas our O(n log(n)) algorithm yields 100 * log(100) = 100 * 2 = 200. Meaning the O(n log(n)) implementation is roughly fifty times faster on an input list with 100 nodes. As the number of nodes we are dealing with increases, the difference in speed only becomes more apparent.

 

We can briefly summarize steps of Quicksort as follows:
  • Partition – Select a random element in the list to use as the pivot.
  • Swap - In this phase, we move all the elements that are greater than the pivot to the end of the list and all those that are less than the pivot to the beginning of the list.
  • Recurse - Then we simply update all the relevant information and repeat this process, picking a new pivot in the sublist to the left of the current pivot and sorting that and doing the same for the list to the right of the current pivot.
Node *partition(Node *head, Node *end, Node **nHead, Node **nTail){
    Node *pivot = end;
    Node *prev = NULL, *cur = head, *tail = pivot;

    while(cur != pivot){
        if(l_str_cmp(cur->item, pivot->item) < 0){
            //string in curr is less than pivot, thus we make cur the new head
            if(*nHead == NULL){
                *nHead = cur;
            }
            prev = cur;
            cur = cur->next;
        }
        else{

            //string in curr is greater than pivot
            if(prev != NULL){
                prev->next = cur->next;
            }
            //put curr after tail and update tail to reflect that
            Node *p = cur->next;
            cur->next = NULL;
            tail->next = cur;
            tail = cur;
            cur = p;
        }
    }

    if(*nHead == NULL){
        /*this means that the pivot was never greater than cur, and thus
        must be the smallest element in the current portion of the linked list.
        Thus we know nHead should be our pivot. */
        *nHead = pivot;
    }
    //We must updated the reference to the real tail node with our local tail variable
    *nTail = tail;

    return pivot;
}
Node *rQuick(Node *head, Node *tail){
    if(head == NULL || head == tail){
        return head;
    }

    Node *nHead = NULL;
    Node *nTail = NULL;

    Node *pivot = partition(head, tail, &nHead, &nTail);

    if(nHead != pivot){
        /*as we mentioned in partition, this means the pivot is not the smallest element
        in our list. If nHead was indeed equal to pivot it would be pointless to attempt
        to sort elements to the left of the pivot, and thus we skip this part */
        Node *p = nHead;
        while(p->next != pivot){
            p = p->next;
        }
        p->next = NULL;

        nHead = rQuick(nHead, p);

        //We make the pivot the new tail for this portion of the list
        p = get_tail(nHead);
        p->next = pivot;
    }

    //Now we have to sort the portion to the right of our partition
    pivot->next = rQuick(pivot->next, nTail);

    return nHead;
}

Now we put both of those functions together under a convenient wrapper function like so: 

void sort_strings(Node **head){
    *head = rQuick(*head, get_tail(*head));
}