Data Structure's Lab 2: Linked List

lab2.c

/*
    char *name = "Khatthaphone";
    char *class = "2IT";
    char *student_id = "FNEN0376/16";
    char *date = "20th March 2018";

    // download source code at:
    // https://gist.github.com/khatthaphone/6ecc58601c07c2948d564bef4c2c0976

    // tested and compiled with clang 3.8.0-2ubntu4 on ubuntu 16.04.4
*/

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

// declare struct (record) with 'typedef'
typedef struct node
{
    int data;
    struct node *next;
}
node;
typedef struct dnode
{
    int data;
    struct dnode *next;
    struct dnode *back;
}
dnode;

node * create_list(int length);
dnode * create_double_list(int length);
void insert_head(node *head, int num);
void insert_at(node *head, int position, int num);
void insert_double_at(dnode *dhead, int position, int num);
void insert_double_head(dnode *dhead, int num);
void delete_at(node *head, int position);
void print_list(node *head);
void print_double_list(dnode *dhead);
int get_int(char *message);

int main(void)
{
    // functions are aligned in order of assignment tasks respectively

    // 1. create a linked list containing 10 nodes and print every node in the list
    node *head = create_list(10);
    // print all linked list data
    print_list(head);

    // 2. create a program/function to insert a  node at the head of the linked list
    // insert_head(head, get_int("enter a number to insert to the head of the linked list\n"));

    // 3. create another function to insert a node at specified position of the linked list
    // insert_at(head, get_int("enter the position of new insertion\n"), get_int("enter a number to insert to the linked list\n"));

    // 4. create a function to delete a specified node of the linked list
    delete_at(head,get_int("position of node to be deleted from the linked list\n"));

    printf("\n\n\n========================================================\n\n\n");

    // 5. create a double linked list containing 5 nodes, sorted by their data
    dnode *dhead = create_double_list(5);
    // print all double linked list data (ascending sorted)
    print_double_list(dhead);
}

node* create_list(int length)
{
    // get input for length times
    // Create head pointer
    node *head = malloc(sizeof(node));
    // Create traversal pointer
    node *trav = head;

    printf("enter %d numbers to create a linked list:\n", length);

    int i;
    for (i = 0; i < length; i++)
    {
        // Assign the first input value to header
        if (i == 0)
        {
            // set num to head->data
            head->data = get_int("");
        }
        // After the first input, save to active traversal pointer and so on
        else
        {
            // allocate new (next) node
            node *next = malloc(sizeof(node));
            // set head->next and move traversal pointer to newly created node
            trav->next = next;
            trav = trav->next;
            // set num to trav->data
            trav->data = get_int("\n");
        }
    }
    return head;
}

dnode* create_double_list(int length)
{
    // get input for length times
    // Create head pointer
    dnode *dhead = malloc(sizeof(dnode));
    // Create traversal pointer
    dnode *dtrav = dhead;

    printf("enter %d numbers to create a double linked list:\n", length);

    int i;
    for (i = 0; i < length; i++)
    {
        // Assign the first input value to header
        if (i == 0)
        {
            // set num to dhead->data
            dhead->data = get_int("");
            dhead->back = NULL;
        }
        // After the first input, save to active traversal pointer and so on
        else
        {
            // go back to head after each iteration
            dtrav = dhead;
            dnode *dprev = dtrav;

            int num = get_int("");
            int data = dtrav->data;
            int position = 0;
            // loop until dtrav is at the position to insert
            while((data < num) && (dtrav != NULL))
            {
                dprev = dtrav;
                dtrav = dtrav->next;
                if (dtrav != NULL) data = dtrav->data;
                position++;
            }

            // if not at the end of the list
            if (dtrav != NULL)
            {
                insert_double_at(dhead, position, num);
            }
            // if at the end of the list
            else
            {
                dnode *new = malloc(sizeof(dnode));
                new->data = num;
                dtrav = new;
                dprev->next = dtrav;
                dtrav->back = dprev;
            }
        }
    }

    return dhead;
}

void insert_head(node *head, int num)
{
    node *new = malloc(sizeof(node));

    new->data = head->data;
    new->next = head->next;

    head->data = num;
    head->next = new;

    print_list(head);
}

void insert_double_head(dnode *dhead, int num)
{
    dnode *dnew = malloc(sizeof(dnode));

    // copy data from dhead to dnew
    dnew->data = dhead->data;
    // point dnew->next to the same as dhead->next
    dnew->next = dhead->next;
    // point dhead->next to dnew
    dhead->next = dnew;
    // point dnew->back back to dhead
    dnew->back = dhead;
    // set dnew->next's back back to dnew
    dnode *dnext = dnew->next;
    dnext->back = dnew;
    // // set new integer to dhead
    dhead->data = num;
}

void insert_at(node *head, int position, int num)
{

    if (position == 0)
    {
        insert_head(head, num);
    }
    else
    {
        node *trav = head;
        node *prev = malloc(sizeof(node));

        node *new = malloc(sizeof(node));
        new->data = num;

        int i = 0;
        // loop until trav is at the position to insert
        while(i < position && trav != NULL)
        {
            if (i == (position - 1)) prev = trav;
            trav = trav->next;
            i++;
        }

        // point new->next to the position (trav)
        new->next = trav;
        // point previos node->next to new node
        prev->next = new;

    }

    print_list(head);
}

void insert_double_at(dnode *dhead, int position, int num)
{

    if (position == 0)
    {
        insert_double_head(dhead, num);
    }
    else
    {
        dnode *dtrav = dhead;

        dnode *dnew = malloc(sizeof(dnode));
        dnew->data = num;

        int i = 0;
        // loop until dtrav is at the position to insert
        while(i < position && dtrav != NULL)
        {
            dtrav = dtrav->next;
            i++;
        }

        // point dnew->next to position's dnode (dtrav)
        dnew->next = dtrav;
        // point dnew->next to the dnode before position's dnode (dtrav)
        dnew->back = dtrav->back;
        // point previous dnode->next to dnew
        dnode *prev = dtrav->back;
        prev->next = dnew;
        // point dtrav->back to dnew
        dtrav->back = dnew;

    }
}

void delete_at(node *head, int position)
{
    node *trav = head;
    node *prev = malloc(sizeof(node));
    node *temp = malloc(sizeof(node));

    if (position == 0)
    {
        temp = head->next;
        head->data = temp->data;
        head->next = temp->next;
        temp = NULL;
    }
    else
    {
        int i = 0;
        // loop until trav is at the position to delete
        while(i != position)
        {
            if (i == (position - 1)) {
                prev = trav;
                prev->next = trav->next;
                trav = NULL;
                break;
            } else {
                trav = trav->next;
                i++;
            }
        }
    }

    free(temp);

    print_list(head);
}

void print_list(node *head)
{
    printf("linked list: \n");
    // loop and print until reaching the end of the list (using for loop)
    int i;
    node *trav;
    for (trav = head, i = 0; trav != NULL; trav = trav->next, i++)
    {
        // indent line number with 1 digit
        if (i < 10) printf(" ");
        printf("%d| %d\n", i, trav->data);
    }
}

void print_double_list(dnode *dhead)
{
    dnode *dtrav = dhead;

    printf("double linked list:\n");
    int i = 0;
    // loop and print until reaching the end of the list (using while loop)
    while(dtrav != NULL)
    {
        // indent line number with 1 digit
        if (i < 10) printf(" ");
        printf("%d| %d\n", i, dtrav->data);
        dtrav = dtrav->next;
        i++;
    }
}

int get_int(char *message)
{
    // if (message != NULL)
    if (message) printf("%s", message);

    int num;
    scanf("%i", &num);
    return num;
}