TDT4102, Spring 2009

Exercise 11

Deadline: 24.04.2009

The objective of this exercise:

Learning the linked list data structure.

General requirements:

use Visual Studio or another IDE of your choice
use exact name and specification when given in the exercise
all files must be stored in the same location

Part 1: Linked lists (40 pt.)

In this exercise you will implement a linked list. A linked list is a list where, in addition to containing some data, each element points to the next element in the list. Use the files which are provided and implement the list.

a) The following classes are used to implement a linked list where each ListNode has a string value. Write the function implementations.

    class ListNode{

       friend class LinkedList;


    public:

        ListNode(const string & );

        string getValue() const;

        ListNode* getNext() const;


    private:

        string value;

        ListNode *next;

    };



    class LinkedList {


    public:

        LinkedList();

        ~LinkedList();

        void insertAtFront(const
string &);

        void insertAtBack(const
string &);


        bool removeFromBack(string
&);

        bool removeFromFront(string
&);

        bool isEmpty() const;

        friend ostream&
operator<<(ostream&, LinkedList&);


    private:

        ListNode *first;

        ListNode *last;

    };

bool LinkedList::isEmpty() const returns true if the list is empty.
LinkedList::LinkedList() constructor which creates a new list with firstPtr and lastPtr pointing to null.
List::~LinkedList() destructor which deletes all elements from the list to free the used memory.
void LinkedList::insertAtFront(const ListNode &value) which inserts an item at the beginning of the list.
void LinkedList::insertAtBack(const ListNode &value) which inserts an item at the back of the list.
bool LinkedList::removeFromFront(ListNode &value) which removes an item from the front of the list. The variable value should reference the removed item.
bool LinkedList::removeFromBack(ListNode &value) which removes an item from the back of the list. The variable value should reference the removed item.
ostream& operator<<(ostream&, LinkedList&) which prints the list in a readable format (Example: List contains: words that are linked together)

The linked list data structure you just created can be used to implement other data structures quite easily. Consider how you could use the LinkedList class to implement a stack or a queue. (You don't have to implement them).

Part 2: Searching the LinkedList (10 pt.)

Add a member function to search the list for a specified string value. The function should return a pointer to the first value that is found; otherwise, null should be returned.

ListNode* LinkedList::search(string&);

Hint! This problem can be solved recursively.

Part 3: Deleting nodes in the LinkedList (10 pt.)

Add a member function to remove and delete all elements from a linked list that matches a given string (the function argument).

void LinkedList::remove(string&);

Hint! This problem can be solved recursively.

Part 4: Create a template class (10 pt.)

Create a template class based on the implementation you have made so far. The purpose is to enable linked list for all data types, not just strings.

Part 5: Sorted double linked list (30 pt.)

Create template classes for a sorted double linked list (SortedDoubleLinkedList). Nodes should be inserted in sorted order based on the use of the "less than" operator (<).
Double linked means that each node has to have pointers for

next

and previous node in the list. The list should allow duplicate values.
The SortedDoubleLinkedList should have a function insert(T&) for adding new values and a function remove(T&) for removing values.

For more information about data structures, see Wikipedia's list of datastructures.