LinkedList.hpp

#include <fstream>
#include <iostream>

template <typename Type> struct NodeType {
  Type data;
  NodeType<Type> *next;
};

template <typename Type> class LinkedList {
public:
  LinkedList();
  ~LinkedList();
  size_t Size() const;
  void Add(Type const &t);
  // return true if the list is empty, otherwise return false
  bool Empty() const;
  // if value x is in the list, remove x
  void Delete(Type const &x);
  // Display the data values in the list
  std::ostream &Display(std::ostream &os = std::cout);
  auto GetRootNode() const { return root_node; }
private:
  NodeType<Type> *root_node; // pointer to the first node in the list
  NodeType<Type> *last_node; // pointer to the first node in the list
  size_t size;
};

template <typename T> std::ostream &LinkedList<T>::Display(std::ostream &os) {
  auto n = root_node;
  while (n) {
    os << n->data << " ";
    n = n->next;
  }
  return os;
}

template <typename T>
LinkedList<T>::LinkedList() : root_node{nullptr}, last_node{nullptr}, size{} {}

template <typename T> LinkedList<T>::~LinkedList() {
  NodeType<T> *temp = root_node;
  while (root_node) {
    temp = root_node->next;
    delete root_node;
    root_node = temp;
  }
}

template <typename T> void LinkedList<T>::Add(T const &elem) {
  NodeType<T> *new_node{new NodeType<T>{elem, nullptr}};
  if (!root_node) {
    root_node = last_node = new_node;
  } else {
    last_node->next = new_node;
    last_node = last_node->next;
  }
  ++size;
}

template <typename T> bool LinkedList<T>::Empty() const { return size == 0; }

template <typename T> size_t LinkedList<T>::Size() const { return size; }

template <typename T> void LinkedList<T>::Delete(T const &elem) {
  if (Empty())
    return;
  if (root_node->data == elem) {
    auto next_node = root_node->next;
    delete root_node;
    root_node = next_node;
  } else {
    auto current_node = root_node->next;
    if (current_node->data == elem) {
      auto node_to_delete = current_node;
      root_node->next = current_node->next;
      delete node_to_delete;
    } else {
      auto prev_node = current_node;
      current_node = current_node->next;
      while (current_node && current_node->data != elem) {
        prev_node = current_node;
        current_node = current_node->next;
      }
      if (!current_node)
        return;
      if (last_node == current_node) {
        last_node = prev_node;
      }
      prev_node->next = current_node->next;
      delete current_node;
    }
  }
  --size;
}

unorderedlist.hpp

// unorderedLinkedList.h

#pragma once

#ifndef H_UnorderedLinkedList

#define H_UnorderedLinkedList

#include "linkedList.hpp"

using namespace std;
template<typename Type>
using nodeType = NodeType<Type>;

template <class Type>

class unorderedLinkedList : public LinkedList<Type>
{
public:
  // Declartion of search method
  bool search(const Type &searchItem) const;

  // Declartion of insertFirst method

  void insertFirst(const Type &newItem);

  // Declartion of insertLast method

  void insertLast(const Type &newItem);

  // Declartion of deleteNode method

  void deleteNode(const Type &deleteItem);
};

// Implementation of search method

template <class Type>
bool unorderedLinkedList<Type>::search(const Type &searchItem) const
{
    using LinkedList<Type>::root_node;
    for ( auto beg = root_node; beg; beg = beg->next ) {
        if ( beg->data == searchItem ) return true;
    }
    return false;
}

// Declaration of insertFirst method

template <class Type>
void unorderedLinkedList<Type>::insertFirst(const Type &newItem)
{
    using LinkedList<Type>::root_node;
    using LinkedList<Type>::size;
    nodeType<Type> *newNode{ new nodeType<Type>{ newItem, root_node } };
    root_node = newNode;
    ++size;
}

// Declaration of insertLast method

template <class Type>
void unorderedLinkedList<Type>::insertLast(const Type &newItem)
{
    LinkedList<Type>::Add( newItem );
}

// Declaration of deleteNode method

template <class Type>
void unorderedLinkedList<Type>::deleteNode(const Type &deleteItem)
{
    LinkedList<Type>::Delete( deleteItem );
}

#endif