Linked Link Assignment

[cblack618]

I need help with this linked List assignment,

Using an appropriate definition of ListNode, design a 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.

All that I have and know is below

  #include <iostream>

using namespace std;

class ListNode{
private:
double value;
ListNode *next;
friend class LinkedLists;
public:
ListNode(double v, ListNode *p)
{
value = v; next = p;
}
// LinkedList has friend status
};

[Manga]

I suppose you should start by coding your default constructor. But remember, the default constructor is the constructor that will get called by default and does not take any arguments.

[jonnin]

did you write that?
it seems overly complex.

class node
{
some kinda data;
node* next;
}
class list
{
node* head; //just use the node class. inheriting from it is unnecessary?
... other things
void add() {code... tmp = new thing, tmp next = head, head = tmp will do it}
list() {head = nullptr;} //
}

I don't see all the friend/deep inheritance stuff as useful unless you have a requirement to do it or a need to do it: it may be making your job harder if you are new to this stuff. If you already understand inheritance and all the bits well, it does not matter, but I don't think you would be asking these questions if you knew it well.

[Duthomhas]

Linked lists are one of those things you will never really understand if you just try to hack through someone else’s code.

The very first thing you need is a literal piece of paper and some kind of stylus. (Construction paper and crayons are most fun.)

Then draw pictures, with little boxes holding values and little arrows pointing to other boxes or to nothing (aka NULL aka nullptr).

Then you need an arrow or two more to keep track of head, traversal, insertions, deletions, etc. Think it through step by step so that nothing gets lost.

Only then are you ready to start writing code. Use the simplest data structure possible:

struct node
{
  int   value;
  node* next;
};

And, if you want, an encapsulating type with some useful methods:

struct linked_list
{
  node* head;

  linked_list() : head{nullptr} { }

  void append( int value );
  void insert( int value, int index );
  void remove( int index );
  int  size() const;
  bool empty() const;
};

And, for testing, you want to be able to iterate through the list and print all the elements:

void print( const linked_list& xs )
{
  ...
}

Your main() practically writes itself:

int main()
{
  linked_list xs;

  std::cout << "size of list = " << xs.size() << "\n";

  xs.append( 2 );  std::cout << "xs = ";  print( xs );
  xs.append( 5 );  std::cout << "xs = ";  print( xs );
  xs.append( 7 );  std::cout << "xs = ";  print( xs );

  xs.insert( 3, 1 );  std::cout << "xs = ";  print( xs );

  xs.remove(             0 );  std::cout << "xs = ";  print( xs );
  xs.remove( xs.size() - 1 );  std::cout << "xs = ";  print( xs );

  std::cout << "size of list = " << xs.size() << "\n";

  // etc
}

Hope this helps.

[dhayden]

Indenting your code and creating the LinkedList class as specified you get this. I've added just one thing: the head pointer in class LinkedList. All you have to do is add the code where indicated.

#include <iostream>

using namespace std;

// Using an appropriate definition of ListNode
class ListNode{
private:
    double value;
    ListNode *next;
    friend class LinkedList;
public:
    ListNode(double v, ListNode *p)
    {
	value = v; next = p;
    }
};

// design a linked list class with only two member functions and a
// default constructor
class LinkedList {
public:
    void add(double x);
    bool isMember(double x);
    LinkedList();
private:
    ListNode *head;
};

LinkedList::LinkedList()
{
    // ADD YOUR CODE
}

void LinkedList::add(double x)
{
    // ADD YOUR CODE
}

bool LinkedList::isMember(double x)
{
    // ADD YOUR CODE
}

[cblack618]

Hello,

Thank you all for your help and assitance. I will look over all your post and recommendations and see can I play around with it and figure it out in Visual Studio

[cblack618]

this is what i have but there are errors and im not sure if what i did is right based on the assignment instructions

#include <iostream>

using namespace std;

// Using an appropriate definition of ListNode
class ListNode {
private:
    double value;
    ListNode* next;
    friend class LinkedList;
public:
    ListNode(double v, ListNode* p)
    {
        value = v; next = p;
    }
};

// design a linked list class with only two member functions and a
// default constructor
class LinkedList {
public:
    void add(double x);
    bool isMember(double x);
    LinkedList();
private:
    ListNode* head;
};

LinkedList::LinkedList()
{
    ListNode* n = head;
    ListNode* d;
    while (n != 0) {
        d = n;
        n = n->next;
        delete d;
        d = 0;
}

void LinkedList::add(double x)
{
    // add to front
    ListNode* n = new ListNode;
    n->data = x;
    n->next = head;
    head = n;
}

bool LinkedList::isMember(double x)
{
    ListNode* n = head;
    // iterate to the end node
    // look for x
    while (n != 0 && n->data != x) {
        n = n->next;
    }
    // if x is found, n is not null
    return n != 0;
}

[Manga]

#include <iostream>

using namespace std;

// Using an appropriate definition of ListNode
class ListNode {
private:
	double value;
	ListNode* next;
	friend class LinkedList;
public:
	ListNode(double v, ListNode* p)
	{
		value = v; next = p;
	}
};

// design a linked list class with only two member functions and a
// default constructor
class LinkedList {
public:
	void add(double x);
	bool isMember(double x);
	//a print function
	void printAll();
	LinkedList();
	//destructor
	~LinkedList();
private:
	ListNode* head;
};

//default constructor
LinkedList::LinkedList()
{
	ListNode* head = nullptr;
}

//destructor
LinkedList::~LinkedList()
{
	{
		// there is at least one item
		if (head != nullptr)
		{
			// release memory starting from the second item
			ListNode* current, * soon;
			current = this->head->next;
			while (current != nullptr)  // if there are at least two items
			{
				/* When there is no more items after current,
				 * delete current and leave.
				 * Otherwise, free up current and move on to
				 * the next item.
				 */
				if (current->next != nullptr)
				{
					soon = current->next;
					delete current;
					current = soon;
				}
				else
				{
					delete current;
					break;
				}

			}
		}

		delete this->head;
	}
}

void LinkedList::add(double x)
	{
		// add to front
		ListNode* n = new ListNode(x, head);
		head = n;
	}

void LinkedList::printAll()
{
	ListNode* n = head;
	while (n != NULL) {
		cout << n->value << " ";
		n = n->next;
	}
}



bool LinkedList::isMember(double x)
	{
		ListNode* n = head;
		// iterate to the end node
		// look for x
		while (n != nullptr) {
			if (n->value == x) return true;
			n = n->next;
		}
		// if x is found, n is not null else...
		return false;
	}


int main() {
	LinkedList one;
	
	one.add(3.1);
	one.add(1.1);
	one.printAll();

	cout << endl << one.isMember(3.1);
	return 0;
}

Adding a print function makes testing your code easier.

[dhayden]

Manga's constructor mistakenly uses a local variable named head. I'm sure he/she meant:

//default constructor
LinkedList::LinkedList()
{
    head = nullptr;
}

Also the destructor can be greatly simplified:

//destructor
LinkedList::~LinkedList()
{
    while (head) {
        ListNode *p = head;
        head = head->next;
        delete p;
    }
}

[Manga]

oops... Good catch dhayden :)