Linked List Class Enhancements Modify the List class that was completed in class
ID: 3690837 • Letter: L
Question
Linked List Class Enhancements
Modify the List class that was completed in class (on 3/16) to include the following additional member
functions:
• void insert(const T& item, const T& location) – Inserts a new node in the linked list with value
item just before the first occurrence of the node with the value location. If no node is value with
the value location, append the new item to the end of the list.
• void remove(const T& item) – Remove the first occurrence of the node with value item from
the list. If there is no node with value item in the list, do nothing.
• void remove_all(const T& item) – Remove all occurrences of nodes with value item from the
list.
Include a main program that tests your modifications to the class. Submit both your test program and
your modified list.h file.
#ifndef LIST_H
#define LIST_H
#include <iostream>
class ListRangeException {};
template <typename T>
class ListNode {
public:
T data;
ListNode<T>* next;
};
template <typename T>
class List {
protected:
ListNode<T>* head;
public:
List() { head = NULL; }
~List() { clear(); }
void append(const T& item);
void clear() { while (head) remove(0); }
T get(int location) const;
void insert(const T& item, int location);
void move(int location, int newLocation);
void remove(int location);
void print() const;
int size() const;
T& operator[] (int location);
void traverse(void(*f)(T&));
};
template <typename T>
void List<T>::append(const T& item) {
ListNode<T>* p = new ListNode<T>;
p->data = item;
p->next = NULL;
if (!head)
head = p;
else {
ListNode<T>* q = head;
while (q->next)
q = q->next;
q->next = p;
}
}
template <typename T>
void List<T>::insert(const T& item, int location) {
if (location < 0 || location >= size())
throw ListRangeException();
if (location == 0) {
ListNode<T>* p = new ListNode<T>;
p->data = item;
p->next = head;
head = p;
}
else {
ListNode<T>* p = head;
for (int i = 0; i < location - 1; i++)
p = p->next;
ListNode<T>* q = new ListNode<T>;
q->data = item;
q->next = p->next;
p->next = q;
}
}
template <typename T>
void List<T>::print() const {
// ListNode<T>* p = head;
// while (p) {
// std::cout << " " << p->data;
// p = p->next;
// }
for (ListNode<T>* p = head; p; p = p->next)
std::cout << " " << p->data;
std::cout << std::endl;
}
template <typename T>
void List<T>::remove(int location) {
if (location < 0 || location >= size())
throw ListRangeException();
if (!location) {
ListNode<T>* p = head;
head = head->next;
delete p;
}
else {
ListNode<T>* p = head;
for (int i = 0; i < location - 1; i++)
p = p->next;
ListNode<T>* q = p->next;
p->next = q->next;
delete q;
}
}
template <typename T>
int List<T>::size() const {
int count = 0;
for (ListNode<T>* p = head; p; p = p->next)
count++;
return count;
}
template <typename T>
T& List<T>::operator[] (int location) {
if (location < 0 || location >= size())
throw ListRangeException();
ListNode<T>* p = head;
for (int i = 0; i < location; i++)
p = p->next;
return p->data;
}
template <typename T>
void List<T>::traverse(void(*f)(T&)) {
ListNode<T>* p = head;
while (p) {
f(p->data);
p = p->next;
}
}
#endif
Explanation / Answer
I've written code for all three functions. First try to understand login by reading comments.
template <typename T>
void List<T>::insert(const T& item, const T& location) {
ListNode<T>* p = head;
//when list is empty.
if(p==NULL)
{
ListNode<T>* q = new ListNode<T>;
q->data = item;
q->next = NULL;
head = q;
return;
}
//case: when value of 1st node is equal to 'location'.
if(p->data == location)
{
ListNode<T>* q = new ListNode<T>;
q->data = item;
q->next = p;
head = q;
return;
}
//case: when node with value 'location' lies after 1st node.
while((p->next != NULL))
{
if(p->next->data == location)
{
ListNode<T>* q = new ListNode<T>;
q->data = item;
q->next = p->next;
p->next = q;
return;
}
p = p->next;
}
// case: when no node with value 'location' exists. Appending node with value
// item at end of list.
if(p->next == NULL)
{
ListNode<T>* q = new ListNode<T>;
q->data = item;
q->next = NULL;
p->next = q;
return;
}
}
//function to remove 1st instance of node with value 'item'.
template <typename T>
void List<T>::remove(const T& item) {
ListNode<T>* p = head;
//if list is empty
if(p==NULL)
return;
//if first node have value equal to 'item'.
if(p->data == item)
{
head = p->next;
delete p;
return;
}
//finding node with value 'item' and deleting it.
while(p->next != NULL)
{
if(p->next->data == item)
{
ListNode<T>* q = p->next;
p->next = q->next;
delete q;
return;
}
}
}
template <typename T>
void List<T>::remove_all(const T& item)
{
ListNode<T>* p = head;
//if list is empty
if(p==NULL)
return;
//if first node have value equal to 'item'.
while(p != NULL && p->data == item)//notice while, in case there are more than one node with value item in beginning of list
{
ListNode<T>* q = p;
head = q->next;
p=head;
delete q;
}
//finding node with value 'item' and deleting it if it exists after 1st node.
while(p->next != NULL)
{
if(p->next->data == item)
{
ListNode<T>* q = p->next;
p->next = q->next;
delete q;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.