Practice Exercise
List is Palindromic
Your task is to write a function, listIsPalindromic, that determines whether the sequence of values in a given doubly linked list is palindromic. A sequence of values is palindromic if it reads the same backwards as forwards. For example, the sequence [1, 2, 3, 2, 1] is palindromic, whereas the sequence [1, 2, 3, 4] is not. The function should return true if the sequence of values in the linked list is palindromic, and false otherwise.
Assumptions and Constraints
- You must not use arrays.
- You must not use any variant of
malloc, either directly or indirectly. - You must not modify the given list.
Download
While in your practice exercises directory, run the following command:
unzip /web/cs2521/practice-exercises/lists/listIsPalindromic/downloads/listIsPalindromic.zip
If you're working at home, download listIsPalindromic.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 |
| testListIsPalindromic.c | Contains the main function, which reads in a list from standard input, calls listIsPalindromic, and prints out the result. |
| listIsPalindromic.c | Contains listIsPalindromic, 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
./testListIsPalindromic Enter list: 1 2 3 2 1 listIsPalindromic returned TRUE
./testListIsPalindromic Enter list: 1 2 3 4 listIsPalindromic returned FALSE
./testListIsPalindromic Enter list: 9 4 7 1 1 7 4 9 listIsPalindromic returned TRUE
./testListIsPalindromic Enter list: 1 8 2 7 7 2 9 1 listIsPalindromic returned FALSE
./testListIsPalindromic Enter list: listIsPalindromic returned TRUE
Testing
You can compile and test your function using the following commands:
make # compiles the program ./testListIsPalindromic # tests with manual input, outputs to terminal ./testListIsPalindromic < input-file # tests with input from a file, outputs to terminal ./testListIsPalindromic < 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.