CS 14 - Lab 1

Simple Linked Lists

This lab will hopefully do two things: give you a quick refresher on pointers and also give you a little hands-on experience with linked-lists. You may want to read the chapter in Carrano (the course text) about ADT List and the "pointer implementation" of List (a linked-list).

The Assignment

Note: if you are unfamiliar with pointers, you should probably ask for help from the TA or search for a tutorial online before beginning the main portion of the lab.

Your TA will check off your work by hand at the end of the lab period. Your attendance is mandatory until that time.

2 points Attendance will be 20% of your lab grade each day. 1 point is available for attendance when the lab begins, and a second when lab ends.

7 points Create a file called "list.cc". In that file, add the following class definition:

class Node
{
public:
   int val;
   Node* next;
};

In your main function, create three objects of type Node, a, b, & c on the heap (using the new operator).
Set the val member of a to be 3, b to 8 and c to 10.
Make the next member of a point to b.
Set the next member of b & c to NULL
Write a function that takes a Node* and prints out all the values in the linked list that begins with that Node: void printList(Node* head).

.2 points: Write a function that calculates the length of a linked list and returns it: unsigned int size(Node* head).

.4 points: Write a function that inserts an int into a linked list at a specified position. This should be creating a new Node on the heap (Thus, the header should be something like

Node* insert(Node* head, int pos, int toInsert)

since it might need to insert before the old head (pos == 0) the return value is the new head of the list.

.4 points: Write a function that deletes all Nodes with a given value from a linked list and returns the new head of the list.

Node* removeVal(Node* head, int valToDelete)

.4 points: Write a function that takes in a value and a linked list and creates a new Node with that value at the end of the list, returning the new list.

Node* addToEnd(Node* head, int valToAdd)