• understanding how to manipulate linked lists

Before the lab you should re-read the relevant lecture slides and their accompanying examples. You should also have read the lab assessment guidelines.

Create a new directory for this lab called lab12 by typing:

mkdir lab12

Change to this directory by typing:

cd lab12

Download list_delete_first.c, the starting code for this exercise or use this cp command:

cp -n /web/cs1511/18s1/activities/list_delete_first/list_delete_first.c .

Note list_delete_first.c uses the following familiar data type:

struct node {
    struct node *next;
    int          data;
};

Your task is to add code to this function:

struct node *delete_first(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return NULL;

}

delete_first is given one argument, head, which is the pointer to the first node in the linked list.

Add code to delete_first so that it deletes the first node from list.

delete_first should return a pointer to the new first node in the list.

If the list is now empty delete_first should return NULL.

delete_first should call free to free the memory of the node it deletes.

For example if the linked list contains these 8 elements:

16, 7, 8, 12, 13, 19, 21, 12

delete_first should return a pointer to a list with these elements:

7, 8, 12, 13, 19, 21, 12

Hint: this is a simple task requiring only a few lines of code.

Testing

list_delete_first.c also contains a main function which allows you to test your delete_first function. It converts command-line arguments to a linked list, calls delete_first, and then prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your delete_first function will be called directly in marking. The main function is only to let you test your delete_first function

Here is how you the main function allows you to test delete_first:

cp -n /web/cs1511/18s1/activities/list_delete_first/list_delete_first.c .
dcc list_delete_first.c -o list_delete_first
./list_delete_first 16 7 8 12 13 19 21 12
[7, 8, 12, 13, 19, 21, 12]
./list_delete_first 2 4 6 2 4 6
[4, 6, 2, 4, 6]
./list_delete_first 42
[]
./list_delete_first
[]

Assumptions/Restrictions/Clarifications.

delete_first should call free to free the memory for the node it deletes

delete_first should not change the data fields of list nodes.

delete_first should not use arrays.

delete_first should not call malloc.

delete_first should not call scanf (or getchar or fgets).

delete_first should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1511 autotest list_delete_first

When you are finished on this exercise you and your lab partner must both submit your work by running give:

give cs1511 wk12_list_delete_first list_delete_first.c

Note, even though this is a pair exercise, you both must run give from your own account before Sunday 27 May 23:59:59 to obtain the marks for this lab exercise.

Download list_delete_last.c, the starting code for this exercise or use this cp command:

cp -n /web/cs1511/18s1/activities/list_delete_last/list_delete_last.c .

Note list_delete_last.c uses the following familiar data type:

struct node {
    struct node *next;
    int          data;
};

Your task is to add code to this function:

struct node *delete_last(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return NULL;

}

delete_last is given one argument, head, which is the pointer to the first node in a linked list.

Add code to delete_last so that it deletes the last node from list.

delete_last should return a pointer to the new list.

If the list is now empty delete_last should return NULL.

delete_last should call free to free the memory of the node it deletes.

For example if the linked list contains these 8 elements:

16, 7, 8, 12, 13, 19, 21, 12

delete_last should return a pointer to a list with these elements:

16, 7, 8, 12, 13, 19, 21

Testing

list_delete_last.c also contains a main function which allows you to test your delete_last function.

This main function:

• converts the command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls delete_last(head)
• prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your delete_last function will be called directly in marking. The main function is only to let you test your delete_last function

cp -n /web/cs1511/18s1/activities/list_delete_last/list_delete_last.c .
dcc list_delete_last.c -o list_delete_last
./list_delete_last 16 7 8 12 13 19 21 12
[16, 7, 8, 12, 13, 19, 21]
./list_delete_last 2 4 6 2 4 6
[2, 4, 6, 2, 4]
./list_delete_last 42
[]
./list_delete_last
[]

Assumptions/Restrictions/Clarifications.

delete_last should call free to free the memory for the node it deletes

delete_first should not change the data fields of list nodes.

delete_last should not use arrays.

delete_last should not call malloc.

delete_last should not call scanf (or getchar or fgets).

delete_last should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1511 autotest list_delete_last

When you are finished on this exercise you and your lab partner must both submit your work by running give:

give cs1511 wk12_list_delete_last list_delete_last.c

Note, even though this is a pair exercise, you both must run give from your own account before Sunday 27 May 23:59:59 to obtain the marks for this lab exercise.

Download list_delete_contains.c, the starting code for this exercise or use this cp command:

cp -n /web/cs1511/18s1/activities/list_delete_contains/list_delete_contains.c .

Note list_delete_contains.c uses the following familiar data type:

struct node {
    struct node *next;
    int          data;
};

Your task is to add code to this function:

// Delete the first node in the list containing the value `value`.
// The deleted node is freed.
// If no node contains `value`, the list is not changed.
// The head of the list is returned.
struct node *delete_contains(int value, struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return NULL;

}

delete_contains is given two argument, value and head. value is an int. head is the pointer to the first node in a linked list.

Add code to delete_contains so that it deletes the first node in the linked list that whose data field equals value.

If value does not occur in the linked list, the list should not be changed.

If value occurs more than once in the linked list, only the first occurrence should be deleted.

delete_contains should return a pointer to the new list.

If the list is now empty delete_contains should return NULL.

delete_contains should call free to free the memory of the node it deletes.

For example if value is 12 and the linked list contains these 8 elements:

16, 7, 8, 12, 13, 19, 21, 12

delete_contains should return a pointer to a list with these elements:

16, 7, 8, 13, 19, 21, 12

Testing

list_delete_contains.c also contains a main function which allows you to test your delete_contains function.

This main function:

• converts the first command-line argument to value
• converts the remaining command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls delete_contains(value, head)
• prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your delete_contains function will be called directly in marking. The main function is only to let you test your delete_contains function

cp -n /web/cs1511/18s1/activities/list_delete_contains/list_delete_contains.c .
dcc list_delete_contains.c -o list_delete_contains
./list_delete_contains 12 16 7 8 12 13 19 21 12
[16, 7, 8, 13, 19, 21, 12]
./list_delete_contains 42 16 7 8 12 13 19 21 12
[16, 7, 8, 12, 13, 19, 21, 12]
./list_delete_contains 2 4 6 2 4 6
[4, 6, 4, 6]
./list_delete_contains 42 42
[]
./list_delete_contains 42
[]

Assumptions/Restrictions/Clarifications.

delete_contains should call free to free the memory for the node it deletes

delete_first should not change the data fields of list nodes.

delete_contains should not use arrays.

delete_contains should not call malloc.

delete_contains should not call scanf (or getchar or fgets).

delete_contains should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1511 autotest list_delete_contains

When you are finished on this exercise you and your lab partner must both submit your work by running give:

give cs1511 wk12_list_delete_contains list_delete_contains.c

Note, even though this is a pair exercise, you both must run give from your own account before Sunday 27 May 23:59:59 to obtain the marks for this lab exercise.

Download list_reverse.c, the starting code for this exercise or use this cp command:

cp -n /web/cs1511/18s1/activities/list_reverse/list_reverse.c .

Note list_reverse.c uses the following familiar data type:

struct node {
    struct node *next;
    int          data;
};

Your task is to add code to this function:

struct node *reverse(struct node *head) {

    // PUT YOUR CODE HERE (change the next line!)
    return NULL;

}

list_reverse is given one argument, head, which is the pointer to the first node in the linked list.

Add code to reverse which rearranges the list to be in reverse order.

reverse should return a pointer to the new list.

reverse must rearrange the list by changing the next fields of nodes.

reverse must not change the data fields of nodes.

For example if the linked list contains these 8 elements:

16, 7, 8, 12, 13, 19, 21, 12

reverse should return a pointer to a list with these elements:

12, 21, 19, 13, 12, 8, 7, 16

Testing

list_reverse.c also contains a main function which allows you to test your list_reverse function.

This main function:

• converts the command-line arguments to a linked list
• assigns a pointer to the first node in the linked list to head
• calls reverse(head)
• prints the result.

Do not change this main function. If you want to change it, you have misread the question.

Your list_reverse function will be called directly in marking. The main function is only to let you test your list_reverse function

cp -n /web/cs1511/18s1/activities/list_reverse/list_reverse.c .
dcc list_reverse.c -o list_reverse
./list_reverse 16 7 8 12 13 19 21 12
[12, 21, 19, 13, 12, 8, 7, 16]
./list_reverse 2 4 6 2 4 6
[6, 4, 2, 6, 4, 2]
./list_reverse 42
[42]
./list_reverse
[]

Assumptions/Restrictions/Clarifications.

list_reverse should not change the data fields of list nodes.

list_reverse should not use arrays.

list_reverse should not call malloc.

list_reverse should not call scanf (or getchar or fgets).

list_reverse should not print anything. It should not call printf.

Do not change the supplied main function. It will not be tested or marked.

When you think your program is working you can use autotest to run some simple automated tests:

1511 autotest list_reverse

When you are finished working on this exercise you must submit your work by running give:

give cs1511 wk12_list_reverse list_reverse.c

You must run give before Sunday 27 May 23:59:59 to obtain the marks for this lab exercise. Note, this is an individual exercise, the work you submit with give must be entirely your own.

When you are finished each exercises make sure you submit your work by running give.

You can run give multiple times. Only your last submission will be marked.

Don't submit any exercises you haven't attempted.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

Remember you have until Sunday 27 May 23:59:59 to submit your work.

Automarking will be run several days after the submission deadline for the test. When complete you can view automarking here and you can view the the resulting mark via give's web interface

You can read more about lab assessment here