C++ Linked list implementation crashing

Question

I am trying to implement a linked list for a data structures class and I am having some difficulty with the searching portion of the algorithm.

Below is the offending code, which I have tried to implement following the pseudo-code in the MIT introduction to algorithms text:

//
// Method searches and retrieves a specified node from the list
//
Node* List::getNode(unsigned position)
{
    Node* current = m_listHead;

    for(unsigned i = m_listSize-1; (current != 0) && (i != position); --i)
            current = current->next;

    return current;
}

The head at this point in the program is the 4th node, which contains the value of int 5. the problem appears to be in the body of the for-loop, where the pointer to the node object is assigned to the next node. But this is going beyond the head of the node, so it is essentially pointing at some random location in memory (this makes sense).

Shouldn't the algorithm be moving to the previous Node instead of the next Node in this case? Below is the pseudo-code:

LIST-SEARCH(L, k)
    x <- head
    while x != NIL and key != k
        do x <- next[x]
    return x

Also, here is the header file for my Linked list implementation. I haven't tried to implement it in Template form yet just to keep things simple:

#ifndef linkList_H
#define linkList_h


//
// Create an object to represent a Node in the linked list object
// (For now, the objects to be put in the list will be integers)
//
struct Node
{
    // nodes of list will be integers
    int number;
    // pointer to the next node in the linked list
    Node* next;
};


//
// Create an object to keep track of all parts in the list
//
class List
{
public:

    // Contstructor intializes all member data
    List() : m_listSize(0), m_listHead(0) {}

    // methods to return size of list and list head
    Node* getListHead() const { return m_listHead; }
    unsigned getListSize() const { return m_listSize; }

    // method for adding a new node to the linked list, 
    // retrieving and deleting a specified node in the list
    void addNode(Node* newNode);
    Node* getNode(unsigned position);

private:

    // member data consists of an unsigned integer representing
    // the list size and a pointer to a Node object representing head
    Node* m_listHead;
    unsigned m_listSize;
};

#endif

Implementation of addNode method:

//
// Method adds a new node to the linked list
//
void List::addNode(Node* newNode)
{
    Node* theNode = new Node;

    theNode = newNode;
    theNode->next;
    m_listHead = theNode;

    ++m_listSize;
}

Is the list doubly-linked? What does is look like in memory? — Dave
– Dave, Commented Oct 10, 2011 at 0:11
I think the problem may be in the addNode member function. Please supply that code so we can ensure that the list is constructed correctly. — Ed Heal
– Ed Heal, Commented Oct 10, 2011 at 0:16
Yes, I believe this should be doubly-linked. I haven't added the previous node field to the element. Not sure how to do that. — dtg
– dtg, Commented Oct 10, 2011 at 0:23

Ed Heal · Accepted Answer · 2011-10-10 00:29:24Z

1

Try this to construct the list:

void List::addNode(int number) 
{ 
    newNode = new Node;
    newNode -> number = number;
    newNode -> next = m_listHead ;
    m_listHead = newNode;
    ++m_listSize; 
}

It will add nodes to the head. Perhaps you may wish to store the pointer to the tail and insert the nodes there.

answered Oct 10, 2011 at 0:29

Ed Heal

60.3k18 gold badges91 silver badges137 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Brian Roach · Accepted Answer · 2011-10-10 00:35:42Z

0

Unfortunately your code doesn't resemble the pseudo code you supply.

The pseudo-code is for searching a linked-list for a key, not a position.

The pseudo code reads as:

Assign head to (node) x.
while x isn't null and the key inside the current node (x) doesn't match k
  assign x->next to x
return x

The returned value is either a pointer to the node that contains k or null

If you're trying to find the node at a given position your loop would be (note this is assuming you're going to use a zero-based index for accessing the list):

Assign head to (node) x
assign 0 to (int) pos
while x isn't null and pos not equal to given position
    assign x->next to x
    increment pos
return x

The result will either be a pointer to the node at the given position or null (if you hit the end of the list first)

Edit: Your code is very close to the latter if that's what you're trying to do ... can you see the difference?

Edit because I like homework where the OP asks the right questions :)

Node* List::getNodeContaining(int searchValue)
{
    Node* current = m_listHead;

    while (current != 0 && current->number != searchValue)
    {
        current = current->next;
    }
    return current;
}

Node* List::getNodeAtPos(int position)
{
     Node* current = m_listHead;
     int pos = 0;

     while (current != 0 && pos != position)
     {
        current = current->next;
        pos++;
     }

     return current;
}

edited Oct 10, 2011 at 0:35

answered Oct 10, 2011 at 0:14

Brian Roach

77k12 gold badges140 silver badges164 bronze badges

6 Comments

dtg Over a year ago

Hmm. I understood the key to be the index of the loop and the k to the position supplied by the client code. Kind of in over my head here it seems...

dtg Over a year ago

Ah, I see. The key field of the Node should be whatever the element is in the given node? (eg. "int number" for a list of numbers)

Brian Roach Over a year ago

Right :) If your method is supposed to be searching for what's inside the node, you need to be comparing the value passed in to each node's contents (Node->number)

dtg Over a year ago

Well, it seems you are incrementing position. I am still slightly confused though; is "the key inside the current node" to mean what is pointed to by x (the current node)? I am trying to basically have the client code say "give me this bit of data (eg integer 4)" and the list will find that element. I guess if that is the case, I should probably be comparing position against current->key...

Brian Roach Over a year ago

See my latest edit. If you're trying to search for something in the list, you need to compare to the value contained inside the node. If you're looking for something at position x in the list, then you need to keep track of position. EDIT: (Gah - it's right now, made a mess of that edit)

|

Dave · Accepted Answer · 2011-10-10 00:38:41Z

You list is very different from what a normal list ADT looks like. Rather than returning nodes, which would require the client know about the list implementation, you return and accept the type you're making a list of.

In this case you're making a list of integers, sou you'd want

public:
    void add(int num); //prepends an Item to the list
    int get(int pos);

The implementations of both are simple. Add makes a new node, and links it in;

void List::add(int num)
{
    Node *newNode = new Node;
    newNode->number  = num;
    newNode->next = m_listHead;
    m_listHead = newNode;
    m_listSize++;
}

Then get is easy too:

int List::get(int pos)
{
    if(pos>m_listSize)
        ;//throw an error somehow
    Node *tmp = m_listHead;
    while(pos-->0)
        tmp=tmp->next; 
    return m->number
}

Collectives™ on Stack Overflow

C++ Linked list implementation crashing

3 Answers 3

Comments

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related