Assignment 1: List Datatype


5/5 - (2 votes)

Assignment 1: List Datatype CMPT 300

Assignment 1: List Datatype
This assignment is to be done individually. Do not share your code or solution, do not
copy code found online, ask all questions on Piazza discussion forum (see webpage).
You may use code provide by the instructor, or in the guides/videos provided by the
instructor (such as instructor’s YouTube videos).
You may follow any guides you like online as long as it is providing you information on
how to solve the problem vs a solution to the assignment.
If receiving help from someone, they must be helping you debug your code, not sharing
their code or writing it for you.
We will be carefully analyzing the code submitted to look for signs of plagiarism so
please don’t do it! If you are unsure about what is allowed please talk to an instructor or
You may not resubmit code you have previously submitted for any course or offering.
Instructors and TAs may conduct followup interviews with students to discuss their
implementation and design in order to verify the originality of the assignment.
This assignment is designed to get you into the swing of things with respect to C and UNIX. You
can develop on any Linux/Unix based system, but be sure that it compiles correctly on the CSIL
Linux computers using the gcc compiler (details on course website).
1. List Data type
You must implement the List abstract data type. The list data structure is widely used
throughout operating system programming. Although you should all be experts at list
manipulation, it will serve to refresh your list skills and get you back onto UNIX and into C
programming. Also, the routines you implement here will hopefully be useful in your subsequent
Each list element (node) is able to hold one item.
An item is any C data type that can be pointed to – so your node structure should have a
void* field in it to reference the item held by that node.
Every list has the notion of a current item, which can refer to any item in the list.
The current pointer may also point beyond the end, or before the beginning, of this list.
If the current pointer is before or beyond the list, a routine returning its item will return a
NULL pointer.
You must create the user-defined type List.
An instance of this type refers to a particular list and will be an argument to most of your
list manipulation routines.
1 Assignment based on version by Harinder Khangura
Generated May 13, 2020, 11:22 PM Page 1/2 Dr. Fraser ©
Assignment 1: List Datatype CMPT 300 with Harinder and Brian

As with all code that is written for operating systems, the goal here is efficiency. You
should temper implementation efficiency with a significant dose of code elegance
(though hopefully one can be accomplished without compromising the other).
The implementation must use statically allocated arrays for list nodes and list heads.
If the nodes are exhausted then trying to add an item to a list fails.
If the heads are exhausted then trying to create a new list fails.
Removing an item from a list frees the node which held the time, making the node
available for future use.
Freeing a list destroys the list, making its head available for future use.
In the interest of efficiency you must not use any “searches” to find free nodes or heads.
You must create a test program which adequately exercises each of the functions in
list.h enough to give confidence that your implementation is correct.
You must create list.h and list.c. A template for list.h can be found on the course
website. You may modify this file as needed (such as the data types defined); however, you must
not alter the function prototypes, or the name of the #define constants, because the marking
test code will depend heavily on this part being unmodified. Carefully review the documentation
for each function in list.h as it specifies what you must implement.
Important Constraints
When creating or deleting a new list, you must not search through heads.
When creating or deleting a node in a list, you must not search through nodes.
When advancing forward or backward through a list, you must not search through the list.
You are allowed to do a one-time non-constant time set-up / initialization of your data
structure(s) the very first time the user calls List_create()
C is loosely typed: when returning a void* the compiler may not provide full type safety.
Ensure that all your functions which return pointers to items (which are void*) are doing
just that: returning a pointer to an item stored in a node, not a pointer to a node.
2. Deliverables
Submit to CourSys ( a ZIP file of your project folder including:
1. list.h
2. list.c
3. Your own C program which uses and exercises your List data type.
4. makefile(s) to build your project.
We will add to your project a test program to mark the correctness of your list implementation. If
you have changed the file names, or constant names / function prototypes in the list.h file
then our test code will not execute and you will likely receive a very low grade.
All submissions will automatically be compared for unexplainable similar submissions. Please
make sure you do your own original work.
Generated May 13, 2020, 11:22 PM Page 2/2 Dr. Fraser ©

PlaceholderAssignment 1: List Datatype
Open chat
Need help?
Can we help?