Trying to understand lists

[darren01]

For my homework in C++ I am required to complete a program provided by my professor. The first part of which requires me to return a pointer to the beginning of the list. I had to miss class due to illness last week and I am a bit mixed up trying to teach myself how this works. Can someone clarify for me? This is what I came up with so far..

Node* List::getFirst()
{
     first = ???;
}
//first is defined in a header file as a pointer to Node 

[nvrmnd]

You mean like :

Node* List::getFirst()
{
     return first;
}

http://www.cprogramming.com/tutorial/lesson15.html

[PrivateRyan]

What is "the list"? What is the prompt? It looks like the assignment is creating a linked list.

If so, first acts as the head of the list. Generally it is initialized to NULL if it is a singly-linked list or doubly-linked list and itself if it is a circular linked list.

The function you wrote above, however, is asking to return first. Literally:

Node* List::getFirst()
{
     return first;
}

This returns the address of the first node in the list, or NULL if the list is empty.

If you missed the lecture on linked lists....well....that is going to make things really difficult....pictures are super helpful when writing it.

Post more of the assignment so you can better be helped!

[darren01]

Thank both of you so much. I was stuck on that and I knew it was something simple. The next part is to add the insert function as well as the delete function given a pointer. PrivateRyan I realize that I missed something important, which is why I have been searching the web and youtube for a bit of explanation. If you can help me with the insert function I will be able to figure out the delete one.

Here is the header file:

#ifndef LIST_H
#define LIST_H

#include <string>
#include <ostream>

typedef std::string ElementType;

typedef struct _node
{
    ElementType payload;
    struct _node* next;
} Node;

class List
{
    private:
    Node* first;

    public:
    List();
    ~List();

    // CHALLENGE: (But not much of one, I admit)
    // Return a pointer to the beginning of the list.
    Node* getFirst();

    void insert(ElementType item, int position);

    // CHALLENGE: We need a new function that takes a Node* after which to insert
    // the new item.
    void insert(ElementType item, Node* prev);
    void add(ElementType item);

    // CHALLENGE: Complete the erase function.  Note that this is a change, in
    // that the original form was to accept an integer position and this one
    // accepts a value of type ElementType, and we want to delete the first
    // item matching that value.
    void erase(ElementType value);

    void display(std::ostream& ostr);
};

#endif 

And the .cpp file (main is complete already I am only required to fill the functions)

#include "list.h"

#include <string>
#include <ostream>
#include <iostream>
using namespace std;

Node* List::getFirst()
{
    return first; 
}

// Insert an element given an integer position
void List::insert(ElementType item, int position)
{

    // Find node after which to insert new item
    Node* here = first;
    for (int i = 1; i < position && here->next; i++)
    {
        here = here->next;
    }

    Node* newNode = new Node;
    newNode->payload = item;

    // here points at Node after which to do insertion.
    if (!here)
    {
        // First item in list
        newNode->next = 0;
        first = newNode;
    }
    else if (position == 0)
    {
        newNode->next = first;
        first = newNode;
    }
    else
    {
        newNode->next = here->next;
        here->next = newNode;
    }
}

// Insert an element given a pointer; you should check out what happens in
// the other list function.
void List::insert(ElementType item, Node* prev)
{
    //////////////  FILL IN THIS FUNCTION ////////////////
}

// Erase an element
// The challenge here is to realize that if we have a pointer to a node to
// erase, we have to "sneak up on it", so that we can fix up the previous
// node's next pointer.  We will assume that the node well and truly exists
void List::erase(ElementType value)
{
    //////////////  FILL IN THIS FUNCTION ////////////////
}

// Display the List
void List::display(ostream& ostr)
{
    Node* variableName = first;
    while (variableName)
    {
        ostr << variableName->payload << endl;
        variableName = variableName->next;
    }
}

// Constructor
List::List()
{
    first = 0;
}

// Destructor
List::~List()
{
    Node* here = first;
    while (here)
    {
        Node* nxt = here->next;
        delete here;
        here = nxt;
    }
}

void List::add(ElementType item)
{
    Node* here = first;
    int i;
    if (!first)
    {
        insert(item, 0);
    }
    else
    {
        for (i = 1; here->next; i++)
        {
            here = here->next;
        }
        insert(item, i);
    }
}

[mrspam]

I'm taking this class with you lol, I have no idea how to do this If you found out let me know.
If you have a Facebook we can figure this out together.

[D80DSL3A]

The existing void List::insert(ElementType item, int position); function is very close to what you need. The difference is in the condition for terminating the for loop.
In the given function, iteration goes until i == position, or here->next == NULL (end of list), whichever comes 1st.
For void List::insert(ElementType item, Node* prev); you want to iterate until here == prev. This is the condition for terminating the for loop (line 19).
A small change to line 34 is needed also.

[mrspam]

I tried what you said fun2code but I get segmentation fault + you dont need to edit the current functions we are required to fill in the functions where it says " ////////////// FILL IN THIS FUNCTION ////////////////"

[D80DSL3A]

You don't need to modify the existing functions. I meant just to refer to them as examples.
Post your code for the void List::insert(ElementType item, Node* prev); function. It may be a simple problem.

[mrspam]

#include "list.h"

#include <string>
#include <ostream>
#include <iostream>
using namespace std;

Node* List::getFirst()
{
    return first;
}

// Insert an element given an integer position
void List::insert(ElementType item, int position)
{

    // Find node after which to insert new item
    Node* here = first;
    for (int i = 1; i < position && here->next; i++)
    {
        here = here->next;
    }

    Node* newNode = new Node;
    newNode->payload = item;

    // here points at Node after which to do insertion.
    if (!here)
    {
        // First item in list
        newNode->next = 0;
        first = newNode;
    }
    else if (position == 0)
    {
        newNode->next = first;
        first = newNode;
    }
    else
    {
        newNode->next = here->next;
        here->next = newNode;
    }
}

// Insert an element given a pointer; you should check out what happens in
// the other list function.
void List::insert(ElementType item, Node* prev)
{
    Node* here = first;
    for (int i = 1; here == prev; i++)
    {
        here = here->next;
    }

    Node* newNode = new Node;
    newNode->payload = item;

    // here points at Node after which to do insertion.
    if (!here)
    {
        // First item in list
        newNode->next = 0;
        first = newNode;
    }
    else if (here == 0)
    {
        newNode->next = first;
        first = newNode;
    }
    else
    {
        newNode->next = here->next;
        here->next = newNode;
    }
}
// Erase an element
// The challenge here is to realize that if we have a pointer to a node to
// erase, we have to "sneak up on it", so that we can fix up the previous
// node's next pointer.  We will assume that the node well and truly exists
void List::erase(ElementType value)
{
    Node* here = first;
    for (int i = 1; here == 0; i++)
    {
        here = here->next;
    }

    Node* newNode = new Node;
    newNode->payload = value;

    // here points at Node after which to do insertion.
    if (!here)
    {
        // First item in list
        newNode->next = 0;
        first = newNode;
    }
    else if (here == 0)
    {
        newNode->next = first;
        first = newNode;
    }
    else
    {
        newNode->next = here->next;
        here->next = newNode;
    }
}

// Display the List
void List::display(ostream& ostr)
{
    Node* variableName = first;
    while (variableName)
    {
        ostr << variableName->payload << endl;
        variableName = variableName->next;
    }
}

// Constructor
List::List()
{
    first = 0;
}

// Destructor
List::~List()
{
    Node* here = first;
    while (here)
    {
        Node* nxt = here->next;
        delete here;
        here = nxt;
    }
}

void List::add(ElementType item)
{
    Node* here = first;
    int i;
    if (!first)
    {
        insert(item, 0);
    }
    else
    {
        for (i = 1; here->next; i++)
        {
            here = here->next;
        }
        insert(item, i);
    }
}

That gave me segmentation fault

[D80DSL3A]

Hmm... I tried the code myself and I guess I was wrong abut the modifications to the existing insert function.

I wound up writing the new insert function myself (and it's working). It's actually simpler than the given version.

There are only 2 insertion scenarios
1) Either first==0 (empty list) or prev==0 (which means to insert before first).
Either way you are adding a new first Node, so:

 newNode->next = first;
 first = newNode;

2) else (only other case) you are inserting after prev, in which case:

newNode->next = prev->next;
prev->next = newNode;

No for loop needed!

Re. the erase() function. Really dude? You thought that might work?
You need to write this one from scratch. There is no other given version to work from.
I have my version working.
Again, there are 2 erasure scenarios:
1) first->payload == value. Erase the 1st Node. I'll give you the code for this:

Node* badNode = first;// Node to be deleted
first = first->next;// new first Node is next in list.
delete badNode;

2) else (only other case) value is deeper in the list. Consider your profs. comments re. "sneaking up" on the Node to be erased. You are seeking the Node previous to the one to be erased, so you can re assign its next pointer to badNode->next. Admittedly, this part is a little tricky.

Some use 2 local Node*'s prev and curr, You iterate until curr->payload == value, and keep prev updated so it's always pointing one behind curr.

I think my approach is cleaner. Having examined first->payload explicitly, we can start at Node* curr = first; and confidently watch for curr->next->payload == value while iterating through the list(using curr). Then:

Node* badNode = curr->next;// save pointer to node to be removed
curr->next = badNode->next;// link across badNode
if( badNode ) delete badNode;

Try to work off of that. Post back with your new functions after giving it a serious shot.
And, watch the content of your PMs. That was risky for you.

[darren01]

Hey fun2code, first off thank you for your insight, your explanation makes it more clear to me what has to happen in the function, but I also found it easier to visualize what is going on by drawing a little diagram. Second that previous example was not from me it was from a fellow classmate (we're in the same boat). Your code for the insert function worked properly, I was a bit stuck on how the function worked since it is passed a pointer and not an int as in the add function. I now need to work on the delete function for which I will look through your explanation and post back if I run into trouble.

Thanks again!

[D80DSL3A]

You're quite welcome. I was aware that I was responding to your classmate.
I hoped you would find my posts to him useful.

Drawing diagrams is the best tool I've found for working out the details of various linked list functions.

[mrspam]

So thats what I have for insert function

void List::insert(ElementType item, Node* prev)
{
        if (first == 0 || prev == 0)
	{
		 newNode->next = first;
		 first = newNode;
	}

    else
    {
		newNode->next = prev->next;
		prev->next = newNode;
    }
}

is that right?

[darren01]

mrspam, yes that is right that is exactly what I have. You can run make test and see if the list prints correctly when you aren't sure. Obviously the second part is wrong because we haven't addressed the delete function, however insert is working properly.

[mrspam]

I'm getting confused, I tried testing the insert function but I get segmentation fault.

Thats what I got for erase so far

void List::erase(ElementType value)
{
  if( first->payload == value )
  {
	  Node* badNode = first;// Node to be deleted
	  first = first->next;// new first Node is next in list.
	  delete badNode;
  }
  else 
  {
		Node* curr = first;
		Node* badNode = curr->next;// save pointer to node to be removed
		curr->next = badNode->next;// link across badNode
		if( badNode ) delete badNode;}
  }
}

I actually couldn't follow what you said I think its about right thou.
I tried something else

void List::erase(ElementType value)
{   
   Node* badNode = first;
	   if (prev == NULL)
   {      
      if (value == first )
      {
	first = first->next;
      }
      else
	{	   
	}
   }
   else
      prev->next = value->next; 
   
   delete value;    
}

but still didnt work (segmentation fault)

[darren01]

So I got the whole program working correctly, including the delete function. Can somebody tell me if how I did it is acceptable?

// Erase an element
// The challenge here is to realize that if we have a pointer to a node to
// erase, we have to "sneak up on it", so that we can fix up the previous
// node's next pointer.  We will assume that the node well and truly exists
void List::erase(ElementType value)
{
    //case 1 empty list
    if (first == 0)
    {
        cout << "The list is empty, cannot remove node" << endl;
    }
    else 
    {
        Node* current = first;
        Node* previous = 0;
        while (current != 0)
        {
            if (current->payload == value)
            {
                break;
            }
            else
            {
                previous = current;
                current = current->next;
            }
        }
        //case 2 Node not found
        if (current == 0)
        {
            cout << "Node: " << value << " not found" << endl;
        }
        else 
        {
            //case 3 delete from first
            if (first == current)
            {
                first = first->next;
            }
            //case 4 delete from beyond first
            else
            {
                previous->next = current->next;
            }
            delete current;
        }
    }
}

[D80DSL3A]

Nice job!
I see you went with the 2 local pointers approach, which is perfectly fine.

Here's mine for comparison. You'll see the single pointer method there

void List::erase(ElementType value)
{
    if( !first ) return;// empty list. Nothing to erase

    if( first->payload == value )// erase the first Node
    {
        Node* badNode = first;
        first = first->next;//
        delete badNode;
    }
    else// go deep!
    {
        Node* iter = first;
        while( iter->next && iter->next->payload != value )// "sneaking up" by watching value of iter->next->payload, instead of iter->payload
            iter = iter->next;

        // iter should now point to the node prev to the one to erase
        Node* badNode = iter->next;// save pointer to node to be removed. This will = NULL if value not found.       
        if( badNode )
        {
            iter->next = badNode->next;// link across badNode
           delete badNode;
        }
        else
           cout << "Node: " << value << " not found" << endl;// added to match your functions features.
    }
}

[darren01]

I see what you did there with the one pointer! You took advantage of the fact that iter->next is pointing to another node pointer correct? While I must admit your version looks cleaner I feel it is a tad bit harder to follow through mentally.

Thanks fun2code! I really appreciate your help, I now feel more confident in my understanding of linked lists and how to go about adding and/or deleting nodes from them.

[mrspam]

Fun2code, yeah I tried to do it your way. Its much cleaner but harder to follow.
I can follow it now, I did something smiler to darren's code but thank you very much for sharing this code. It actually made me understand linked lists more and gave me a different way to think about solving this problem.
darren yeah your code is totally fine, I didn't test it but it should work fine.

[mrspam]

If I want the program to print the words in alphabetical order but without "." how can I do that?
the program reads from a text file which contains "The quick brown fox jumped over the back of the lazy dog."
when I run what I have it prints "dog." how can I tell the program to ignore the "."?