Consider the LinkedList class and the Node class that we saw in lecture. The LinkedList class basically represents a singly linked list.

Now, for this lab, consider a doubly linked list, i.e. each node has a next and previous pointers to the next and previous node, respectively.

Modify the Node class to reflect this change and implement the following methods for DoublyLinkedList class:

addFirst

addLast

addAtIndex

removeFirst

removeLast

removeAtIndex

Note: We saw how to implement these methods for a singly linked list and the code is added as an attachment.

Submit a zipped file containing the Visual Studio Project folder.

use this for c++

#include <stdexcept>
using namespace std;

template<typename T>
class Node
{
public:
T element; // Element contained in the node
Node<T> *next; // Pointer to the next node

Node() // No-arg constructor
{
next = NULL;
}

Node(T element) // Constructor
{
this->element = element;
next = NULL;

}
};

template<typename T>
class LinkedList
{
public:
LinkedList();
void addFirst(T element);
void addLast(T element);
T removeFirst() throw (runtime_error);
T removeLast();
void add(int index, T element);
T removeAt(int index);

private:
Node<T> *head, *tail;
int size;
};

template<typename T>
LinkedList<T>::LinkedList()
{
head = tail = NULL;
size = 0;
}

template<typename T>
void LinkedList<T>::addFirst(T element)
{
Node<T> *newNode = new Node<T>(element);
newNode->next = head;
head = newNode;
size++;

if (tail == NULL)
tail = head;
}

template<typename T>
void LinkedList<T>::addLast(T element)
{
if (tail == NULL)
{
head = tail = new Node<T>(element);
}
else {
tail->next = new Node<T>(element);
tail = tail->next;
}

size++;
}

template<typename T>
void LinkedList<T>::add(int index, T element)
{
if (index == 0)
addFirst(element);
else if (index >= size)
addLast(element);
else
{
Node<T> *current = head;
for (int i = 1; i < index; i++)
current = current->next;
Node<T> *temp = current->next;
current->next = new Node<T>(element);
(current->next)->next = temp;
size++;
}
}

template<typename T>
T LinkedList<T>::removeFirst() throw (runtime_error)
{
if (size == 0)
throw runtime_error(“No elements in the list”);
else
{
Node<T> *temp = head;
head = head->next;
size–;
T element = temp->element;
delete temp;
return element;
}
}

template<typename T>
T LinkedList<T>::removeLast()
{
if (size == 0)
throw runtime_error(“No elements in the list”);
else if (size == 1)
{
Node<T> *temp = head;
head = tail = NULL;
size = 0;
T element = temp->element;
delete temp;
return element;
}
else
{
Node<T> *current = head;

for (int i = 0; i < size – 2; i++)
current = current->next;

Node<T> *temp = tail;
tail = current;
tail->next = NULL;
size–;
T element = temp->element;
delete temp;
return element;
}
}

template<typename T>
T LinkedList<T>::remove(int index)
{
if (index < 0 || index >= size)
throw runtime_error(“Index out of range”);
else if (index == 0)
return removeFirst();
else if (index == size – 1)
return removeLast();
else {
Node<T> *previous = head;

for (int i = 1; i < index; i++)
{
previous = previous->next;
}

Node<T> *current = previous->next;
previous->next = current->next;
size–;
T element = current->element;
delete current;
return element;
}
}

Do you need a similar assignment done for you from scratch? We have qualified writers to help you. We assure you an A+ quality paper that is free from plagiarism. Order now for an Amazing Discount!
Use Discount Code "Newclient" for a 15% Discount!

NB: We do not resell papers. Upon ordering, we do an original paper exclusively for you.