Laboratory: Linked Lists

The problems below should be solved using singly linked simple lists (without sentinel). All basic list operations must be realized: traversing, insertion and deleting from the list. It is advantageous to draw the pointers and the interesting elements and how the given operation works: how the pointer values change.

Preparation for lab:

• Review lecture topics on pointers
• Review lecture topics on linked lists

There is a mistake in the code similar to those seen on the previous practice. Do you get any compiler message? What happens when you run the program and why? Is there any difference between the two versions? Discuss it with your lab conductor.

#include <stdio.h>

int *f1(int i) {
    return &i;
}

int main(void) {
    int *p;
    p = f1(10);
    printf("%d\n", *p);
    printf("%d\n", *p);
    return 0;
}

#include <stdio.h>

int *f1(int i) {
    return &i;
}

int main(void) {
    int x = 10;
    int *p = f1(x);
    printf("%d\n", *p);
    printf("%d\n", *p);
    return 0;
}

See the code below. The program builds a singly linked list from the content of the array, head points to the beginning of the list.

#include <stdlib.h>

typedef struct ListEl {
    int data;
    struct ListEl *nxt;
} ListEl;


/* creates a new list from the array elements */
ListEl *list_build(void) {
    int values[] = { 8, 14, 13, 17, 1, 19, 16, 5, 3, 11, 2,
                     15, 9, 10, 6, 22, 4, 7, 18, 27, -15 };
    ListEl *lis = NULL;

    int i;
    for (i = 0; values[i] > -1; ++i) {
        ListEl *u;
        u = (ListEl*) malloc(sizeof(ListEl));
        u->nxt = lis;
        u->data = values[i];
        lis = u;
    }
    return lis;
}


int main(void) {
    ListEl *head;
    
    head = list_build();
    
    ....
    
    return 0;   
}

Copy and paste the code into a new project! Write a loop that prints the values stored in the list! You should get this output:

27 18 7 4 22 6 10 9 15 2 11 3 5 16 19 1 17 13 14 8

Why are the values reversed?

Insert a code segment that counts the length of the list! To check it compare the calculated number to the number of elements printed.

After testing, move and turn this code segment into a function that receives the list as parameter and returns its length!

There is memory leak in the program above. Write a loop that deletes the elements of the list! (Do NOT use recursion!) Move this loop into a function that receives the list as parameter.

Write a function that receives a list and an integer value as parameters. Insert the value as the first element of the list (at the head).

This way the head pointer in main must change for each insertion. Thus the function must either return the new head pointer, or take the head pointer parameter by address. Choose the first now:

head = list_insert_athead(head, 25);

Insert a few values and print the list. The inserted values print in reverse order, of course. If your function works fine, delete the function list_build() provided in the code above, and replace it with this new function.

Write a function that receives a list and an integer value as parameters. Insert the value as the last element of the list. Pay special attention to make it work for an empy list as well (NULL pointer parameter)! In this case the head pointer changes, so it must be handled like in the previous function.

Create a function that takes a list and an integer value parameter. Return a pointer to the first such element of the list that contains the received integer. Return NULL if there is no such element.

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


/* an element of the list: */
typedef struct ListEl {
    int data;              /* The data to store */
    struct ListEl *nxt;    /* Pointer to the next list element */
} ListEl;


/* Printing the list */
void list_print(ListEl *head) {
    ListEl *p;
    for (p = head; p != NULL; p = p->nxt)
        printf("%d ", p->data);
    printf("\n");
}

/* Releasing a list */
void list_free(ListEl *head) {
    ListEl *p = head;
    /* Traversing the list */
    while (p != NULL) {
        /* Just writing free(p); is wrong, the rest of the list would be lost */
        /* hence p=p->nxt; would be invalid */
        ListEl *tmp = p->nxt; /* Store the pointer to the rest of the list */
        free(p); /* Now we can delete the current element */
        p = tmp; /* Keep releasing the list from the next element on */
    }
}

/* Inserting a new element to the head of the list */
ListEl *list_insert_athead(ListEl *head, int what) {
    ListEl *newel = (ListEl *) malloc(sizeof(ListEl)); /* New element */
    newel->data = what; /* Copy data to store to the list element */
    newel->nxt  = head; /* After the new element goes the rest of the list (even if it is empty) */
    return newel; /* The new element will be the new head of the list */
}

/* Inserting a new element to the end of the list */
ListEl *list_insert_atend(ListEl *head, int what) {
    ListEl *newel = (ListEl *) malloc(sizeof(ListEl)); /* New element */

    newel->data = what; /* Copy data to store to the list element */
    newel->nxt  = NULL; /* This will be the last element of the list, next pointer is NULL */
    if (head == NULL) {
        return newel; /* If the list was empty, the new element is the head of the list */
    } else {
        ListEl *p = head; /* Walk to the end of the list */
        while (p->nxt != NULL) p = p->nxt;
        p->nxt = newel; /* ... and add the new element to the chain */
        return head; /* The head of the list did not change in this case */
    }
}

/* Return length of the list */
int list_length(ListEl *head) {
    /* Traversing the list and counting the number of elements */
    int len = 0;
    ListEl *p = head;
    while (p != NULL) {
        len++;
        p = p->nxt;
    }
    return len;
}

/* Searching for an element in the list */
ListEl *list_search(ListEl *head, int what) {
    ListEl *p;
    for (p = head; p != NULL; p = p->nxt)
        if (p->data == what)
            return p;
    return NULL;
}

/* The main program */
int main(void) {
    ListEl *head = NULL;

    head = list_insert_atend(head, 66);
    head = list_insert_athead(head, 55);
    head = list_insert_atend(head, 77);
    head = list_insert_athead(head, 44);
    head = list_insert_athead(head, 33);
    head = list_insert_athead(head, 22);
    head = list_insert_athead(head, 11);
    list_print(head);
    printf("\nLength: %d\n", list_length(head));

    ListEl *hit = list_search(head, 44);
    if (hit != NULL)
        printf("%d\n", hit->data);
    else
        printf("no such data in the list\n");

    list_free(head);

    return 0;
}

Copying a list

Define a type for a simple singly linked list, the data member of which is an array of 20 int values! Write a function that receives a list as parameter. It should create an identical copy of the received list and return it. (So it should create another list with the same elements, in the same order.)

Delete the fifth element

Write a function that deletes the fifth element of a list! If there are less than 5 elements, nothing to be done. The function has a single parameter: the head pointer.

Define a type for a simple singly linked list, the data member of which is a word of max. 30 characters. Make a drawing and number the required steps. Demonstrate the usage of the function: define a list, suppose it has some values in it, then delete the fifth element using the function.

Insert into fifth position

Write a function that inserts a new value into a list in such a way that the new element will be the fifth one of the list! If there are less than 4 elements, insert at the end. The function has two parameters: the head pointer and the data to be inserted.

Define a type for a simple singly linked list, the data member of which is a name of max. 50 characters. Make a drawing and number the required steps. Demonstrate the usage of the function: define a list, suppose it has some values (at least one value) in it, then insert Donald Duck into fifth position using the function.

From head to end

Write a function that moves the very first element of a list to the very last position! (Like from a list of 1,2,3,4,5 the modified list should be 2,3,4,5,1.) If there are less than two elements, nothing to be done.

Define a type for a simple singly linked list, the data member of which is an integer value. Make a drawing and number the required steps. Demonstrate the usage of the function: create a list of two elements, then move the first one to the end using the function.

From end to head

Write a function that moves the very last element of a list to the very first position! (Like from a list of 1,2,3,4,5 the modified list should be 5,1,2,3,4.) If there are less than two elements, nothing to be done.

Define a type for a simple singly linked list, the data member of which is a real value. Make a drawing and number the required steps. Demonstrate the usage of the function: create a list of two elements, then move the last one to the head using the function.