Question

Could you check/edit my code?

Design and implement your own linked list class to hold a sorted list of integers in ascending order. The class should have member function for inserting an item in the list, deleting an item from the list, and searching the list for an item. Note: the search function should return the position of the item in the list (first item at position 0) and -1 if not found. In addition, it should member functions to display the list, check if the list is empty, and return the length of the list. Be sure to have a class constructor, a class destructor, and a copy constructor for deep copy. Demonstrate your class with a driver program (be sure to include the following cases: insertion at the beginning, end, and inside the list, deletion of first item, last item, and an item inside, searching for an existing/non-existing item, and modifying a list that was initialized to an existing list).

#ifndef LIST_H
#define LINKEDLIST_H

template <class T>
class ListNode
{
public:
   //Node value
   T value;
   //Pointer to the next node
   ListNode<T> *next;
   //Constructor
   ListNode(T nodeValue)
   {
       value = nodeValue
           next = nullptr;
   }
};
//LinkedList class
template <class T>
class LinkedList
{
private:
   //List head pointer
   ListNode<T> *head;
public:
   //Constructor
   LinkedList()
   {
       head = nullptr;
   }
   //Destructor
   ~LinkedList();

   //Linked list operations
   void appendNode(T);
   void insertNode(T);
   void deleteNode(T);
   void displayList() const;
};
template <class T>
void LinkedList<T>::appendNode(T newValue)
{
   //To point to a new node
   ListNode<T> *newNode;
   //To move through the list
   ListNode<T> *nodePtr;
   //Allocate a new node and store new Value there.
   newNode = new ListNode<T>(newValue);
   if (!head)
       head = newNode;
   else
   {
       //Initialize nodePtr to head of list.
       nodePtr = head;
       //Find the last node in the list
       while (nodePtr->next)
           nodePtr = nodePtr->next;
       //Insert newNode as the last node.
       nodePtr->next = newNode;
   }
}
template <class T>
void LinkedList<T>::displayList() const
{
   //To move through the list
   ListNode<T> *nodePtr;
   //Position nodePtr at the head of the list.
   nodePtr = head;
   //Traverse the list
   while (nodePtr)
   {
       //Value of this node
       cout << nodePtr->value << endl;
       //Move to the next node.
       nodePtr = nodePtr->next;
   }
}
template <class T>
void LinkedList<T>::insertNode(T newValue)
{
   ListNode<T> *newNode;
   //traverse the list
   ListNode<T> *nodePtr;

   ListNode<T> *previousNode = nullptr;
   newNode = new ListNode<T>(newValue);

   if (!head)
   {
       head = newNode;
       newNode->next = nullptr;
   }
   else
   {
       nodePtr = head;
       previousNode = nullptr;

       //Skip all nodes whose value is less than newValue.
       while (nodePtr != nullptr && nodePtr && nodePtr->value < newValue)
       {
           previousNode = nodePtr;
           nodePtr = nodePtr->next;
       }
       //If the new node is to be the 1st in the list, then insert it before all other nodes
       if (previousNode == nullptr)
       {
           head = newNode;
           newNode->next = nodePtr;
       }
       else {
           previousNode->next = newNode;
           newNode->next = nodePtr;
       }
   }
}
template <class T>
void LinkedList<T>::deleteNode(T searchValue)
{
   //To traverse the list
   ListNode<T> *nodePtr;
   //To point to the previous node
   ListNode<T> *previousNode;
   //There is no need to do anything if the list is empty
   if (!head)
       return;

   //Determine if the first node is one
   if (head->value == searchValue)
   {
       nodePtr = head->next;
       delete head;
       head = nodePtr;
   }
   else
   {
       //Initialize nodePtr to head of list
       nodePtr = head;

       //Skip all nodes whose value member is not equal to num
       while (nodePtr != nullptr && nodePtr->value != searchValue)
       {
           previousNode = nodePtr;
           nodePtr = nodePtr->next;
       }
       //If nodePtr is not at the end of the list, link the
       //previous node ot the node after nodePtr, then delete nodePtr.
       if (nodePtr)
       {
           previousNode->next = nodePtr->next;
           delete nodePtr;
       }
   }
}
//Destructor
//This function will delete every node on the list

template <class T>
LinkedList<T>::~LinkedList()
ListNode<T> *nodePtr;
ListNode<T> *nextNode;

//Position nodePtr at the head of the list.
nodePtr = head;
//While nodePtr is not at the end of teh list...
while (nodePtr != nullptr)
{
   //Save a pointer to the next node.
   nextNode = nodePtr->next;

   delete nodePtr;

   nodePtr = nextNode;
}
}
#endif

Answer 1

There were no bugs in your code but they asked to write methods, which could add/delete elements in the beginning and in the end of the linked list. Also you didn't write find method, which should find element in the linked list. I added these methods to your code and tested your methods, which were working properly. The methods, which I added, are bolded.

#ifndef LIST_H
#define LINKEDLIST_H

template <class T>
class ListNode
{
public:
//Node value
T value;
//Pointer to the next node
ListNode<T> *next;
//Constructor
ListNode(T nodeValue)
{
value = nodeValue
next = nullptr;
}
};
//LinkedList class
template <class T>
class LinkedList
{
private:
//List head pointer
ListNode<T> *head;
public:
//Constructor
LinkedList()
{
head = nullptr;
}
//Destructor
~LinkedList();

//Linked list operations
void appendNode(T);
void insertAtBeginning(T);
void insertNode(T);
void deleteNode(T);
void deleteAtBeginning();
void deleteAtEnd();
int findNode(T);
void displayList() const;
};
template <class T>
void LinkedList<T>::appendNode(T newValue)
{
//To point to a new node
ListNode<T> *newNode;
//To move through the list
ListNode<T> *nodePtr;
//Allocate a new node and store new Value there.
newNode = new ListNode<T>(newValue);
if (!head)
head = newNode;
else
{
//Initialize nodePtr to head of list.
nodePtr = head;
//Find the last node in the list
while (nodePtr->next)
nodePtr = nodePtr->next;
//Insert newNode as the last node.
nodePtr->next = newNode;
}
}

template <class T>
void LinkedList<T>::insertAtBeginning(T newValue)
{
//To point to a new node
ListNode<T> *newNode;
//Allocate a new node and store new Value there.
newNode = new ListNode<T>(newValue);
if (!head)
head = newNode;
else
{
//Add at the beginning
newNode->next = head;
head = newNode;
}
}

template <class T>
void LinkedList<T>::displayList() const
{
//To move through the list
ListNode<T> *nodePtr;
//Position nodePtr at the head of the list.
nodePtr = head;
//Traverse the list
while (nodePtr)
{
//Value of this node
cout << nodePtr->value << endl;
//Move to the next node.
nodePtr = nodePtr->next;
}
}
template <class T>
void LinkedList<T>::insertNode(T newValue)
{
ListNode<T> *newNode;
//traverse the list
ListNode<T> *nodePtr;

ListNode<T> *previousNode = nullptr;
newNode = new ListNode<T>(newValue);

if (!head)
{
head = newNode;
newNode->next = nullptr;
}
else
{
nodePtr = head;
previousNode = nullptr;

//Skip all nodes whose value is less than newValue.
while (nodePtr != nullptr && nodePtr && nodePtr->value < newValue)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
//If the new node is to be the 1st in the list, then insert it before all other nodes
if (previousNode == nullptr)
{
head = newNode;
newNode->next = nodePtr;
}
else {
previousNode->next = newNode;
newNode->next = nodePtr;
}
}
}
template <class T>
void LinkedList<T>::deleteNode(T searchValue)
{
//To traverse the list
ListNode<T> *nodePtr;
//To point to the previous node
ListNode<T> *previousNode;
//There is no need to do anything if the list is empty
if (!head)
return;

//Determine if the first node is one
if (head->value == searchValue)
{
nodePtr = head->next;
delete head;
head = nodePtr;
}
else
{
//Initialize nodePtr to head of list
nodePtr = head;

//Skip all nodes whose value member is not equal to num
while (nodePtr != nullptr && nodePtr->value != searchValue)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
//If nodePtr is not at the end of the list, link the
//previous node ot the node after nodePtr, then delete nodePtr.
if (nodePtr)
{
previousNode->next = nodePtr->next;
delete nodePtr;
}
}
}

template <class T>
int LinkedList<T>::findNode(T searchValue)
{
int ans = 0;
//To move through the list
ListNode<T> *nodePtr;
//Position nodePtr at the head of the list.
nodePtr = head;
//Traverse the list
while (nodePtr != nullptr && nodePtr -> value != searchValue) {
nodePtr = nodePtr->next;
ans++;
}
//If we didn't find the value;
if (nodePtr == nullptr) {
return -1;
}
return ans;
}

template <class T>
void LinkedList<T>::deleteAtBeginning()
{
if (!head)
return;
//To point to a new node
ListNode<T> *newNode;
newNode = head->next;
delete head;
head = newNode;
}

template <class T>
void LinkedList<T>::deleteAtEnd()
{
if (!head)
return;
//To point to a new node
ListNode<T> *newNode;
//To move through the list
ListNode<T> *nodePtr;
while (nodePtr -> next != nullptr) {
nodePtr = nodePtr -> next;
}
delete nodePtr -> next;
}

//Destructor
//This function will delete every node on the list

template <class T>
LinkedList<T>::~LinkedList() {
ListNode<T> *nodePtr;
ListNode<T> *nextNode;

//Position nodePtr at the head of the list.
nodePtr = head;
//While nodePtr is not at the end of teh list...
while (nodePtr != nullptr)
{
//Save a pointer to the next node.
nextNode = nodePtr->next;

delete nodePtr;

nodePtr = nextNode;
}
}
#endif

comment down for any queries

please give a thumbs up