Practice Exercise

Your task is to write a function, listInsertNth, that takes three arguments: a linked list, a value and a position n, and inserts the value before position n of the list. Positions are counted in the same manner as the indexes of an array, so the first element in the list is regarded as being at position 0, the second element is regarded as being at position 1, and so on. If there are fewer than n elements in the list, the value should be appended to the end of the list.

Assumptions and Constraints

• n is non-negative.
• You must not use arrays.
• You must not change the values in any existing nodes.

Download

While in your practice exercises directory, run the following command:

unzip /web/cs2521/practice-exercises/lists/listInsertNth/downloads/listInsertNth.zip

If you're working at home, download listInsertNth.zip by clicking on the above link and then unzip the downloaded file.

Files

list.c	Contains the implementation of basic list functions
list.h	Contains the definition of the list data structure and function prototypes
testListInsertNth.c	Contains the main function, which reads in a list, a value and a position from standard input, calls listInsertNth, and prints out the result.
listInsertNth.c	Contains listInsertNth, the function you must implement
Makefile	A makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic tests
autotest	A script that uses the tests in the tests directory to autotest your solution. You should only run this after you have tested your solution manually.

Examples

./testListInsertNth
Enter list: 16 7 8
Enter value to insert: 12
Enter position to insert at: 0
Original list: [16] -> [7] -> [8] -> X
List after inserting 12 at position 0: [12] -> [16] -> [7] -> [8] -> X

./testListInsertNth
Enter list: 16 7 8
Enter value to insert: 12
Enter position to insert at: 1
Original list: [16] -> [7] -> [8] -> X
List after inserting 12 at position 1: [16] -> [12] -> [7] -> [8] -> X

./testListInsertNth
Enter list: 16 7 8
Enter value to insert: 12
Enter position to insert at: 2
Original list: [16] -> [7] -> [8] -> X
List after inserting 12 at position 2: [16] -> [7] -> [12] -> [8] -> X

./testListInsertNth
Enter list: 16 7 8
Enter value to insert: 12
Enter position to insert at: 3
Original list: [16] -> [7] -> [8] -> X
List after inserting 12 at position 3: [16] -> [7] -> [8] -> [12] -> X

Testing

You can compile and test your function using the following commands:

make                                 # compiles the program
./testListInsertNth                  # tests with manual input, outputs to terminal
./testListInsertNth < input-file     # tests with input from a file, outputs to terminal
./testListInsertNth < tests/01.in    # for example, tests with input from tests/01.in
                                       # (then manually compare with tests/01.exp)

After you have manually tested your solution, you can autotest it by running ./autotest. This will run some basic tests on your program, as well as check for memory leaks/errors.

It is possible to devise your own tests by creating your own input files. See the existing input files for examples. Note that you will need to check the output yourself.