Part 3: Design your own linked list and member functions Design a simple linked
ID: 3735967 • Letter: P
Question
Part 3: Design your own linked list and member functions
Design a simple linked list class with only two member functions and a default constructor:
void add(double x);
boolean isMember(double x);
LinkedList( );
The add function adds a new node containing x to the front (head) of the list, while the isMember function tests to see if the list contains a node with the value x. Test your linked list class by adding various numbers to the list and then testing for membership.
List Copy Constructor
Add a copy constructor. Test your class by making a copy of a list and then testing membership on the copy.
List Print
Add a print member function. Test the class by starting with an empty list, adding some elements, and then printing the resulting list out.
List Member Deletion
Modify the list class you created in the previous programming challenges by adding a function to remove an item from the list, and by adding a destructor:
void remove(double x);
~LinkedList();
Test the class by adding by a sequence of instructions that mixes operations for adding items, removing items, and printing the list.
List Reverse
Adding a member function for reversing the list:
void reverse();
The member function rearranges the nodes in the list so that their order is reversed. You should do this without creating or destroying nodes.
List Search
Modify the list class include a member function
int search(double x)
that returns the position of a number x on the list. The rst node in the list is at position 0, the second node is at position 1, and so on. If x is not found on the list, the search would return -1. Test the new member function using an appropriate driver program.
Explanation / Answer
#include <iostream>
class LinkedList
{
protected:
class ListNode
{
public:
double x;
ListNode* next;
ListNode(double x, ListNode* next = NULL)
{
this->x = x;
this->next = next;
}
};
ListNode* head; // Points to the first ListNode node
// Helper functions
bool isMemberRec(double x, ListNode* listHead); // recursive isMemberRec function
public:
/* Constructors and Destructor(s) */
LinkedList() { head = NULL; } // constructor
~LinkedList(); // Destructor
LinkedList(const LinkedList &); // Copy constructor
ListNode* copyList(ListNode* aList); // copies a list by returning a pointer to itself. Used by copy constructor
/* Mutators */
void add(double x);
void remove(double x);
void remove(int pos);
void insert(double x, int pos);
void reverse();
/* Accessors */
bool isMember(double x);
bool isMemberRec(double x) { return isMemberRec(x, head); } // recursive isMember - initial call takes only 1 arg to get chain going
void print();
int search(double x);
void sort();
};
//Destructor. Deletes entire list. cout statements for demo purposes
LinkedList::~LinkedList()
{
ListNode* nodePtr = head;
/* traverse the list with nodePtr; garbage follows in wake and deletes */
while (nodePtr != NULL)
{
ListNode* garbage = nodePtr;
nodePtr = nodePtr->next;
std::cout << "Deleting node: " << garbage->x << std::endl;
delete garbage;
}
std::cout << "List deleted." << std::endl;
std::cin.get();
}
//Copy constructor.
LinkedList::LinkedList(const LinkedList & original)
{
head = copyList(original.head);
}
//Returns a pointer to a copy of a list.
LinkedList::ListNode* LinkedList::copyList(ListNode* aList)
{
// Base case
if (aList == NULL)
return NULL;
else
{
// First copy the tail
ListNode* tailCopy = copyList(aList->next);
// Return copy of head attached to copy of tail
return new ListNode(aList->x, tailCopy);
}
}
// Add an element to the end (tail) of the list
void LinkedList::add(double x)
{
// If list has no head (empty list) then point the head to a newly allocated ListNode
if (head == NULL)
{
head = new ListNode(x);
}
// Otherwise, add the list to the tail
else
{
// Traverse the list
ListNode* ptr = head;
while (ptr->next != NULL)
{
ptr = ptr->next;
}
// Update the next pointer at the tail to point to new memory and pass the value x to its constructor
ptr->next = new ListNode(x);
}
}
// Remove the first instance of x from the listNode.
void LinkedList::remove(double x)
{
if (head == NULL)
return;
ListNode* nodePtr = head, *previousNodePtr = head;
// handle case of head containing value x first
if (head->x == x)
{
nodePtr = head;
head = head->next;
delete nodePtr;
}
else // or it might be in rest of list
{
nodePtr = head;
// Traverse the list until end or find value
while (nodePtr != NULL && nodePtr->x != x)
{
previousNodePtr = nodePtr;
nodePtr = nodePtr->next;
}
if (nodePtr)
{
previousNodePtr->next = nodePtr->next;
delete nodePtr;
}
}
}
// Remove the first instance of x from the listNode.
void LinkedList::remove(int pos)
{
int position = 0;
if (head == NULL)
return;
ListNode* nodePtr = head, *previousNodePtr = head;
// handle case of deleting head b/c we need to point LinkedList::head to the next value
if (pos == 0)
{
head = head->next;
delete nodePtr;
}
else
{
// Traverse the list until end or find position
while (nodePtr != NULL && position != pos)
{
previousNodePtr = nodePtr;
nodePtr = nodePtr->next;
position++;
}
if (nodePtr)
{
previousNodePtr->next = nodePtr->next;
delete nodePtr;
}
}
}
// Add the value x into the position in the list indicated by pos
void LinkedList::insert(double x, int pos)
{
if (head == NULL)
{
head = new ListNode(x);
}
// Otherwise, add the list to the correct position
else
{
int position = 0;
// Traverse the list
ListNode* nodePtr = head, *priorNodePtr = NULL;
// move forward in the list until we find the correct position or we've reached the end
while (pos != position && nodePtr->next != NULL)
{
priorNodePtr = nodePtr; // remember where the last node was so we can update its next pointer
nodePtr = nodePtr->next; // move up
position++; // increment our position counter
}
priorNodePtr->next = new ListNode(x);
priorNodePtr = priorNodePtr->next;
priorNodePtr->next = nodePtr;
}
}
//Reverse all of the nodes in the list.
void LinkedList::reverse()
{
ListNode* priorNodePtr, *nextNodePtr, *nodePtr;
nodePtr = head;
priorNodePtr = NULL;
// Now have three pointers external to the list itself we can use to reconnect each position
while (nodePtr != NULL) // stops when the nodePtr is pointing at NULL
{
nextNodePtr = nodePtr->next;
nodePtr->next = priorNodePtr; // point current node's next value backwards to last node, or null if it was the head
priorNodePtr = nodePtr; // shift the prior node up one position
nodePtr = nextNodePtr; // move current node
}
head = priorNodePtr;
}
void LinkedList::sort()
{
ListNode* nodePtr = head, * minNode = head, minNodeLess1 = NULL, startScan = head, startScanLess1 = NULL;
// For each index, we find the smallest value in the rest of the array and relink it
while (startScan != NULL)
{
while (nodePtr != NULL)
{
// If the value at any given node is less than the current min, repoint minNode
if (nodePtr->x < minNode->x)
{
minNode = nodePtr;
}
// Check next node
nodePtr = nodePtr->next;
}
startScanLess1->next = minNode;
nodePtr = minNode->next; // remember where minNode used to point
minNode->next = startScan; // then point the minNode->next to the value that we were at
startScanLess1 = startScan;
startScan = startScan->next;
nodePtr = startScan;
}
int minVal = nodePtr->x, minIndex = 0, position = 0;
while (/*condition*/)
{
position++;
nodePtr = nodePtr->next;
if (nodePtr->x < minVal)
{
minVal = nodePtr->x;
minIndex = position;
}
}
}
// Returns true of x is found in the list
bool LinkedList::isMember(double x)
{
// if list is empty, x is not a member of the list
if (head == NULL)
{
return false;
}
// Otherwise, start searching
else
{
ListNode* ptr = head;
while (ptr != NULL)
{
if (ptr->x == x)
{
return true; // value found
}
else
{
ptr = ptr->next;
}
}
return false;
}
}
//Returns true if x is found in the list - recursive version of isMember
bool LinkedList::isMemberRec(double x, ListNode* listHead)
{
if (listHead == NULL)
return false;
ListNode* ptr = listHead;
if (ptr->x == x)
{
return true;
}
else
{
return isMemberRec(x, ptr->next);
}
}
//Prints the elements in the list with a space as padding between values
void LinkedList::print()
{
if (head == NULL)
return; // do nothing if list empty
else
{
ListNode* ptr = head;
std::cout << "List values: ";
while (ptr != NULL)
{
std::cout << ptr->x << " ";
ptr = ptr->next;
}
std::cout << std::endl;
}
}
// Returns true if x is found in the list - recursive version of isMember
int LinkedList::search(double x)
{
int position = 0; // track the position that the value x is found, if any.
// if list is empty, x is not a member of the list
if (head == NULL)
{
return -1; // if list is empty, return -1 to signal list is empty
}
// Otherwise, start searching
else
{
ListNode* ptr = head;
while (ptr != NULL)
{
if (ptr->x == x)
{
return position;
}
else
{
ptr = ptr->next;
position++;
}
}
return -1; // signal not a member
}
}
int main()
{
LinkedList l;
// Try adding a member
l.print();
l.add(5);
l.print();
l.add(10);
l.add(15);
l.print();
l.remove(10);
l.print();
l.remove(15);
l.remove(5);
l.print();
for (int i = 0; i < 15; i++)
{
l.add(i + 10);
}
l.print();
std::cout << "calling l.isMember(11): " << l.isMember(11) << std::endl;
std::cout << "calling l.isMemberRec(12): " << l.isMemberRec(12) << std::endl;
std::cout << "calling l.isMemberRec(1200): " << l.isMemberRec(1200) << std::endl;
LinkedList l2 = l;
l2.print();
std::cout << "Reversing l2 using l2.reverse()." << std::endl;
l2.reverse();
l2.print();
std::cout << "List item 15 is in position: " << l2.search(15) << std::endl;
std::cout << "Inserting 99 into position of 15..." << std::endl;
l2.insert(99, 9);
l2.print();
std::cin.get();
return 0;
}