<!--# <mark>Bug Fixes</mark>
<mark>Please see <a href="Lab1BugFix">Lab1 Bug Fix</a> for instructions on fixing bugs. Please see <a href="VMSetup#ssh">VM Setup's SSH section</a> if you want to use SSH keys instead of typing your username and password every time you hit Git.</mark-->
# Introduction
Please follow the [lab handout](lab2res/CS3841Lab2LinkedList.pdf).
* Submit your report in hard-copy at the start of the week 3 lab period, with the [Lab2 Checklist](lab2res/CS3841Lab2Checklistv3.pdf) stapled on top of it. <!--through [MSOE's esubmit](https://esubmit.msoe.edu/login) -->
* Submit your code through github classroom by forking [the lab 2 repository (navigate to link within blackboard)](http://msoe.blackboard.com). Place the link to your github repository by your name on the first page after the checklist. For example, Phileas might write:
<div align=center><big>Lab 2: Linked List<br>Phileas Fogg</big><br>
<mark>1 Jan 2018<br>
cs3841-2018-lab-2-foggp</mark></div>
I require [a more formal lab report](ReportStyle) this quarter than I usually do. <mark>Please see the new Report Style Guide for specific requirements as well as an example report</mark>.
# Resources
* [Lab Handout](lab2res/CS3841Lab2LinkedList.pdf)
* [Lab2 Checklist](lab2res/CS3841Lab2Checklistv3.pdf) <mark>Updated to match new style guide and to include Doxygen comments</mark>
* YouTube: [Detecting Memory Leaks With Valgrind](https://www.youtube.com/watch?v=UQ-QrdwjHMw) (Dr. Schilling)
* YouTube: [Using Doxygen with Eclipse](https://www.youtube.com/watch?v=GC9Xy7nLxyw) (Dr. Schilling)
* The API below
# API
To aid in copying the API into your souce code, the following listings are provided.
## Create Operation
<code>void ll_init(struct linkedList* list)</code>
This method will initialize an instance of a linked list, passed as a parameter, to default values.
This includes setting the head and tail to NULL and the size to 0.
<dl><dt>Parameters</dt><dd>struct linkedList* list : This is a pointer to the list that is initialized. The method must verify that this parameter is not NULL before dereferencing it.
<dt>Preconditions</dt><dd>list is a valid, non-NULL pointer to a struct linkedList structure which has been declared external to the linked list library.
<dt>Postconditions</dt><dd>The head and tail of the list are set to NULL. The size of the linked list is set to 0.
</dl>
## Destroy Operation
<code>void ll_clear(struct linkedList* list)</code>
This method will clear a linked list and restore it to its default, uninitialized state. All linked nodes and data associated with the node will be returned to the heap using the free operation.
<dl><dt>Basic Algorithm</dt><dd>Starting with the head, iterate through the list. As each node is reached, free the data memory with a call to the free function. After the data memory has been freed, determine the next node before freeing the listNode structure. When the end is reached, stop continuing.
<dt>Parameters</dt><dd>struct linkedList* list : This is a pointer to the linked list that is to be cleared. The method must verify that this parameter is not NULL before dereferencing it.
<dt>Preconditions</dt><dd>list must be a pointer to a struct linkedList which has previously been initialized with the ll_init function.
<dt>Postconditions</dt><dd>All allocated memory has been returned to the heap. The head and tail of the list are set to NULL. The size of the linked list is set to 0.
</dl>
## Add Operation
<code>bool ll_add(struct linkedList* list, const void* object, uint32 t size)</code>
This function will add the data pointed to by the object pointer to the end of the current linked list. This size will be adjusted accordingly.
<dl><dt>Basic Algorithm</dt><dd>The function must first check the validity of all parameters. This list must not be NULL, the object must not be NULL, and the size must be greater than 0. If all parameter validations pass, then the function shall allocate memory using malloc. The first allocation is for a listNode instance. The second allocation is for the data. The data will be copied from the address pointed to by the object parameter to the memory allocated by the second call to malloc. This listNode instance data will be set to point to the memory allocated for the data by the second malloc call. Once this is finished, the listNode instance will be added to the tail of the list and the links within the list will be updated appropriately. The list size will also be incremented by 1.
<dt>Parameters</dt><dd>struct linkedList* list : This is a pointer to the list that is to have data added to it. The function must verify that this parameter is not NULL before dereferencing it.
const void* object : This is a pointer to the object that is to be added onto the linked list. Typically this will be a C struct, though it may also be an array or other c data type. The function must verify that this parameter is not NULL before dereferencing it.
uint32 t size : This is the size of the object that is to be added onto the linked list. Typically, if a structure is being added to the list, this will be obtained through the sizeof() operator when the call to this function is made. The function must verify that this parameter is greater than
0.
<dt>Return Value</dt><dd>This function will return true if it is able to successfully complete and the appropriate data object is added to the end of the linked list. It will return false if any of the parameters is NULL or otherwise out of range or if the memory allocation calls fail.
<dt>Preconditions</dt><dd>list must be a pointer to a struct linkedList which has previously been initialized with the ll_init function.
<dt>Postconditions</dt><dd>The data pointed to by the object parameter will be added to the linked list. The size will be incremented by 1. The tail of the list will point to the new node which has been added.
</dl>
## Retrieve Operation
<code>void* ll_get(struct linkedList* list, uint32 t index)</code>
This method will retrieve data from the linked list, returning a pointer to the data in the list.
<dl><dt>Basic Algorithm</dt><dd>The function must first check the validity of all parameters. This list must not be NULL and the index must fall within the range 0 = index = listSize-1. If all parameter validations pass, then the iterate from the head until the appropriate index is reached. At this point, a pointer to the appropriate data is returned.
<dt>Parameters</dt><dd>struct linkedList * list : This is a pointer to the linked list. The function must verify that this parameter is not NULL before dereferencing it.uint32 t index : This is the index for the data which is to be retrieved. This must be within the range 0 = index = listSize - 1.
<dt>Return Value</dt><dd>This function will return a valid pointer if it is able to successfully complete and the appropriate data object is obtained from the linked list. It will return NULL if any of the parameters is NULL or otherwise out of range.
<dt>Preconditions</dt><dd>list must be a pointer to a struct linkedList which has previously been initialized with the ll_init function.
<dt>Postconditions</dt><dd>A pointer to the desired memory will be returned.
</dl>
## Remove Operation
<code>bool ll_remove(struct linkedList* list,uint32 t index)</code>
This method will remove an item from the given linked list. When this method is completed, the list will be reduced in size by 1 and the allocated memory will be freed.
<dl><dt>Basic Algorithm</dt><dd>The function must first check the validity of all parameters. This list must not be NULL and the index must fall within the range 0 = index = listSize-1. If all parameter validations pass, then the iterate from the head until the appropriate index is reached. At this point, adjust the links so that the node is no longer part of the list. Using the free function, free the data memory and then free the node of the linked list.
<dt>Parameters</dt><dd>struct linkedList* list: This is a pointer to the linked list. The function must verify that this parameter is not NULL before dereferencing it.
uint32 t index : This is the index for the data which is to be removed. This must be within the range 0 = index = listSize - 1.
<dt>Return Value</dt><dd>This function will return true if it is able to successfully complete and the appropriate data object is removed from the linked list. It will return false if any of the parameters is NULL or otherwise out of range.
<dt>Preconditions</dt><dd>list must be a pointer to a struct linkedList which has previously been initialized with the ll_init function.
<dt>Postconditions</dt><dd>The data stored in element index will be removed from the linked list. The size of the list will be decreased by 1. The head and / or tail of the list may be updated based on the removed element of the linked list.
</dl>
## Iterator
<code>struct linkedListIterator* ll_getIterator(struct linkedList* list)</code>
This function will return an iterator for the linked list. The iterator is contained within the linkedListIterator structure returned by this function.
<dl>
<dt>Basic Algorithm</dt><dd>Verify that the list parameter is not NULL. Using malloc, allocate memory for a linkedListIterator structure. Set the current element of this allocated structure to point to the head of the list. Then return the allocated structure.
<dt>Parameters</dt><dd>struct linkedList* list : This is a pointer to the linked list. The function must verify that this parameter is not NULL before dereferencing it.Return Value:
This function will return a pointer to a linkedlistIterator structure that has been allocated on the heap. The return value will be NULL if there is any problem creating this structure.
<dt>Preconditions</dt><dd>list must be a pointer to a struct linkedList which has previously been initialized with the ll_init function.
<dt>Postconditions</dt><dd>A new linkedListIterator will be allocated on the heap, and the current element of this structure will be set to the head of the list. (Note: The iterator will point at the head element, and the first call to the next method will return the data from the head element.)
</dl>
## Iterator
<code>bool ll_hasNext(struct linkedListIterator* iter)</code>
This method will determine if the given iterator has more data that has not been retrieved via the iterator. If yes, a value of true will be obtained. If not a value of false will be returned.
<dl><dt>Parameters</dt><dd>struct linkedListIterator* iter : This is a pointer to the iterator. The function must verify that this parameter is not NULL before dereferencing it.Return Value:
This function will return true if the given iterator has another element. Another element will be present so long as current is not NULL. It will return false if either the iterator is NULL or there are no additional items in the linked list, meaning that current is now assigned a value of NULL.
<dt>Preconditions</dt><dd>iter must be a pointer to a struct linkedListIterator which has previously been created by a call to the ll_getIterator function.
</dl>
## Iterator
<code>void * ll_next(struct linkedListIterator * iter)</code>
This function will obtain the next object from the linked list. A pointer to the next object will be returned.
<dl><dt>Basic Algorithm</dt><dd>Verify that the iterator is not NULL. Determine the location for the given data and define a pointer to it which will subsequently be returned. The given data is currently pointed to by current. Update the current to point to the next node on the linked list. Return the pointer that was stored previously.
<dt>Parameters</dt><dd>struct linkedListIterator* iter : This is a pointer to the iterator. The function must verify that this parameter is not NULL before dereferencing it.Return Value:
The return value will be a pointer to the next object on the linked list. (Note: The next object is stored in the location referred to as current in the iterator structure.) It if the iterator is invalid or there is no next object, the return value will be NULL.
<dt>Preconditions</dt><dd>iter must be a pointer to a struct linkedListIterator which has previously been created by a call to the ll_getIterator function.
<dt>Postconditions</dt><dd>The next element on the list will be returned. The iterator will be advanced to reference the next element on the linked list.
</dl>
## Size
<code>uint32 t ll_size(struct linkedList* list)</code>
This function will obtain the size of the linked list, namely the number of objects stored on the list.
<dl><dt>Basic Algorithm</dt><dd>Verify that the list is not NULL. Return the size element of the linked list structure.
<dt>Parameters</dt><dd>struct linkedList* list : This is a pointer to the linked list. The function must verify that this parameter is not NULL before dereferencing it.Return Value:
The return value will be the size of the list. If the list is empty or the list parameter is NULL, a value of 0 will be returned.
<dt>Preconditions</dt><dd>iter must be a pointer to a struct linkedList.
</dl>