3. Linear Structures

A computer processes some data. Always. Now what we are interested in this chapter is the structure of the data. Typically we will study linear structures like arrays, linked lists, stacks, queues etc. The structure of data is important because it governs how we can perform insertion, deletion, update and more such operations on data. It not only governs but also how fast we will be able to do such stuff. Some languages which have big standard libraries like C++, Python, Java etc they provide many utilities data structures and most common operations as a part of it. However, since C99 is having a much smaller standard library such facilities are not there.

It is assumed that the reader i.e. you know about basics of concepts like arrays, pointers, functions and recursion. C is primarily used to implement the data structures and algorithms therefore if you do not know C then probably you would want to read this.

Some of the linear structures are linked lists, stacks and queues. We will start with linked lists. Linked lists are also simply known as lists. A list can be mathematically modeled as \(t_1, t_2, ..., t_n\) i.e. a list having n items of element type. \(t_i\) is known as node at position \(i\) where \(i\) is used to indicate the position. All the elements are of the same type.

3.1. Singly Linked List

Let us begin with singlly linked lists. When we say linked typically we mean singly linked list. There is other types as well. Doubly linked lists and circular linked list for example. For now we will start with singly linked list because it is simplest to understand and can be used for as a base data structure to implement stacks and queues which are going to be coming chapters. A singly linked list looks something like given below:

System Message: WARNING/2 (\node at (0, 0) [rectangle, draw] (A1) {10}; \node at (2, 0) [rectangle, draw] (A2) {20}; \node at (4, 0) [rectangle, draw] (A3) {30}; \node at (6, 0) [rectangle, draw] (A4) {40}; \draw[<-, >=stealth] (A1.west) -- ++(-.5, 0); \draw[->, >=stealth] (A1.east) -- (A2.west); \draw[->, >=stealth] (A2.east) -- (A3.west); \draw[->, >=stealth] (A3.east) -- (A4.west); \draw[->, >=stealth] (A4.east) -- ++(.7, 0); \draw (A1.west)+(-1,0) node {head}; \draw (A2.west)+(-.7,.2) node {next}; \draw (A3.west)+(-.7,.2) node {next}; \draw (A4.west)+(-.7,.2) node {next}; \draw (A4.east)+(.5,.2) node {next}; \draw (A4.east)+(1.5,0) node {NULL};)

!pdftoppm command cannot be run

An example linked list.

A linked list’s first element is typically known as head and last element is known as tail. All nodes have a pointer which points to next node so that you can traverse list in forward direction. Note that it is impossible to traverse in opposite direction. tail’s next pointer point to NULL which indicates the ending point of the linked list. tail is not mandatory to have when dealing with linked list but a pointer to head is aleways present.

Impementation of a linked list involved a self referencing structure. Given below is a typical self referencing structure:

struct S {
  struct S *next;
};

struct S* head;

The presence of next which is a pointer of C causes some meory to be wasted in linear order equal to number of nodes in linked list. Note that real implementations will have some data members as well. Some common operation on a linked list are insertion at beginning, in between somewhere and at the end. We also can have an operation for counting number of nodes. Deletion and searching of a node is also there. Note that to do any of these operations except insertion at beginning we need to search the appropriate node which is an operation involving traversal of list in linear fashion. Therefore time compexity of all such operations is \(O(n)\). Insertion at beginning will have \(O(1)\) time complexity. However, if search operation for a particular node is to be considered separate then deletion and insertion at any place will have time complexity of \(O(n)\).

Let us implement a linked list and its operations:

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

typedef struct linked_list {
    int data;
    struct linked_list *next;
}ll;

void menu();
void add_at_beg(ll**);
void print(ll*);
void search(ll*);
void delete(ll**);
void append(ll**);
void add_in_bet(**);

void delete(ll** head)
{
    ll *temp, *q;
    int i;

    temp = *head;

    if(*head == NULL) {
        printf("There is no element to be deleted.\n");
        return;
    }

    printf("Enter the value of data to be deleted.\n");
    scanf("%d", &i);

    if(temp->data == i) {
        *head = temp->next;
        free(temp);
        return;
    } else {
        while(temp->next != NULL) {
            if(temp->data == i) {
                q->next = temp->next;
                free(temp);
                return;
            }
            q = temp;
            temp = temp->next;
        }
    }

    if(temp->data == i) { // case of deletion of last node
        q->next = temp->next;
        free(temp);
        return;
    }

    printf("The element to be deleted was not found.\n");
}

int count(ll* head)
{
    int count = 1;

    if(head == NULL) {
        printf("The no. of elements in linked list is %d.\n", 0);
        return 0;
    }

    while(head->next != NULL) {
        count++;
        head = head->next;
    }

    printf("The no. of elements in linked list is %d.\n", count);
    return count;
}

void menu()
{
    puts("1. Add an element at beginning.");
    puts("2. Add an element at position n.");
    puts("3. Add an element at end.");
    puts("4. Count the number of elements.");
    puts("5. Delete an element.");
    puts("6. Search an element.");
    puts("7. Print the list.");
}

void append(ll** head)
{
    ll* temp, *q = *head;
    int i;

    printf("Enter the number which is to be appended to the list.\n");
    scanf("%d", &i);

    temp = (ll*)malloc(sizeof(ll));
    temp->data = i;
    temp->next = NULL;

    if(!(*head)) {
        *head=temp;
        return;
    }

    while(q->next != NULL) {
        q = q->next;
    }

    q->next = temp;
}

void add_in_bet(ll** head)
{
    ll *temp, *q = *head;
    int i = 0, j = 0;
    int position = 0;

    printf("Enter position at which the number is to be added.\n");
    scanf("%d", &position);

    if(position == 0)
        return add_at_beg(head);

    temp = (ll*)malloc(sizeof(ll));

    printf("Enter an integer to be added in between.\n");
    scanf("%d", &i);

    while(q->next != NULL) {
        ++j;
        if(j == position) {
            temp->next = q->next;
            q->next = temp;
            temp->data = i;
            return;
        }
        q = q->next;
    }
    ++j;
    // This is the case when q->next is NULL so it is an append
    // operation
    if(j == position) {
        append(head);
    }
    free(temp); // no insertion happened so we need to free temp
                // i.e. j was out of possible positions
}

void add_at_beg(ll** head)
{
    ll *temp;
    int i;

    temp = (ll*)malloc(sizeof(ll));

    printf("Enter an integer to be added at beginning\n");
    scanf("%d", &i);

    temp->next = *head;
    *head = temp;
    (*head)->data = i;
}

void print(ll* head)
{
    printf("Head-->");
    while(head != NULL) {
        printf("%d--->", head->data);
        head = head->next;
    }

    printf("NULL\n");
}

void search(ll* head)
{
    int i=0, position=1;

    printf("Enter the number to be searched.");
    scanf("%d", &i);

    while(head != NULL) {
        if(head->data == i) {
            printf("%d is found at %dth position.\n", i, position - 1);
            return;
        }

        head = head->next;
        position++;
    }
    printf("%d was not found in linked list.\n", i);
}

int main()
{
    ll* head = NULL;
    int option = 0;

    menu();
    printf("Enter 1 to 7 to choose an action. Any other number to quit.\n");
    scanf("%d", &option);
    getchar(); // to remove \n

    while(option  >= 1 && option <= 7) {
        switch(option) {
            case 1:
                add_at_beg(&head);
                break;
            case 2:
                add_in_bet(&head);
                break;
            case 3:
                append(&head);
                break;
            case 4:
                count(head);
                break;
            case 5:
                delete(&head);
                break;
            case 6:
                search(head);
                break;
            case 7:
                print(head);
                break;
            default:
                break;
        }
        menu();
        printf("Enter 1 to 7 to choose an action. Any other number to quit.\n");
        fflush(stdin);
        scanf("%d", &option);
        getchar(); // to remove \n
    }

    return 0;
}

Now I will explain these function one by one using images. First we discuss add_at_begin. Note that we can wrap all insertion functions by calling single insert function of the type insert(ll* head, int item, size_t position). Please note that I have used size_t for position because I want the list to be able to have as many members as malloc allows. If we use something like int which is nothing but signed int then we would be restricted to 2 * 1024 * 1024 * 1024 or 2147483648 members. Note that size_t is nothing but unsigned long which is 4 bytes on 32-bit systems and 8 bytes on 64-bit systems.

3.1.1. Insertion at the Beginning

Insertion at beginning is simple. We create a new node. Then we make its next pointer to point to current head and then use current head pointer to point to this new node. The entire operation is shown graphically below:

System Message: WARNING/2 (\node at(0, 0) [rectangle, draw] (A) {G}; \draw[->, >=stealth] (A.east) -- ++(1, 0); \draw (A.east)+(.5, .2) node (B) {next}; \draw (A.north)+(0, 1) node (C) {temp}; \draw[->, >=stealth] (C.south) -- (A.north); \draw (A.west)+(-4,0) node(D) {*head}; \draw[->, >=stealth] (D.east) -- ++(1, 0); \draw (D.east)+(1.8, 0) node (E) {$NULL$}; \node [label={[align=center, yshift=-2.5cm]Initially $*head$ is $NULL$. We allocate a $temp$ node.\\$temp->data$ contains garbage and $temp->next$ points to unknown location.\\Let us say we want to insert 10.}] (F) {};)

!pdftoppm command cannot be run

System Message: WARNING/2 (\node at(0, 0) [rectangle, draw] (A) {G}; \draw[->, >=stealth] (A.east) -- ++(1, 0); \draw (A.east)+(.5, .2) node (B) {next}; \draw (A.north)+(0, 1) node (C) {temp}; \draw[->, >=stealth] (C.south) -- (A.north); \draw (A.west)+(-4,0) node(D) {*head}; \draw[->, >=stealth] (D.east) -- ++(1, 0); \draw (D.east)+(1.8, 0) node (E) {$NULL$}; \draw (A.east)+(1.8, 0) node {$NULL$}; \node [label={[align=center, yshift=-1.5cm]$temp->next$ is assigned $*head$ pointer which is $NULL$.}] (F) {};)

!pdftoppm command cannot be run

System Message: WARNING/2 (\node at(0, 0) [rectangle, draw] (A) {10}; \draw[->, >=stealth] (A.east) -- ++(1, 0); \draw (A.east)+(.5, .2) node (B) {next}; \draw (A.north)+(0, 1) node (C) {temp}; \draw[->, >=stealth] (C.south) -- (A.north); \draw[<-, >=stealth] (A.west) -- ++(-1, 0); \draw (A.west)+(-1.6, 0) node (E) {*head}; \draw (A.east)+(1.8, 0) node {$NULL$}; \node [label={[align=center, yshift=-1.5cm]$*head$ is assigned $temp$ and 10 is copied.}] (F) {};)

!pdftoppm command cannot be run

System Message: WARNING/2 (\node at(-2, 0) [rectangle, draw] (A) {G}; \draw[->, >=stealth] (A.east) -- ++(1, 0); \draw (A.east)+(.5, .2) node (B) {next}; \draw (A.north)+(0, 1) node (C) {temp}; \draw[->, >=stealth] (C.south) -- (A.north); \node at(3, 0) [rectangle, draw] (D) {10}; \draw[<-, >=stealth] (D.west) -- ++(-1,0); \draw (D.west)+(-1.6, 0) node (E) {*head}; \draw (D.east)+(1.8, 0) node {$NULL$}; \draw[->, >=stealth] (D.east) -- ++(1,0); \node [label={[align=center, yshift=-1.5cm] To insert another node 20 before 10 we allocate $temp$.}] (F) {};)

!pdftoppm command cannot be run