For this assignment you must: 1. Create a generic linked-list class (i.e., it ca
ID: 670281 • Letter: F
Question
For this assignment you must:
1. Create a generic linked-list class (i.e., it can handle any data type) named. Assume each list only will contain one data type for this assignment.
2. This class should contain all the necessary functions for accessing and modifying data. If you do not use it then you do not need to write it, thus you may have a different set of functions from your classmates.
3. Implement the following functions (note, these are not the prototypes):
i. insert_node()// insert to any index
ii. remove_node()// remove from any index iii. find() // find first instance of object
iv. remove_duplicates()// removes all duplicates from list
v. equals()// compares two lists
vi. list()// neatly list the node information to the terminal
vii. split_merge()// split list at given index and append tail section to head section (e.g., 4 5 6 1 2 3 = 1 2 3 4 5 6 if index was 3)
4. Write a main function that highlights all of these functions working (please take care with the formatting of the terminal output).
I have finished insert_node(), remove_node), find(), and list(). This is my code far:
____________________________________________________________________
Linked_list.cpp
#include <iostream>
#include <cstddef>
using std::cout;
using std::endl;
/* definition of the list node class */
class node
{
friend class linked_list;
private:
int _value;
node *_next_node;
public:
node(void) : _next_node(NULL){ }
node(int val) : _value(val), _next_node(NULL){ }
node(int val, node* next) : _value(val), _next_node(next) { }
/* accessors */
int get_value() { return _value; }
node * getNext(){ return _next_node; }
};
/* definition of the linked list class */
class linked_list
{
private:
node *_head;
node *_tail;
public:
linked_list();
linked_list(int val);
void print();
void insert_node(node * n, int _value);
void append_node(node * n);
void append_node_to_head(node * n);
node* find(int pos);
void remove_node(int x);
};
linked_list::linked_list()
{
_head = _tail = NULL;
}
linked_list::linked_list(int val)
{
_head = new node(val);
_tail = _head;
}
void linked_list::print()
{
node * n = _head;
// Check to see if empty
if (_head == NULL)
{
cout << "The list is empty" << endl;
return;
}
cout << "Linked List: ";
while (n != NULL)
{
cout << n->_value;
n = n->_next_node;
cout << " ";
}
cout << endl;
}
node* linked_list::find(int pos){
node *p = _head;
while (pos--){
if (p != NULL)
p = p->_next_node;
else
return NULL;
}
return p;
}
void linked_list::append_node(node * n)
{
// Check if the node is null
if (n == NULL)
{
cout << "The node to append is NULL, not appending node" << endl;
return;
}
_tail->_next_node = n;
_tail = n;
}
void linked_list::insert_node(node * n, int _value){
if (n != NULL){
n->_next_node = new node(_value, n->_next_node);
}
}
void linked_list::append_node_to_head(node * n)
{
// Check if the node is null
if (n == NULL)
{
cout << "The node to append is NULL, not appending node" << endl;
return;
}
//set new node to point to current head
n->_next_node = _head;
//make our new node the head
_head = n;
}
void linked_list::remove_node(int x){
node * n = NULL;
node * p = NULL;
if (_head->_value == x ){
p = _head;
_head = p->_next_node;
delete p;
return;
}
n = _head;
p = _head->_next_node;
while (p != NULL){
if (p->_value == x){
n->_next_node = p->_next_node;
if (p == _tail){
_tail = n;
}
delete p;
return;
}
n = p;
p = p->_next_node;
}
}
int main(int argc, const char * argv[])
{
linked_list list(42);
cout << "Created an empty list named list." << endl;
/* output the result */
cout << "list:" << endl;
list.print();
//create new node
node * n = new node(10);
//append the node to list
list.append_node(n);
cout << "list:" << endl;
list.print();
//create new node
n = new node(10);
//append the node to head of list
list.append_node_to_head(n);
cout << "list:" << endl;
list.print();
//insert node
list.insert_node(list.find(1), 4);
cout << "list:" << endl;
list.print();
//remove node value
list.remove_node(4);
cout << "list:" << endl;
list.print();
Explanation / Answer
#include <iostream>
#include <set>
using namespace std;
template<class T>
class Node
{
public:T data;
Node<T> * next;
Node<T>(const T& d):data(d),
next() {}
Node<T>(const Node<T>& copyNode) : data(copyNode.data),
next() {}
private:
Node<T>& operator=(const Node<T>&);
};
template<class T>
class LinkedList
{
public:
Node<T> * head;
Node<T> * tail;
LinkedList(const LinkedList& LL);
LinkedList& operator=(LinkedList byValList);
LinkedList(): head(NULL), tail(NULL) {}
LinkedList(Node<T> * newNode) : head(newNode), tail(newNode) {}
LinkedList();
static LinkedList<int> sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2);
void insertToTail(T val);
void insertToHead(T val);
void print();
void printBackwards();
};
template<class T>
LinkedList<T>::LinkedList(const LinkedList<T>& LL) : head(NULL), tail(NULL)
{
const Node<T> * curr = LL.head;
if (!head && curr)
{
head = new Node<T>(curr->data);
tail = head;
curr = curr->next;
}
while (curr)
{
Node<T> * newNode = new Node<T>(curr->data);
tail->next = newNode;
tail = newNode;
curr = curr->next;
}
}
template<class T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList byValList)
{
std::swap(head, byValList.head);
return *this;
}
template<class T>
LinkedList<T>::~LinkedList()
{
Node<T> * curr = head;
while (head)
{
head = head->next;
delete curr;
curr = head;
}
}
template<class T>
void LinkedList<T>::insertToTail(T val)
{
Node<T> * newNode = new Node<T>(val);
if (tail == NULL)
{
newNode->next = tail;
tail = newNode;
head = newNode;
return;
}
tail->next = newNode;
tail = tail->next;
}
template<class T>
void LinkedList<T>::insertToHead(T val)
{
Node<T> * newNode = new Node<T>(val);
newNode->next = head;
head = newNode;
if (head->next == NULL)
tail = newNode;
}
template<class T>
void LinkedList<T>::print()
{
Node<T> * curr = head;
while (curr)
{
cout<<curr->data<<" --> ";
curr = curr->next;
}
cout<<"NULL"<<endl;
}
template<class T>
void LinkedList<T>::printBackwards()
{
Node<T> * curr;
LinkedList ReversedList(new Node<T>(head->data));
curr = head->next;
while (curr)
{
ReversedList.insertToHead(curr->data);
curr = curr->next;
}
curr = ReversedList.head;
while (curr)
{
cout<<curr->data<<" --> ";
curr = curr->next;
}
cout<<"NULL ";
}
template<class T>
LinkedList<int> LinkedList<T>::sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2)
{
Node<T>* curr1 = LL1.head;
Node<T>* curr2 = LL2.head;
LinkedList<int> ResultList;
int newData;
int carry = 0;
while (curr1 && curr2)
{
newData = (curr1->data + curr2->data + carry) % 10;
carry = (curr1->data + curr2->data + carry) / 10;
ResultList.insertToTail(newData);
curr1 = curr1->next;
curr2 = curr2->next;
}
while (curr1 || curr2)
{
if (carry)
{
if (curr1)
ResultList.insertToTail(curr1->data + carry);
if (curr2)
ResultList.insertToTail(curr2->data + carry);
carry = 0;
continue;
}
if (curr1)
{
ResultList.insertToTail(curr1->data);
curr1 = curr1->next;
}
if (curr2)
{
ResultList.insertToTail(curr2->data + carry);
curr2 = curr2->next;
}
}
return ResultList;
}
int main()
{
LinkedList<int> LL1(new Node<int>(7));
LL1.insertToTail(1);
LL1.insertToTail(6);
LL1.insertToTail(5);
LL1.insertToTail(4);
LinkedList<int> LL2(new Node<int>(5));
LL2.insertToTail(9);
LL2.insertToTail(2);
LinkedList<int> LL = LL1.sumLists(LL1, LL2);
LL.print();
LL2.print();
LL = LL2;
LL.print();
LL2.print();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.