Make a list First thing we need for a linked list is a node

Make a list

First thing we need for a linked list is a node class. It needs a data member,use string for this, and a pointer to the same class (often called link or next). For this we will use public data members. Might as well put in a constructor that lets you set data and sets link to NULL, for convenience.

We are going to start writing a set of functions to work with a linked list. Important Note! The node class that we just made represents one node in the list, not the whole list. Therefore, it is not appropriate to add functions that work with the whole list into that class. In this lab, we\'ll just use global functions. Later, we\'ll look at creating a List class that uses the node class.

Implement a print function (not method) that takes a pointer to a list of nodes and traverses the list, printing all the values. Call it in main to verify that it works.

Implement a find function that takes a pointer to a list of nodes and a string to find, and returns True if that string is in the list, False otherwise. Verify with test cases in main that it works for all relevant cases: empty list, first item,last item,middle item,item that doesn\'t exist.

You should be using a function that can append a new value to a list of any size.

Write another function (not method) that takes a pointer to a list and a new value to append to the end of the list. It\'ll follow the same generic traversal approach, you need to figure out: where to stop,the right condition for stopping there, what to do at each node (if anything), what to do when you stop (if anything)

Don\'t forget to test your append function for all the relevant cases: list with 1 item, list with more than 1 item, empty list

Solution

#include <string>

#include <cassert>

#include <vector>

#include <functional>

#include <iostream>

namespace ds {

struct node_t{

node_t* next = nullptr;

std::string data;

  

node_t(const std::string& data) : data(data), next(nullptr){

  

}

  

virtual ~node_t(){

if(next != nullptr){

delete next;

next = nullptr;

}

}

};

  

/*

   */

node_t* create_list(const std::string& data){

return new node_t(data);

}

  

/* add element to list or create a list with the element

   */

node_t* add_or_create_list(node_t*& head, const std::string& data){

if(head == nullptr){

head = create_list(data);

return head;

}

else{

node_t* curr = head;

while(curr->next!=nullptr)

curr = curr->next;

curr->next = new node_t(data);

return curr->next;

}

}

  

  

/* check if element exists in list

   */

bool find_in_list(const node_t* head, const std::string& data){

while(head!=nullptr){

if(head->data==data){

return true;

}

head = head->next;

}

return false;

}

  

void traverse_list(const node_t* head, std::function<void(const std::string&)> fn){

while(head!=nullptr){

fn(head->data);

head = head->next;

}

}

  

void print_list(const node_t* head){

traverse_list(head, [](const std::string& data){

std::cout << data << \"\\t\";

});

}

  

  

void test_list(){

node_t* ll = nullptr;

assert(find_in_list(ll, \"lily\")==false);

  

/* empty list verification*/

std::vector<int> xs = {1,11,191, 87, 78, 98};

  

for(auto x: xs){

add_or_create_list(ll, std::to_string(x));

}

  

/* first item*/

assert(find_in_list(ll, std::to_string(xs[0]))==true);

/* middle item*/

assert(find_in_list(ll, std::to_string(xs[xs.size()/2]))==true);

/* last item*/

assert(find_in_list(ll, std::to_string(xs[xs.size()-1]))==true);

assert(find_in_list(ll, \"alpha\")==false);

      

print_list(ll);

}

  

}

int main(){

ds::test_list();

}