C++ Linked List Operations

Question

I'm trying to do a lab for class and despite my professor's lecture and the accompanying reading, I'm having issues figuring out syntax. If someone can help with one of the functions, I feel like I can figure out the rest.

This is the header

#pragma once

#include <string>

using namespace std;

struct ListNode
{
public:
    ListNode( const string& theString, ListNode* pNext = NULL )
    {
        word = theString;
        pNextNode = pNext;
    }

    string word;
    ListNode* pNextNode;
};

//add a node (pNode) at the head of the list.  
//return a pointer to the head node
ListNode* addFront( ListNode* pHead, ListNode* pNode );

//add a node (pNode) at the tail of the list.  
//return a pointer to the head node
ListNode* addEnd( ListNode* pHead, ListNode* pNode );

//remove (and cleanup after) the node at the head of the LinkedList (pHead)
//return a pointer to the head node
ListNode* removeFront( ListNode* pHead );

//remove (and cleanup after) the node at the tail of the LinkedList (pHead)
//return a pointer to the head node
ListNode* removeEnd( ListNode* pHead );

//traverse the LinkedList (pHead) and delete all nodes
//return a pointer to the head node
ListNode* removeAllNodes( ListNode* pHead );

//traverse the LinkedList (pHead) and write out all the words in the list
//separated by a space
void printNodeReport( ListNode* pHead, ostream& out );

and this is the cpp in which I need to implement stubs

#include "LinkedList.h"
#include <string>
#include <sstream>

//add a node (pNode) at the head of the list.  
//return a pointer to the head node
ListNode* addFront( ListNode* pHead, ListNode* pNode )
{
    //stub

    return pHead;
}

//add a node (pNode) at the tail of the list.  
//return a pointer to the head node
ListNode* addEnd( ListNode* pHead, ListNode* pNode )
{
    //stub
    return pHead;
}


//remove (and cleanup after) the node at the head of the LinkedList (pHead)
//return a pointer to the head node
ListNode* removeFront( ListNode* pHead )
{
    //stub
    return pHead;
}

//remove (and cleanup after) the node at the tail of the LinkedList (pHead)
//return a pointer to the head node
ListNode* removeEnd( ListNode* pHead )
{
    //stub
    return pHead;
}



//traverse the LinkedList (pHead) and delete all nodes
//return a pointer to the head node
ListNode* removeAllNodes( ListNode* pHead )
{
    //stub
    return pHead;
}


//traverse the LinkedList (pHead) and write out all the words in the list
//separated by a space
void printNodeReport( ListNode* pHead, ostream& out )
{
    out << "Here's the list: ";
    ListNode* pCurr = pHead;
    while( pCurr != NULL )
    {
        out << pCurr->word << " ";
        pCurr = pCurr->pNextNode;
    }
    out << "EOL \n";
}

Wow, at this rate, they may be teaching current C++ standards to students in another 20 years. — crashmstr, Mar 10 '14 at 19:28
Look at http://stackoverflow.com/questions/397895/how-could-i-create-a-list-in-cpost, for the answer by Johannes Schaub — KevinDTimm, Mar 10 '14 at 19:28

score 1 · Answer 1 · answered Mar 10 '14 at 19:26

1

First one:

ListNode* addFront( ListNode* pHead, ListNode* pNode )
{
    pNode->pNextNode = pHead;
    return pNode;
}

One could also be more defensive:

ListNode* addFront( ListNode* pHead, ListNode* pNode )
{
    if(pNode == NULL)
    {
        //Exception handling.
    }
    pNode->pNextNode = pHead;
    return pNode;
}

answered Mar 10 '14 at 19:26

riklund

1,031
2
8
16

Hmmmmmmm ... :/ That's not what I would expect as behavior of a function named `addFront()` – πάντα ῥεῖ Mar 10 '14 at 19:48
How so? It attaches the front element to the element to add, and then sets the front element to the new front element, right? – riklund Mar 10 '14 at 22:07
The signature you're using is wrong, `pHead` should be a reference. – πάντα ῥεῖ Mar 10 '14 at 22:09
I don't think so? I copied the signature from the problem description. – riklund Mar 10 '14 at 22:12
Might have been, but it's not obviously wrong. While I wouldn't write `addFront()` that way, I don't see that it's not a valid implementation. – riklund Mar 10 '14 at 22:18

πάντα ῥεῖ · Answer 2 · 2014-03-10T20:15:19.487

If someone can help with one of the functions, I feel like I can figure out the rest.

You should pass your lists head as reference (and be sure to have it initialized to nullptr in your client code):

ListNode* addFront( ListNode*& pHead, ListNode* pNode )
{
    if(!pHead) {
        pHead = pNode;
    }
    else if(pNode) {
        pNode->pNextNode = pHead;
        pHead = pNode;
    }
    return pHead;
}

Alternatively use this function signature (if this helps you better understanding the reference):

ListNode* addFront( ListNode** pHead, ListNode* pNode )
{
    assert(pHead);
    if(!(*pHead)) {
        *pHead = pNode;
    }
    else if(pNode) {
        pNode->pNextNode = *pHead;
        *pHead = pNode;
    }
    return *pHead;
}

Use of 1st sample:

ListNode* theList = nullptr;
addFront(theList,new ListNode("World!"));
addFront(theList,new ListNode("Hello "));

Use of 2nd sample:

ListNode* theList = nullptr;
addFront(&theList,new ListNode("World!"));
addFront(&theList,new ListNode("Hello "));

The following code after the above statements

for(ListNode* curNode = theList; curNode; curNode = curNode->pNextNode) {
    std::cout << curNode->word;
}

outputs

Hello World!

While I totally agree that your implementation is better, it does not actually answer the question posed. The question was to fill in the provided function, not change the signature. I believe the intention of the provided signatures were to call by issuing `list = addFront(list, nodeToAdd)`. — riklund, Mar 10 '14 at 22:16
@riklund I even thought about making the function `void`. But since the statement you're proposing would still work well with my proposal, I condemned that for less confusion ... — πάντα ῥεῖ, Mar 10 '14 at 22:20

C++ Linked List Operations

2 Answers2