I\'m trying to write a C++ DoublyLinkedList template template<class T> class Dou
ID: 641717 • Letter: I
Question
I'm trying to write a C++ DoublyLinkedList template
template<class T>
class DoublyLinkedList {
void insertAfter(T target, T newData); //must find the (first) instance of T in the list and place the new value after it.
void insertAtFront(T newData); //inserts at the front of the list, replacing the head
void insertAtBack(T newData); //inserts at the end of the list
private:
struct node {
node* next;
node* prev;
T data;
};
node* head;
node* tail;
};
If I have access to these data types, how do I write those three functions?
Explanation / Answer
#include <iostream>
using namespace std;
template<class T>
class DoublyLinkedList {
private:
struct node{
node* next;
node* prev;
T data;
};
node* head;
node* tail;
public:
DoublyLinkedList(){
head = NULL;
tail = NULL;
}
void print(){
node *temp = head;
while(temp != NULL){
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
void insertAfter(T target, T newData); //must find the (first) instance of T in the list and place the new value after it.
void insertAtFront(T newData); //inserts at the front of the list, replacing the head
void insertAtBack(T newData); //inserts at the end of the list
};
template<class T>
void DoublyLinkedList<T>::insertAfter(T target, T newData){
node *temp = new node;
temp->next = NULL;
temp->prev = NULL;
temp->data = newData;
node *temp1 = head;
while(temp1 != NULL && temp1->data != target){
temp1 = temp1->next;
}
if(temp1 == NULL){
insertAtBack(newData);
}
else{
temp->next = temp1->next;
temp->prev = temp1;
if(temp->next != NULL){
temp->next->prev = temp;
}
temp1->next = temp;
}
}
template<class T>
void DoublyLinkedList<T>::insertAtFront(T newData){
node *temp = new node;
temp->next = NULL;
temp->prev = NULL;
temp->data = newData;
if(head == NULL){
head = temp;
tail = temp;
}
else{
temp->next = head;
head->prev = temp;
head = temp;
}
}
template<class T>
void DoublyLinkedList<T>::insertAtBack(T newData){
node *temp = new node;
temp->next = NULL;
temp->prev = NULL;
temp->data = newData;
if(tail == NULL){
head = temp;
tail = temp;
}
else{
tail->next = temp;
temp->prev = tail;
tail = temp;
}
}
int main(){
DoublyLinkedList<int> Lst;
Lst.insertAtFront(2);
Lst.insertAtFront(3);
Lst.insertAtFront(5);
Lst.insertAtBack(6);
Lst.insertAtBack(7);
Lst.insertAfter(3, 9);
Lst.print();
return 0;
}