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. Remember that the linked-list is a simple
implementation of the ADT List type, and ADT that we will come back to
repeatedly over the course of the quarter.
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.
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.
- 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.
.2 points: Write a function that calculates the length of a linked list
and returns it.
.4 points: Write a function that inserts a Node* into a linked list
at a specified position. This should NOT be creating a new Node, only
adding the Node* in the correct place. (Thus, the header should be
something like
Node* insert(Node* head, int pos, Node* toInsert)
since it might need to insert before the old head (pos == 0), so 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)