Homework 9 Linked List Solution

1.1    Purpose

The purpose of this assignment is to introduce you to dynamic memory allocation in C. You will also learn how to implement a singly-linked list data structure in C.

How do we allocate memory on the heap? How do we de-allocate it when it is no longer used?

The goal of this assignment is to learn how to dynamically allocate and de-allocate memory, or manage memory, in C.

1.2    Task

In this assignment, you will be implementing a singly-linked list data structure. Your linked list nodes will have String-data (of type char *). Your linked list will be able to add, remove, and mutate, and query the data stored within it.

You will be writing code in

    1. list.c

    2. main.c

(main.c is only for your own testing purposes)

1.3    Criteria

You will be graded on your ability to implement the linked list data structure properly. Your implementation must be as described by each function’s documentation. Your code must manage memory correctly, meaning it must be free of memory leaks.

Note: A memory leak is when a block of memory is allocated for some purpose, and never de-allocated before the program loses all references to that block of memory.


    • Instructions

2.1    Implementation

You have been given one C le - list.c in which to implement the data structure. Implement all functions in this le. Each function has a block comment that describes exactly what it should do.

Be sure not to modify any other    les. Doing so will result in point deductions that the tester will not re ect.

Remember that the string data passed to certain methods (char *data) is malloc-ed data. However, this data is malloc-ed separately from the node structs that contain it.

Forgetting to free this data when it is removed can cause memory leaks, but freeing it when it should be returned to the user can cause a use-after-free scenario. Keep this in mind when writing your list methods.




2

You are given a struct linked list, which has a head pointer that points to the rst node in the list and a size which represents the length of the linked list. You also have a struct node that has a next pointer to the next list node and also a char pointer that points to a String in memory. Refer to the following diagram for a visual representation of list and list node:


































Once you’ve implemented the functions in the list.c le, or after implementing a few, compile your code using the make le. You may test your methods manually by writing your own test cases in the provided main.c, or run the autograder. See the Testing section below for more information.

2.2    Testing

Note: If you don’t want to use the docker GUI, run the cs2110 docker script with the ag -it. This will connect to docker using only the terminal, which is all you need for this homework.

To compile and test your code, use the Make le given as follows:

To manually test speci c methods in your code,    ll in the main method in main.c with tests, and run

make hw9

This will create an executable called hw9. Then, run the main method using

./hw9

To run the autograder, run

make run-tests


3

The local autograder does not test for memory leaks, though the one on gradescope does. To test your code for memory leaks locally, you will need to use valgrind.

To test your code using valgrind, run

make run-valgrind


    • Deliverables

Your only deliverable is the list.c    le.

The is what you need to submit to gradescope.


    • Appendix

4.1    Appendix D: Rules and Regulations

4.1.1    General Rules

    1. Starting with the assembly homeworks, any code you write should be meaningfully commented for your bene t. You should comment your code in terms of the algorithm you are implementing; we all know what each line of code does.

    2. Although you may ask TAs for clari cation, you are ultimately responsible for what you submit. This means that (in the case of demos) you should come prepared to explain to the TA how any piece of code you submitted works, even if you copied it from the book or read about it on the internet.

    3. Please read the assignment in its entirety before asking questions.

    4. Please start assignments early, and ask for help early. Do not email us the night the assignment is due with questions.

    5. If you nd any problems with the assignment it would be greatly appreciated if you reported them to the author (which can be found at the top of the assignment). Announcements will be posted if the assignment changes.

4.1.2    Submission Conventions

    1. All les you submit for assignments in this course should have your name at the top of the le as a comment for any source code le, and somewhere in the le, near the top, for other les unless otherwise noted.

    2. When preparing your submission you may either submit the les individually to Canvas/Gradescope. You can create an archive by right clicking on les and selecting the appropriate compress option on your system. Both ways (uploading raw les or an archive) are exactly equivalent, so choose whichever is most convenient for you.

    3. Do not submit compiled les, that is .class les for Java code and .o les for C code. Only submit the les we ask for in the assignment.

    4. Do not submit links to les. The autograder does not understand it, and we will not manually grade assignments submitted this way as it is easy to change the les after the submission period ends.





4

4.1.3    Submission Guidelines

    1. You are responsible for turning in assignments on time. This includes allowing for unforeseen circum-stances. If you have an emergency let us know IN ADVANCE of the due time supplying documenta-tion (i.e. note from the dean, doctor’s note, etc). Extensions will only be granted to those who contact us in advance of the deadline and no extensions will be made after the due date.

    2. You are also responsible for ensuring that what you turned in is what you meant to turn in. After submitting you should be sure to download your submission into a brand new folder and test if it works. No excuses if you submit the wrong les, what you turn in is what we grade. In addition, your assignment must be turned in via Canvas/Gradescope. Under no circumstances whatsoever we will accept any email submission of an assignment. Note: if you were granted an extension you will still turn in the assignment over Canvas/Gradescope.

    3. There is a 6-hour grace period added to all assignments. You may submit your assignment without penalty up until 11:55PM, or with 25% penalty up until 5:55AM. So what you should take from this is not to start assignments on the last day and plan to submit right at 11:54AM. You alone are responsible for submitting your homework before the grace period begins or ends; neither Canvas/Gradescope, nor your aky internet are to blame if you are unable to submit because you banked on your computer working up until 11:54PM. The penalty for submitting during the grace period (25%) or after (no credit) is non-negotiable.

4.1.4    Syllabus Excerpt on Academic Misconduct

Academic misconduct is taken very seriously in this class. Quizzes, timed labs and the nal examination are individual work.

Homework assignments are collaborative, In addition many if not all homework assignments will be evaluated via demo or code review. During this evaluation, you will be expected to be able to explain every aspect of your submission. Homework assignments will also be examined using computer programs to nd evidence of unauthorized collaboration.

What is unauthorized collaboration? Each individual programming assignment should be coded by you. You may work with others, but each student should be turning in their own version of the assignment. Submissions that are essentially identical will receive a zero and will be sent to the Dean of Students’ O ce of Academic Integrity. Submissions that are copies that have been super cially modi ed to conceal that they are copies are also considered unauthorized collaboration.

You are expressly forbidden to supply a copy of your homework to another student via elec-tronic means. This includes simply e-mailing it to them so they can look at it. If you supply an electronic copy of your homework to another student and they are charged with copying, you will also be charged. This includes storing your code on any site which would allow other parties to obtain your code such as but not limited to public repositories (Github), pastebin, etc. If you would like to use version control, use github.gatech.edu

4.1.5    Is collaboration allowed?

Collaboration is allowed on a high level, meaning that you may discuss design points and concepts relevant to the homework with your peers, share algorithms and pseudo-code, as well as help each other debug code. What you shouldn’t be doing, however, is pair programming where you collaborate with each other on a single instance of the code. Furthermore, sending an electronic copy of your homework to another student for them to look at and gure out what is wrong with their code is not an acceptable way to help them, because it is frequently the case that the recipient will simply modify the code and submit it as their own.





5
























Figure 1: Collaboration rules, explained colorfully









































6