For this assignment you must: 1. Create a generic linked-list class (i.e., it ca

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 <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_duplicates(){
  
Node* temp=head;
int i = 0,count = 0;
//count of values in linked list
while(temp){
    count++;
    temp = temp->next;
   }
while(temp){
    for(int i = 0 ; i < count ; i++){
       if(find(i)->value == temp->value){
           remove_node(i);
           }
       }
temp = temp->next;
}
}
}

bool linked_list::equals(lined_list b){
   Node *p = this.head;
   Node *q = this.head;
   while(p && q){
       if(p->value != q->value){
           return 0;
       }
   }
   return 1;
  
}

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();
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.