Link Search Menu Expand Document
CS16 S23

lab06 - Linked Lists in C++ with structs

Goals for this lab

The goal of this lab is practice iterating through linked lists and solving problems. Continue to practice code tracing to reason about your code.

We request that you DO NOT ask the staff to debug your code for you. They have been specifically instructed not to debug for you, but rather to guide you through the process of debugging your code yourselves.

Step by Step Instructions

Step 1: Getting Ready

  1. Go to github and find a repo for this lab assigned to your GitHub id.
  2. Log on to your CSIL account.
  3. Change into your ~/cs16 directory
  4. Clone your empty lab06 repo into your ~/cs16 directory.
  5. In your empty repo, do git checkout -b main to establish that you are on the main branch as your default branch.

Step 2: Obtain the starter code

The starter code is in this repo:

The URL for cloning this repo is this:

  • git@github.com:ucsb-cs16-s23/STARTER-lab06.git

Previous labs contain instruction for the process of:

  • Adding a starter remote for this repo
  • Pulling the code from that starter remote into your own repo.

Please do those steps now, and then do a git push origin main to populate your own repo with the starter code.

If you need help with these steps:

  • First consult previous labs for more detailed instructions.
  • Then, if you are still having trouble, ask the staff for help during discussion section or office hours.

Once you’ve populated your repo, typing the ls command should show you the following files in your current directory

$ ls
Makefile              linkedListFuncs.h	       tddFuncs.cpp
README.md             llTests.cpp		           tddFuncs.h
linkedList.h          moreLinkedListFuncs.cpp
linkedListFuncs.cpp	  moreLinkedListFuncs.h

Step 3: Reviewing the files and what your tasks are

Here is a list of your tasks for this lab:

Step 3a: Familiarize yourself with the big picture

Type “make tests” and you will see some tests pass, but some fail.

You are finished when all the tests pass. We have implemented a few function that involve linked lists in linkedListFuncs.cpp. There is only one file you need to edit this week:

moreLinkedListFuncs.cpp contains more functions that deal with linked lists.

Step 3b: Work on the linked list functions

Working on the linked list functions below is one of the most important things you can do to prepare for the final exam.

There are 7 functions you will need to write for this lab:

  • addIntToEndOfList
  • addIntToStartOfList
  • pointerToMax
  • pointerToMin
  • largestValue
  • smallestValue
  • sum

Each one has a set of tests which can be found under its corresponding heading when you type make tests. For example, the addIntToEndOfList tests look like this to start:

./llTests 1
--------------ADD_INT_TO_END_OF_LIST--------------
PASSED: linkedListToString(list)
   FAILED: linkedListToString(list)
     Expected: [42]->[57]->[61]->[12]->null Actual: [42]->[57]->[61]->null
   FAILED: linkedListToString(list)
     Expected: [42]->[57]->[61]->[12]->[-17]->null Actual: [42]->[57]->[61]->null
PASSED: linkedListToString(empty)
   FAILED: linkedListToString(empty)
     Expected: [0]->null Actual: null
   FAILED: linkedListToString(empty)
     Expected: [0]->[19]->null Actual: null

You should replace each function stub with the correct code for the function until all of the tests for each one pass. It is recommended that you work on the functions one at a time in the order that they are presented above. That is, get all the tests to pass for addIntToStartOfList then addIntToEndOfList and so on. When all the tests pass, move on to the next step.

Step 4: Checking your work before submitting

When you are finished, you should be able to type make clean and then make tests and see the following output:

-bash-4.2$ make clean
/bin/rm -f llTests *.o
-bash-4.2$ make tests
g++ -Wall -Wno-uninitialized   -c -o llTests.o llTests.cpp
g++ -Wall -Wno-uninitialized   -c -o linkedListFuncs.o linkedListFuncs.cpp
g++ -Wall -Wno-uninitialized   -c -o moreLinkedListFuncs.o moreLinkedListFuncs.cpp
g++ -Wall -Wno-uninitialized   -c -o tddFuncs.o tddFuncs.cpp
g++ -Wall -Wno-uninitialized  llTests.o linkedListFuncs.o moreLinkedListFuncs.o tddFuncs.o -o llTests
./llTests 1
--------------ADD_INT_TO_END_OF_LIST--------------
PASSED: linkedListToString(list)
PASSED: linkedListToString(list)
PASSED: linkedListToString(list)
PASSED: linkedListToString(empty)
PASSED: linkedListToString(empty)
PASSED: linkedListToString(empty)
./llTests 2
--------------ADD_INT_TO_START_OF_LIST--------------
PASSED: linkedListToString(list)
PASSED: linkedListToString(list)
PASSED: linkedListToString(list)
PASSED: linkedListToString(empty)
PASSED: linkedListToString(empty)
PASSED: linkedListToString(empty)
./llTests 3
--------------POINTER_TO_MAX--------------
PASSED: pointerToMax(list1)
PASSED: pointerToMax(list1)
PASSED: pointerToMax(list1)->data
PASSED: pointerToMax(list1)->next->data
PASSED: pointerToMax(list2)
PASSED: pointerToMax(list2)
PASSED: pointerToMax(list2)->data
PASSED: pointerToMax(list3)
PASSED: pointerToMax(list3)
PASSED: pointerToMax(list3)->data
PASSED: pointerToMax(list4)
PASSED: pointerToMax(list4)
PASSED: pointerToMax(list4)->data
PASSED: pointerToMax(list4)->next->data
./llTests 4
--------------POINTER_TO_MIN--------------
PASSED: pointerToMin(list1)
PASSED: pointerToMin(list1)
PASSED: pointerToMin(list1)->data
PASSED: pointerToMin(list1)->next->data
PASSED: pointerToMin(list2)
PASSED: pointerToMin(list2)
PASSED: pointerToMin(list2)->data
PASSED: pointerToMin(list3)
PASSED: pointerToMin(list3)
PASSED: pointerToMin(list3)->data
PASSED: pointerToMin(list4)
PASSED: pointerToMin(list4)
PASSED: pointerToMin(list4)->data
PASSED: pointerToMin(list4)->next->data
./llTests 5
--------------LARGEST_VALUE--------------
PASSED: largestValue(list1)
PASSED: largestValue(list2)
PASSED: largestValue(list3)
PASSED: largestValue(list4)
./llTests 6
--------------SMALLEST_VALUE--------------
PASSED: smallestValue(list1)
PASSED: smallestValue(list2)
PASSED: smallestValue(list3)
PASSED: smallestValue(list4)
./llTests 7
--------------SUM--------------
PASSED: sum(list1)
PASSED: sum(list2)
PASSED: sum(list3)
PASSED: sum(list4)

-bash-4.2$

At that point, you are ready to try submitting on Gradescope.

Step 5: Turn in your code on Gradescope

Submit all the .cpp and .h files to the assignment on Gradescope called lab06 via your github repo. Then visit Gradescope and check that you have a correct score.

  • You must check that you have followed these style guidelines:
  1. Indentation is neat, consistent and follows good practice (see below)
  2. Variable name choice: variables should have sensible names. More on indentation: Your code should be indented neatly. Code that is inside braces should be indented, and code that is at the same “level” of nesting inside braces should be indented in a consistent way. Follow the examples from lecture, the sample code, and from the textbook.
  3. Practice the DRY (Don’t Repeat Yourself) principle. Once you have finished implementing your code, try to find areas that are repetitive or redundant and spend some time to optimize.

Commit and push the latest version of your code on github.

Graders will check your code to make sure it follows the coding style guidelines. Egregious violations to the coding style guidelines may be subject a score reduction for your lab grade. If you are unsure whether your code exhibits good coding style, please ask a member of the course staff during lab.

An important word about academic honesty and the gradescope system

We will test your code against other data files too—not just these. So while you might be able to pass the tests on gradescope now by just doing a hard-coded “cout” of the expected output, that will NOT receive credit.

To be very clear, code like this will pass on gradescope, BUT REPRESENTS A FORM OF ACADEMIC DISHONESTY since it is an attempt to just “game the system”, i.e. to get the tests to pass without really solving the problem.

I would hope this would be obvious, but I have to say it so that there is no ambiguity: hard coding your output is a form of cheating, i.e. a form of “academic dishonesty”. Submitting a program of this kind would be subject not only to a reduced grade, but to possible disciplinary penalties. If there is any doubt about this fact, please ask your TA and/or your instructor for clarification.

Logging out

If you are logged in remotely, you can log out using the exit command:

$ exit