What follows here, are very rough algorithms on the basic operations that you wo
ID: 3756563 • Letter: W
Question
What follows here, are very rough algorithms on the basic operations that you would perform on a linked list. In actually implementing list operations, you would have to consider conditions such as: Is the list empty? What happens if I get to the null pointer and haven't found a data member that is supposed to be in the list? The algorithms here are just to provide you with an overview of the concepts involved in simple operations.
Creating a List (makeList(const ListNode::value_type [],const size_t& count))
This function receives an array in the order that we want to add it to the linkedlist. Index 0 will be the head node, index n-1 will be the last node. You may assume that the array is at least of size 1
Inserting Nodes (insertItem( value_type item))
This algorithm assumes that you want to insert a node into a list of ordered values. Let's say you have two values, 12 and 24. A new value of 14 should be inserted between these existing values so that the final list will contain the values 12, 14, and 24.
This is much easier to understand if you visualize the nodes and the pointers as they are changed. The following diagram attempts to illustrate this process.
Deleting Nodes (deleteList())
Delete ALL nodes in the list. This is a great function to call in the deconstructor too! After all, we do not want any memory leaks.
Memory leaks will lead to grade leaks on this assignment. No heap memory should be in use when the main function reaches the return 0.
Absolutely no #includes in your implementation other than ostream and linkedlist.h.
No recursion!
Example Output
This is the .h file and my implementation
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <cstdlib>
namespace LLLAB {
class ListNode
{
public:
typedef int value_type;
ListNode (value_type d = value_type(), ListNode* n = NULL) { datum = d; next = n; }
//Assessor
value_type getDatum () const { return datum; }
ListNode const* getNext () const { return next; }
//Mutator
void setDatum (const value_type& d) {datum = d; }
ListNode* getNext () { return next; }
void setNext (ListNode* new_link) {next = new_link; }
private:
value_type datum;
ListNode* next;
};
class LinkedList
{
public:
LinkedList ();
virtual ~LinkedList ();
void insertItem (ListNode::value_type);
void makeList (const ListNode::value_type [],const size_t& count);
void deleteList ();
//The following friend function is implemented in lablinklist.cpp
friend std::ostream& operator<<(std::ostream&, const LinkedList&);
private:
ListNode* head; //points to the first node of the linked list
};
} //end namespace
#endif /* LINKEDLIST_H_ */
#include <iostream>
#include "linkedlist.h"
using namespace std;
namespace LLLAB {
LinkedList::LinkedList ()
{
head = NULL;
}
LinkedList:: ~LinkedList ()
{
}
void LinkedList::insertItem (ListNode::value_type)
{
ListNode *newNode, *firstNode = head;
newNode = new ListNode;
head -> setDatum(newDatum);
newNode -> setNext (NULL);
if (head==NULL)
{
head = newNode;
}
else
{
while (firstNode ->getNext()!= NULL)
{
firstNode = fistNode -> getNext();
}
firstNode->setNext(newNode);
}
}
void LinkedList::makeList(const ListNode::value_type items[],const size_t& count)
{
int i = 0;
while (i < count)
{
insertItem(items[++i]);
}
}
void LinkedList::deleteList ()
{
ListNode *p = head;
while (p != NULL)
{
head = head->linkedlist;
delete p;
p = head;
}
}
New Node 12 24 1 previous current 12 24 previous current 24 previousExplanation / Answer
#include <iostream>
#include <cstdlib>
class Node
{
public:
Node* nxt;
int info;
};
using namespace std;
class LinkedList
{
public:
int len;
Node* headd;
LinkedList();
~LinkedList();
void add(int info);
void print();
};
LinkedList::LinkedList(){
this->len = 0;
this->headd = NULL;
}
LinkedList::~LinkedList(){
std::cout << "LIST DELETED";
}
void LinkedList::add(int info){
Node* node = new Node();
node->info = info;
node->nxt = this->headd;
this->headd = node;
this->len++;
}
void LinkedList::print(){
Node* headd = this->headd;
int i = 1;
while(headd){
std::cout << i << ": " << headd->info << std::endl;
headd = headd->nxt;
i++;
}
}
int main(int argc, char const *argv[])
{
LinkedList* list = new LinkedList();
for (int i = 0; i < 100; ++i)
{
list->add(rand() % 100);
}
list->print();
std::cout << "List Length: " << list->len << std::endl;
delete list;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.