I'm attempting to create a function getPredecessor() in which the function recieves an int in reference to a position in the list and should return a pointer to the node before that position. If the position is the first place in the list, return 0.

Here's my header (followed by my lame attempt to define getPredecessor()) so you can see what I'm attempting. The getPredecessor() will be used in functions following its protype and definition. FYI, some of the functions dont have a data type because I'm still working on them, so please disregard any of those

#include<iostream>
using namespace std;

typedef int ElementType;
class LinkedList
{
    private: 
        class Node
        {
            public:
                ElementType data;
                Node * next;
        };
        typedef Node * NodePointer;
        NodePointer ptr;            //pointer to nodes
        NodePointer first;          //points to first node
        NodePointer predptr;        //points to predecessor node
        NodePointer newptr;         //points to a new node
        int mySize;                 //number of nodes
        
    public:
        LinkedList(int size);                                       //constructor
        void display(ostream & out)const;
        int getPredecessor(int pos);
        int length();
        void insert(ElementType item, int pos);
        erase();
        bool empty();
        bool intList();
        ~LinkedList();                                     //destructor
        LinkedList(const LinkedList & orig);         //copy constructor
        const LinkedList & operator=(const List & other);
};
ostream & operator <<(ostream & out, const LinkedList & aList);

getPredecessor definition

int LinkedList::getPredecessor(int pos)
{
    if(ptr==first)
        return 0;
    else
    {
        for(int i = 0; i > pos; i++)
        {
             ptr->data = predptr->data; 
               
        }
        return ptr->data; 
    }       
}

Edited 6 Years Ago by bmos31: n/a

A little more clarity? I'd like some tips on whether or not this is a correct function for getting a predecessor.

The reason I set it to greater than is because I thought that maybe I should traverse the list starting from the first node until I reach the predecessor...

Here's a modified version of my function, but I'm not sure if its even close

int LinkedList::getPredecessor(int pos)
{

    if(ptr->data==first->data)
        return 0;
    else
    {
        ptr = first;
        for(int i = 0; i > pos; i++)
        {
             ptr->next = predptr->next;     
        }
        return ptr; 
    }       
}

>> for(int i = 0; i > pos; i++)

Edited 6 Years Ago by bmos31: n/a

>> for(int i = 0; i > pos; i++)

That loop is a bug. If pos is greater than 0, then that loop will not execute. If pos is less than or equal to 0, the that loop becomes a infinite loop. What you are looking for is the "<" operator. That is i < pos . You might be getting confused a little bit.

I'm not exactly sure what your getPredecessor function does. Whats its exact purpose?

Oh, sorry if I wasn't clear on that. Here's the requirements assigned to me:
"getPredecessor: receives an integer representing a position in the list, and returns a
pointer to the node before that position. If the given position is the first place in the list,the function should return 0. This function should be a private function, but you may need to make it public as you test it. You will want to test it thoroughly before continuing,as subsequent functions will use the function."

I'm honestly just totally lost on this...array based Lists weren't so bad, but I'm just having trouble with this linked list stuff

>> for(int i = 0; i > pos; i++)

That loop is a bug. If pos is greater than 0, then that loop will not execute. If pos is less than or equal to 0, the that loop becomes a infinite loop. What you are looking for is the "<" operator. That is i < pos . You might be getting confused a little bit.

I'm not exactly sure what your getPredecessor function does. Whats its exact purpose?

Ok I see now. Don't be overwhelmed. Before you know it, you will be helping someone out with similar linked list problem.

So lets start :

this function at the end should be private but for testing reason make it public for now :

int LinkedList::getPredecessor(int pos){
};

Now first you want to implement this statement : "If the given position is the first place in the list,the function should return 0."

namely like so :

Node* LinkedList::getPredecessor(int pos){
 if(pos == 0)//we return NULL or 0 since there is no node before the first
   return NULL; 

 //...
};

Now you need to implement this statement :"returns a pointer to the node before that position"

your attempt is close, but this is what you have to do :

Node* LinkedList::getPredecessor(int pos){
 if(pos == 0)//we return NULL or 0 since there is no node before the first
   return NULL; 

  Node* nodeBeforePos = first; 
  for(int i = 0; i < pos - 1; ++i){
      nodeBeforePos = nodeBeforePos->next
  }
  return nodeBeforePos;
};

Lets dissect this new code.

This code : Node* nodeBeforePos = first; declares a Node variable called nodeBeforePos and sets it to point to the first node;
Then this code for(int i = 0; i < pos - 1; ++i) declares a for loop. In which i runs from 0 to pos-1. The reason why its pos-1 is because we want 1 before the pos, therefore we must stop 1 before the pos, in another way stop before pos - 1.
This code nodeBeforePos = nodeBeforePos->next basically advances the node by 1.


Now in your function you were returning an int. It needs to return a Node before pos, thus you should return a Node* instead.

Comments
Very clear, walking me through the steps was very helpful

Does integer mean the number of nodes downstream from the head node or the integer address of a given node? I suspect you want the former, but I can't say for sure.

If you start with a pointer called currentPointer that is assigned the value of first how do you move currentPointer to the second node in the list, and then from the second to the third, etc? Once you figure that out, put it the body of the above loop to move the currentPointer the desired number of times. Then you can assign currentPointer to predptr and you should be all set.

Edit: Ah, the comfort of (almost) simultaneous posts.

Edited 6 Years Ago by Lerner: n/a

This is exactly what I was trying to do, except in my 'if' statement, I compared the ptr and first instead of the pos to NULL/0, plus my confusion with traversing the list. Thanks so much! Lets see if I can finish this code on my own.

Ok I see now. Don't be overwhelmed. Before you know it, you will be helping someone out with similar linked list problem.

So lets start :

this function at the end should be private but for testing reason make it public for now :

int LinkedList::getPredecessor(int pos){
};

Now first you want to implement this statement : "If the given position is the first place in the list,the function should return 0."

namely like so :

Node* LinkedList::getPredecessor(int pos){
 if(pos == 0)//we return NULL or 0 since there is no node before the first
   return NULL; 

 //...
};

Now you need to implement this statement :"returns a pointer to the node before that position"

your attempt is close, but this is what you have to do :

Node* LinkedList::getPredecessor(int pos){
 if(pos == 0)//we return NULL or 0 since there is no node before the first
   return NULL; 

  Node* nodeBeforePos = first; 
  for(int i = 0; i < pos - 1; ++i){
      nodeBeforePos = nodeBeforePos->next
  }
  return nodeBeforePos;
};

Lets dissect this new code.

This code : Node* nodeBeforePos = first; declares a Node variable called nodeBeforePos and sets it to point to the first node;
Then this code for(int i = 0; i < pos - 1; ++i) declares a for loop. In which i runs from 0 to pos-1. The reason why its pos-1 is because we want 1 before the pos, therefore we must stop 1 before the pos, in another way stop before pos - 1.
This code nodeBeforePos = nodeBeforePos->next basically advances the node by 1.


Now in your function you were returning an int. It needs to return a Node before pos, thus you should return a Node* instead.

This article has been dead for over six months. Start a new discussion instead.