1. Consider the Linked list discussed in the class (must use the code discussed in class, provided in the textbook any changes made to it must be documented and explained).

template

class Node

{

public:

Node();

Node(T value, Node* nextNode);

T data;

Node* next;

};

template

class LinkedList

{

public:

LinkedList();

Node* getHead() const; // return the head pointer.

Node* getTail() const; // returns the tail pointer.

void ListAppend(T value); // inserts an element at the end of the list.

void listPrepend(T value); //inserts a n element at the head of the list.

void insertAfter(Node* curNode, T value); // Insert value after the curNode

void removeAfter(Node* curNode); // remove Node after CurNode

void removeHead(); // Removes the first element.

void removeTail(); // removes the last element.

void printList() const; // print the elements of the linked list.

private:

Node* head;

Node* tail;

};

Add the following functions to the class LinkedList (No need to run your code, unless you want to. The code must be syntactically correct.)

1. getLength(): returns the number of items in the LinkedList.
2. search(T element) : searches for the element in the LinkedList, returns a pointer to the Node containing the element if found, otherwise returns NULL.

1. Define the Node class for a Doubly linked list. Define a doubly linked list class that uses this Node. Implement the node as well as the Doubly Linked list classes. In the doubly linked list class include a default constructorand functions append, prepend and print that displays all the elements of the doubly linked list. Implement your classes and write a main function in which you populate a doubly linked list by appending and prepending then print the list.