In Class Exercise

In Class Exercise:

Get in groups of 3-ish

Instructions:

NOTE: you may have problems just unzipping the files and sticking them in a project in eclipse. If so, try creating a new project, creating each file, and then copying the contents of the files I’ve given you into those files

You’re creating a circular linked lists for the game Duck Duck Goose, in which, like the game, one goes around the list saying, “duck, duck”, and then eliminating the goose (in other words, removing every third node from the list.

First: a circular linked list is a linked list with one difference – the last’s next pointer holds the address of the first node, so, while the linked list still has a first and a last pointer, you can actually find the first node from the last node (in other words, the list is circular). This means that whenever you create a new last node, you must make sure that last node points to the first node. Equally, when you add a new first node, you must make sure the last node points to the new first node. Otherwise the linked list is exactly the same as any other linked list.

For this exercise, you’ll be editing the CLL.cpp file to fill in the methods as defined below:

void CLL::push(char data) { // You write - if the size is 0, add a first node in the linked list

// by calling addFirst. Otherwise add a new node to the end of the linked list. Note that this

// linked list is circular, so you must make the last node's next pointer point to the first node.

}

void CLL::addFirst(char data) {

// you write - add the very first node to the linked list

}

void CLL::addAtFront(char data) {

// you write - if the size of the linked list is 0, add a first node by calling addFirst.

//Otherwise add a new node to the beginning of the list

//Since this linked list is circular, you must make the last node now point to this new node

//you just added to the front of the linked list

}

void CLL::removeNext(SNode *n) {

// Longest method - given node n, remove the next node in the linked list.

// you have 4 conditions:

//1: there's only one node in the list, in which case you delete that node and set the size to 0

//2: n's next node is a last node, in which case n becomes the new last node and n's next must point

//to the first node in the list (remember to decrease the size of the list)

//3: n's next node is the first node in the list (i.e., n is the last node in the list), in which case

//n's next becomes first's next, first is deleted, and first becomes n's next (again, remember

//to decrease the size)

//4: n is just some node in the middle of the list, in which case you should create a tmp node to point

// to n's next, then set n's next to n's next's next, and then delete the tmp node (again, decrease

//size).

}

void CLL::printList(){

// print out the data in each node in the linked list, starting at the first node.

}

You will also be modifying the file DuckDuckGoose.cpp to fill in the methods as defined below:

voidDuckDuckGoose::MakeListEnd() {

// create a linked list by pushing every character in arr1 to the end of linked list clist (the field in

// DuckDuckGoose

}

voidDuckDuckGoose::MakeListBoth() {

// create a linked list by alternately pushing and adding at front every character in arr2 onto the linked list

// clist (so if i%0 == 0, push arr2[i], and otherwise addAtFront arr2[i])

}