CSci223 - Spring 2005

Programming Assignment #3

Doubly-Linked List

---

For your third programming assignment you will be implementing five linked list functions. This assignment is intended to get you more familiar with pointers, as well as the C programming language in general.

The starter code includes the data structure as well as a few example functions. The header file included in the tarball contains prototypes for the functions. The header file should not be changed unless you are explicitly told to by the instructor. The starter code also includes a Makefile and a test program. The test program already tests the existing functions. You should add code to the test program to test the functions you write.

For all functions other than DLList_previous(), you may assume that the first argument is a pointer to the head node of the list. In other words, there are no nodes previous to it.

DLList DLList_previous( DLList );

This function should return a pointer to the node previous to its argument in the list.

DLList DLList_nth( DLList, int );

This function should return the nth node in the list. Numbering is just like arrays in Java or C. The first node is 0, second is 1, and so on. If the nth node does not exist, the function should return NULL.

int DLList_index( DLList, int );

This function should return the index of the of the first node whose data element is equal to the second argument. Numbering is as previously stated. If the data cannot be found in the list, -1 should be returned.

DLList DLList_prepend( DLList list, DLList new );

This function should place the new node at the head of the list. It should then return a pointer to the new node.

DLList DLList_remove( DLList list, DLList old );

This function should remove the old node from the list. A pointer should be returned to the head of the list.

DLList DLList_sort( DLList ); (Extra Credit)

Students may implement this function for 6 points of extra credit. The entire assignment is worth 100 points. This function should return a pointer to the sorted list. The nodes should be sorted by their data element. No new nodes can be created. The existing nodes must be rearranged into the proper order. It doesn't matter which sorting algorithm you use. Bubble sort should work just fine.

All functions should ensure that any pointers passed to them are not NULL. They should return NULL in this case. There are two exceptions to this. If the second argument to either DLList_prepend() or DLList_remove() is NULL, they should return their first argument.

This assignment will be graded according to the Programming Assignment #3 Grading Sheet. Any solutions that don't compile on onyx using the supplied Makefile will receive a healthy deduction.

This assignment is due by class time on Friday, March 11th. It will be considered late at 11:00am on Monday, March 14th. Any solutions received after graded solutions have been distributed to the class will receive a zero. Graded solutions will be distributed in class on March 21st.

Students should submit their solutions by email to the instructor. They should only submit the DLList.c file.

Please review the Honor Code section of the syllabus and be sure you are familiar with the applicable documents.