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;

}

}

Use Discount Code "Newclient" for a 15% Discount!

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

WhatsApp us