Close Lab 5: Practicing LinkedList The objective of this close lab is to practic
ID: 3572545 • Letter: C
Question
Close Lab 5: Practicing LinkedList
The objective of this close lab is to practice linked list.
Assignment:
Complete the definition of the template linklist class below,
template <typename T>
class LinkList
{ private:
class Node
{
public:
T info;
Node *next;
};
typedef Node *nodePtr;
public:
LinkList(); //constructor
LinkList(const LinkList<T> & orig); //copy constructor
bool empty(); //determine if the LinkList is empty
T Front(); // returns item at front of LinkList
T Back(); // returns item at back of LinkList
Void PrintSecond();//print the content of the second node
void Push_front(const T & item);
//add item at the begining of LinkList
void pop_back(); //remove the last item of the LinkList
// Search function to search a given value and return the count
// of the given value
_______________________________________________________
// Pop_front function to remove the first item of the LinkList.
___________________________________________________________
// push_back function to add an item at the end of the LinkList
____________________________________________________________
private:
// node pointer which points to the front(first node)
____________________________________________________
};
Complete the implementation of the following member functions: Search(), Front(), Back(), PrintSecond(), Pop_front() and Push_back(), and then write a test driver to fully test your linklist.
Explanation / Answer
#include <iostream>
using namespace std;
template<class T>
class Node
{
public:
template<class>friend class MyList;
T element;
Node* prev;
Node* next;
Node (T e)
{
element = e;
prev = next = NULL;
}
};
template <class T>
class MyList
{
Node<T> *head, *tail;
int count;
public:
MyList();
~MyList();
void push_back(T data);
void push_front(T data);
void pop_front();
void pop_back();
void clear();
T front();
T back();
int size()
{
int count = 0;
Node<T> *cursor = head;
while(cursor != NULL)
{
cursor = cursor->next;
count++;
}
return count;
}
void reverse();
void sort();
void unique();
T operator[] (int index);
};
template<class T>
MyList<T>::MyList()
{
int count = 0;
head = tail = NULL;
}
template<class T>
MyList<T>::~MyList()
{
Node<T>* cursor = head;
while (cursor != NULL)
{
Node<T>* next_ptr = cursor->next;
delete cursor;
cursor = next_ptr;
}
}
template<class T>
T MyList<T>::operator[] (const int index)
{
Node<T> *cursor = this->head;
for(int x = 0; x < index; x++)
{
cursor = cursor->next;
}
return cursor->element;
}
template<class T>
void MyList<T>::push_back(T data)
{
if(head == NULL)
{
head = new Node<T>(data);
}
else
{
Node<T> *cursor = head;
while(cursor->next != NULL)
{
cursor = cursor->next;
}
cursor->next = new Node<T>(data);
}
}
template<class T>
void MyList<T>::push_front(T data)
{
Node<T> *cursor = new Node<T>(data);
cursor->element = data;
cursor->next = head;
head = cursor;
if(tail == NULL)
{
tail = cursor;
}
}
template<class T>
void MyList<T>::pop_front()
{
Node<T> *cursor = head;
head = head->next;
delete cursor;
if(head == NULL)
{
tail = NULL;
}
}
template<class T>
void MyList<T>::pop_back()
{
Node<T> *cursor = head;
while(cursor->next)
{
cursor = cursor->next;
}
delete cursor->next;
cursor->next = NULL;
}
template<class T>
void MyList<T>::clear()
{
head = NULL;
}
template <class T>
T MyList<T>::front()
{
return head->element;
}
template<class T>
T MyList<T>::back()
{
return tail->element;
}
template<class T>
void MyList<T>::reverse()
{
if(head == NULL)
return;
Node<T> *prev = NULL, *cursor = NULL, *next = NULL;
cursor = head;
while(cursor != NULL)
{
next = cursor->next;
cursor->next = prev;
prev = cursor;
cursor = next;
}
head = prev;
}
template<class T>
void MyList<T>::sort()
{
Node<T> *cursor = NULL;
while(cursor != head)
{
Node<T> *temp, *swap;
swap = head;
while( swap->next != cursor )
{
if(swap->element > swap->next->element)
{
Node<T> *swap2 = swap->next;
swap->next = swap2->next;
swap2->next = swap;
if(swap == head)
{
head = swap2;
swap = swap2;
}
else
{
swap = swap2;
temp->next = swap2;
}
}
temp = swap;
swap = swap->next;
}
cursor = swap;
}
}
template<class T>
void MyList<T>::unique()
{
sort();
Node<T> *ptr1, *ptr2, *duplicate;
ptr1 = head;
while(ptr1 != NULL && ptr1->next != NULL)
{
ptr2 = ptr1;
while(ptr2->next != NULL)
{
if(ptr1->element == ptr2->next->element)
{
duplicate = ptr2->next;
ptr2->next = ptr2->next->next;
(duplicate);
}
else
{
ptr2 = ptr2->next;
}
}
ptr1 = ptr1->next;
}
}
template <class T>
void print(MyList<T>& l)
{
for (int x = 0; x < l.size(); x++)
cout << l[x] << " ";
cout << endl;
}
int main()
{
MyList<string> l;
cout << "-- push_front push_back test --" << endl;
l.push_back("one");
l.push_back("two");
l.push_back("three");
l.push_back("four");
l.push_back("five");
l.push_back("six");
l.push_front("zero");
l.push_front("neg-one");
l.push_back("six");
print(l);
cout << "-- pop_front pop_back test 1 --" << endl;
l.pop_front();
l.pop_back();
print(l);
cout << "-- clear test (should be blank) --" << endl;
l.clear();
print(l);
cout << "-- front back test 1 --" << endl;
l.push_back("apple");
l.push_back("orange");
l.push_back("happy meal");
l.push_front("whopper");
cout << l.front() << " " << l.back() << endl;
cout << "-- front back test 2 --" << endl;
l.push_back("finance");
l.push_back("google");
l.push_back("green");
print(l);
cout << "-- reverse test --" << endl;
l.reverse();
print(l);
cout << "-- sort test --" << endl;
l.sort();
print(l);
cout << "-- unique test --" << endl;
l.push_back("aapl");
l.push_back("aapl");
l.push_front("goog");
l.push_back("goog");
l.push_back("happy meal");
l.unique();
print(l);
cout << "-- pop_front pop_back test 2 --" << endl;
l.pop_back();
l.pop_front();
l.pop_back();
print(l);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.