CS250 Unit 10 Project: Linked List

Table of Contents


c4_u10_LinkedLists_Illustration.png

1. Introduction

About
For this project we will be implementing a LinkedList data structure. We will use the same Program from the previous two assignments, as the LinkedList is also a linear data structure.
Goals
  • Implement a LinkedList
  • Observe its usage in a program
Overview
  1. First you'll implement the LinkedList data structure, following the doxygen documentation.
  2. Second, in the Program.h, you'll replace the vector (or SmartDynamicArray) with the LinkedList.
Starter code
https://gitlab.com/moosadee/courses/-/tree/main/wip_projects/starter_code/c4_u10_LinkedLists?ref_type=heads
Doxygen documentation
doxygen/c4_u10_LinkedLists/classDataStructure_1_1LinkedList.html

1.1. Getting started

1.1.1. Creating a new branch

BEFORE getting started on the assignment, make sure to go back to the main or master branch and pull latest. This way, you will have the most up-to-date version of your repository, and you'll be starting from a shared base-point.

  1. git add . && git commit -m "backup" && git push to make sure to backup any work on your current branch.
  2. git checkout main to check out the main branch again.
  3. git pull to pull latest changes from the server.

Next, you will create a new branch to get started from:

  1. git checkout -b LinkedList to create a new branch for this assignment.

1.1.2. Getting the starter code

Download the starter code for this assignment here:

https://gitlab.com/moosadee/courses/-/tree/main/wip_projects/starter_code/c4_u10_LinkedLists?ref_type=heads

Extract the contents somewhere within your course repository folder.

The following files are already part of this directory:

CuTest
The unit test framework.
Data
The path where the products.txt file is.
DataStructure/Interfaces
ILinearDataStructure interface
DataStructure/
LinkedList.h, LinkedListNode.h, and LinkedListTester.h
Program
Product and Program files, same as with the Dynamic Array project
Utilities
Various helper functionality like string/int conversion, menu stuff, etc.

As well as VisualStudio2022 and CodeBlocks project files, and a Makefile and build.sh script.

. 
├── CuTest
│   ├── LICENSE
│   ├── README.md
│   ├── TesterBase.cpp
│   └── TesterBase.h
├── Data
│   └── products.txt
├── DataStructure
│   ├── Interfaces
│   │   └── ILinearDataStructure.h
│   └── LinkedList
│       ├── LinkedList.h
│       ├── LinkedListNode.h
│       └── LinkedListTester.h
├── Doxyfile
├── Exceptions
│   ├── InvalidIndexException.h
│   ├── ItemNotFoundException.h
│   ├── NotImplementedException.h
│   ├── NullptrException.h
│   ├── StructureEmptyException.h
│   └── StructureFullException.h
├── main.cpp
├── Program
│   ├── Product.cpp
│   ├── Product.h
│   ├── Program.cpp
│   └── Program.h
├── Project_CodeBlocks
│   ├── LinkedList_DataStructure.cbp
│   └── LinkedList_DataStructure.layout
├── Project_Makefile
│   ├── build.sh
│   └── Makefile
├── Project_VisualStudio2022
│   ├── DataStructures.sln
│   ├── DataStructures.vcxproj
│   ├── DataStructures.vcxproj.filters
│   └── DataStructures.vcxproj.user
└── Utilities
    ├── Logger.cpp
    ├── Logger.h
    ├── Menu.cpp
    ├── Menu.h
    ├── StringUtil.cpp
    ├── StringUtil.h
    └── Timer.h


2. Implementing the data structure

2.1. Opening the data structure documentation

To access the data structure's auto-generated documentation, go to this page:

doxygen/c4_u10_LinkedLists/classDataStructure_1_1LinkedList.html

(All the documentation on the doxygen page is also written out in the data structure's comments.)

You can click on a function name to view the detailed notes about the structure and how to implement it.


2.2. Running the unit tests

There are unit tests already provided for the entire structure. Use these to validate your work. If all your unit tests pass (and the tester doesn't crash before the end then you can assume that your data structure probably works correctly.


3. Updating the program

This program is the same as with the Dynamic Array structure. Replace the vector (or SmartDynanicArray) with the LinkedList structure and update the function calls.


Author: Rachel Wil Sha Singh

Created: 2023-10-13 Fri 18:48

Validate