Linked Lists [SOLVED]

[msulli1355]

I'm trying to work through a tutorial on linked lists. I've typed in the code exactly as it was given, but for some reason, only one node is being output.

michael@caitlyn linkedlists $ cat Node.h
#ifndef _NODE_
#define _NODE_

#include <iostream>
#include <string>

class Node
{
   friend std::ostream& operator<< (std::ostream& os, Node& n);
   friend class LinkedList;
   
   public:
   	Node(std::string name = "none");

   private:
	std::string name;
	Node* next;

};
#endif
michael@caitlyn linkedlists $ cat Node.cpp
#include "Node.h"
using namespace std;

Node::Node(string n) : name(n), next(NULL)
{}

ostream& operator<<(ostream& os, Node &n)
{
   return os << "Name:  " << n.name;
}

michael@caitlyn linkedlists $ cat LinkedList.h
#ifndef _LINKEDLIST_
#define _LINKEDLIST_
#include "Node.h"

class LinkedList
{
   public:
      LinkedList();
      void addToHead(const std::string &name);
      void printList();
      
   private:
      Node* head;
      int size;
};

#endif
michael@caitlyn linkedlists $ cat LinkedList.cpp
#include "LinkedList.h"
#include <string>
using namespace std;

LinkedList::LinkedList() : head(0), size(0)
{}

void LinkedList::addToHead(const string &name)
{
   Node* newOne = new Node(name);

   //Is the list currently empty?  Let's check.
   if (head == NULL)
   {
      //It IS empty!
      head = newOne;
   }
   else
   {
      //Nope, it's NOT empty.
      newOne = head->next;
      head = newOne;
   }
   size++;
   cout << "Size = " << size << endl;
}
void LinkedList::printList()
{
   Node  *tp = head;  //Traversal pointer set to head.
   
   while (tp != 0) //While tp not equal null.
   {
      cout << "Size = " << size << endl;
      cout << *tp << endl;
      tp = tp->next;
   }
}
michael@caitlyn linkedlists $ cat main.cpp 
#include "LinkedList.h"
using namespace std;

int main()
{
   LinkedList* l1 = new LinkedList();

   string name;

   while (true)
   {
      cout << "Input the name of the contact, or 'q' to quit" << endl;
      cin >> name;
      if (name == "q") break;
      l1->addToHead(name);
   }

   l1->printList();

}

And here's the output:

michael@caitlyn linkedlists $ ./main
Input the name of the contact, or 'q' to quit
tom
Size = 1
Input the name of the contact, or 'q' to quit
bob
Size = 2
Input the name of the contact, or 'q' to quit
sally
Size = 3
Input the name of the contact, or 'q' to quit
q
Size = 3
Name:  sally
michael@caitlyn linkedlists $ 

Why is only sally printed out? I've been thinking about this for two days and I cannot figure it out.

[Ganado]

Line 62: You point newOne to a new Node.
Line 73: You immediately overwrite the pointer you just set, by setting it to head->next, which is a nullptr.
Line 74: You then set head to be newOne, which is a nullptr, so you set head to be a nullptr as well.
Next addToHead() called:
head is still null, so head = newOne is called. Basically, every other insertion, you're setting a lot of things to null, and sally happened to make it out alive while everyone else didn't.

[msulli1355]

But if head is null, line 73 should never be executed, yes?

[msulli1355]

I changed my code to say:

void LinkedList::addToHead(const string &name)
{
   Node* newOne = new Node(name);

   //Is the list currently empty?  Let's check.
   if (head == NULL)
   {
      //It IS empty!
      head = newOne;
   }
   else
   {
      //Nope, it's NOT empty.
      newOne->next = head;
      head = newOne;
   }
   size++;
}

And now it works as expected. Thank you for your help.

[Ganado]

But if head is null, line 73 should never be executed, yes?

Correct, but then the next iteration, when head is no longer null, you immediately overwrite the pointer you just allocated memory to on line 73.

But anyway, yeah your new code looks correct.