Project Assignment: Implementation of a Linked List in C
Overview
The objective of this project is to implement functions for linked list in C. You should use the
following declaration for linked list nodes:
typedef struct node {
char data[10];
struct node *pNext;
} Node;
Functions
Your task is to implement the following functions. You are not allowed to change these listed
declarations.
Note that there are no indexes in a linked list (as in an array). In some functions, the assignment
mentions position. Positions are defined so that the first node in the list is in the position 1, the
second node in the list is in position 2, and so on.
The *head parameter points to the first element of the list.
• int isEmpty(Node *head) returns 1, if the list is empty; otherwise 0.
• Node *addToEnd(Node *head, char str[]) adds a new node containing the string
str to the end of the list. The function returns a pointer to the first node in the list.
• Node *addToBeginning(Node *head, char str[]) adds a new node containing
the string str to the start of the list. The function returns a pointer to the first node.
• int size(Node *head) returns the total number of nodes in the list.
• Node *tail(Node *head) returns a pointer to the last node in the list.
• Node *get_node(Node *head, int pos) returns the node at the given position. If
pos is bigger than the number of elements in the list, then the function returns NULL. The value
of the parameter pos is always at least 1.
• Node *deleteFirst(Node *head) removes the first element of the list and returns a
pointer to the new first element. The memory space of the deleted element is freed. If the only
element of the list is removed or the list was empty, the method returns NULL.
• Node *deleteLast(Node *head) removes the last element of the list and returns a
pointer to the first element. The memory space of the deleted element is freed. If the first
element is removed or the list was empty, the method returns NULL.
• int find(Node *head, char *str) returns the position of the element containing
the string str. If such an element is not found, then the method returns 0.
• void print(Node *head) prints the names stored in Nodes. For instance, the printing may
look like this:
Printing...
Node position 1: Heikki.
Node position 2: Matti.
Node position 3: Sirkka.
Node position 4: Pirkko.
• char *toString(Node *head) returns your list as a string, so you can print and preview
the list. The output format should be:
(Heikki) -> (Matti) -> (Sirkka) -> (Pirkko) -> NULL
• Node *reverse(Node *head) reverses the list so that the last the last node becomes the
first, the second-last node becomes the second, and so on until the first node becomes the last.
The requirement is that the reversing must be done only by changing the pointers. The method
returns a pointer to the beginning of the reversed list.
The main program
Download the file names.txt from Moodle and store it in the same directory as your source files
are. This file contains 25 Finnish first names – one name in one line and each line ends with a new
line character. Your main program should read this file line-by-line and store the names to a linked list
using repeatedly the function addToEnd.
Your main program should call all the functions you have implemented. You may use the function
main available in Moodle file model.c as a model.
Grading
Implementing one function may give 7 points in the case the solution works as specified. Because
there are 12 functions to implement, it is possible to get 7 x 12 = 84 points from the functions.
You may get 5 points from the main program implementation.
You may have additional 11 points if you divide your code into two C source files. The division needs
to be done so that the linked list functions are in one file (linked_list.c) and the main function
is in the file project.c. You need to also provide a header file (linked_list.h) that contains
the declarations of the linked list node and the functions you have implemented. You need also to
write a makefile, which first compiles your source codes to object codes, and then links the object
codes to one executable, whose name is project.
To pass the project work, you need to gather at least 50 points. The grade of the project work is
determined by this table:
Points 50-59 60-69 70-79 80-89 90-100
Grade 1 2 3 4 5
Submitting your program
There will be two submission boxes. Be sure that your program compiles correctly. If your source
codes are not compiling or they crash, this leads to the rejection of your project. Note that you
should not upload the file names.txt. That file is already available in CodeGrade.
Without makefile: Your program will be compiled in CodeGrade by using the command
gcc project.c -o project. Then, CodeGrade executes the complied program project.
The output of the program should show that the functions you have implemented work correctly.
With makefile: You submit four files: linked_list.c, linked_list.h, project.c,
makefile. The program is compiled in CodeGrade by the command make and your makefile
should produce an executable file project.
Note that the first submission round closes at 8/5 at 6:00 AM
Resubmission
If you got rejected, your project work needs to be corrected / completed. Also, those who got the
grade 1 or 2 in the first submission can resubmit their work.
If you are resubmitting, you must write in comments in the beginning of the file what are the
changes and improvements related to the first version.
The maximum number of points which you can obtain by resubmission is 75. This means that the
maximum grade in resubmission is 3.
You need to resubmit the project work by 29/5 at 6:00 AM.
If you did not submit your work in the first submission, you are not allowed to submit in
resubmission.
Plagiarism and ChatGPT
Plagiarism is an offense against teaching at LUT. All programs will be checked by using the plagiarism
detection tool of CodeGrade. If plagiarism is found, the project work is evaluated as failed. LUT
officials will be also informed.
Using ChatGPT is not prohibited. If you use AI in this project work or develop methods together with
your friend, you need to explain this briefly but clearly in the comment section in the beginning of
the file project.c.
If you claim as your own work something that you have not done, then this is considered as a
fraud.
Timetable
• 21/4: The submission boxes open in CodeGrade (at latest).
• 8/5 at 6:00 AM: Deadline for submitting the project work.
• 22/5: By this date, you will get the grade. Resubmission opens for works that need improving.
• 29/5: Resubmission closes.