C Code Consider the LinkedList class and the Node class that

C++ Code

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.

C++ Code

***********************************************************************************************

***********************************************************************************************

C++ Code

Solution

#include <stdio.h>
#include <iostream>

using namespace std;

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

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

template <class T>
class LinkedList
{
public:
LinkedList();
void addFirst(T element);
void addLast(T element);
T removeFirst() ;
T removeLast();
void addAtIndex(int index, T element);
T removeAtIndex(int index);
void traverseList();

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

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

template <class T>
void LinkedList<T>::addFirst(T element)
{
Node<T> *newNode = new Node<T>(element);
newNode->next = head;
if(head != NULL) {
head->previous = newNode;
}
newNode->previous = NULL;
head = newNode;
size++;

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

template <class 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 <class T>
void LinkedList<T>::addAtIndex(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 <class T>
T LinkedList<T>::removeFirst()
{
if (size == 0)
exit(1);
else
{
Node<T> *temp = head;
head = head->next;
size--;
T element = temp->element;
delete temp;
return element;
}
}

template <class T>
T LinkedList<T>::removeLast()
{
if (size == 0)
exit(1);
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 <class T>
T LinkedList<T>::removeAtIndex(int index)
{
if (index < 0 || index >= size)
exit(1);
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;
}
}

template <class T>
void LinkedList<T>::traverseList()
{
Node<T> *temp = head;
while(temp !=NULL) {
   cout<<temp->element<<\"\ \";
   temp = temp->next;
}
  
}

int main() {
   LinkedList<int> *myList = new LinkedList<int>();
   myList->addFirst(10);
   myList->addFirst(20);
   myList->addLast(30);
   myList->removeAtIndex(1);
   myList->traverseList();
   delete myList;
}