Adding index counter to linked list

[Daniel Vukadinovic]

I want to implement an index/counter to my linked list.
Why? I wrote a search function which searches the list for elements
based on their values (say I add an element and I assign the value 54
and the next element 789 and so on...) now I'd like to write a search
function which would search the list for elements based on their index.

Say first element is 54 and index 1, second element is 789 and index 2
so when I want to search, I'll do Search index: 2 and it will return
789.

How should I do that? I was thinking of making a global int counter = 0
and then in the add_to_beginning function I would do counter++ and the
same with other functions but that would only increment the counter, it
wouldn't index my elements.

Please, no pre-made libraries or OOP.I'm doing this with structures,
then I'll move to OOP.

 

[Daniel Vukadinovic]

This is what I got:

void searchindex(node*& p_beginning, int index)
{
int counter;
node* p_temp = p_beginning;

while (p_temp != 0)
{
if (p_temp->element == index)
{
cout << counter; or return counter; (int instead od void)
}
else
{
p_temp = p_temp->p_next;
counter++;
}
}
}

When I search it returns nothing and gets back to the menu.

 

[Victor Bazarov]

This is what I got:

void searchindex(node*& p_beginning, int index)
{
int counter;

Note that 'counter' is uninitialised. At best it contains some valid
value, but not what you think. At worst, the value it contains is
a trap value which can cause your computer to blow up. In any case,
the behaviour of your program is undefined if you use that value.

node* p_temp = p_beginning;

while (p_temp != 0)
{
if (p_temp->element == index)
{
cout << counter; or return counter; (int instead od void)

And here you try to return a value of an uninitialised variable.

}
else
{
p_temp = p_temp->p_next;
counter++;

And here you're incrementing an unintialised variable.

}
}
}

When I search it returns nothing and gets back to the menu.

No surprise.

V

 

[Daniel Vukadinovic]

I did counter = 0; but I still don't get anything.
Am I doing this the right way? I mean, the whole indexing thing.

 

[Marcus Kwok]

Your first post:

I want to implement an index/counter to my linked list.
Why? I wrote a search function which searches the list for elements
based on their values (say I add an element and I assign the value 54
and the next element 789 and so on...) now I'd like to write a search
function which would search the list for elements based on their index.

Say first element is 54 and index 1, second element is 789 and index 2
so when I want to search, I'll do Search index: 2 and it will return
789.

This is what I got:

void searchindex(node*& p_beginning, int index)
{
int counter;
node* p_temp = p_beginning;

while (p_temp != 0)
{
if (p_temp->element == index)

Based on your first post, why are you looking at p_temp->element? In
your example, if index == 2, then element == 789. These are not equal,
so you continue looping until you hit the end of the list, or until
coincidentally the index and the element are the same.

 

[pillbug]

I want to implement an index/counter to my linked list.
Why? I wrote a search function which searches the list for elements
based on their values (say I add an element and I assign the value 54
and the next element 789 and so on...) now I'd like to write a search
function which would search the list for elements based on their index.

Have you considered implementing this a bit differently?

template<class Value>
struct Node
{
Value value;
int next;
};

then allocate an array of these guys, and use indexes as your links
rather than pointers to nodes.

so your array might look like:

begin = 2
array[0] =: Node<int> { 10000, 3 }
array[1] =: Node<int> { 10001, -1 }
array[2] =: Node<int> { 10002, 0 }
array[3] =: Node<int> { 10003, 1 }

and now you have your O(1) random access along with the O(N) seqeuntial
lookup. this is of course extendible to any number of O(N) indexing
schemes, but may not be useful depending on your insert/delete requirements.

you might also try comp.programming as this is clearly not just a c++
problem as my crappy little psuedo code demonstrates :-\

 

[Markus Schoder]

This is what I got:

void searchindex(node*& p_beginning, int index)
{
int counter;
node* p_temp = p_beginning;

while (p_temp != 0)
{
if (p_temp->element == index)
{
cout << counter; or return counter; (int instead od void)
}
else
{
p_temp = p_temp->p_next;
counter++;
}
}
}

When I search it returns nothing and gets back to the menu.

I am guessing here but maybe the below is what you want i.e. finding
the index-th element:

void searchindex(node*& p_beginning, int index)
{
int counter = 0;
node* p_temp = p_beginning;

while (p_temp != 0)
{
if (counter == index)
{
cout << p_temp->element; // or return p_temp->element;
}
else
{
p_temp = p_temp->p_next;
counter++;
}
}
}

 

[Markus Schoder]

Daniel Vukadinovic wrote:
I am guessing here but maybe the below is what you want i.e. finding
the index-th element:

void searchindex(node*& p_beginning, int index)
{
int counter = 0;
node* p_temp = p_beginning;

while (p_temp != 0)
{
if (counter == index)
{
cout << p_temp->element; // or return p_temp->element;
}
else
{
p_temp = p_temp->p_next;
counter++;
}
}
}

Need to add a return after the cout to avoid an infinite loop.

 

[Daniel Vukadinovic]

pillbug: That's too complicated.
Markus: That's what I did after I modified the code and as a result,
when search, my screen gets flooded with numbers.

 

[Daniel Vukadinovic]

Yes, return helps.Thanks!
Thank you all for helping me!