Thread: Linked Lists Question

I'm getting into learning linked lists, and I have a fairly decent grasp on some of it. There is something I'm wondering though. Is there a way to index the nodes in a linked list without refering to it's distance from the root node?

For instance, the only way I know how to get to a specific node is to reset the pointer that goes through the list to point to the root node, then do Ptr = Ptr->next as many times as I need to get to the correct node.

Code:

int count = 0;
transPtr = root;  
   
if ( transPtr != 0 ) {
   while ( transPtr->next != 0 && count != x) {
       transPtr = transPtr->next;
       count++;
   }
}

Is there a better way of doing this?

Edit: Also, I hate trying to figure this stuff out from a small tutorial, does anyone know a good place to go to get linked lists in detail?

I'm getting into learning linked lists, and I have a fairly decent grasp on some of it. There is something I'm wondering though. Is there a way to index the nodes in a linked list without refering to it's distance from the root node?

Sure, it's called an array. Whoops! An array name is a pointer to the first element and the elements of the array are offsets in memory relative to the first element. The size of the offsets is equivalent to the size of the type stored in the array. In addition, an array doesn't let you grow its size--an array's size is set when it's created because the compiler has to allocate a contiguous section of memory for the array, so that the offsets from the start will be array elements.

You could create a list pointer called middle and have it point to, say, the 5th node added to the list. Then you could search for nodes starting at middle and going to the end of the list. But if the node you are looking for is one of the first 4 nodes, you'll conclude the node isn't in the list when it actually is.

I think that leaves you with getting a random number, using it to create a memory address, and then accessing that memory address and hoping the node you want is there.

Well I know about arrays, thank you.

The problem is, as you said arrays can't grow in size. ... which is one of the main advantages of linked lists in the first place.
The second suggestion of creating a middle node as you said also has it's faults.

So, if this is it, I guess I could conclude there isn't a much better way of reaching specific nodes in the list? I mean, it's not like running the loop I showed 100,000s of times would be more than barely measurable, but it just seems like a shame that there is no way to really index them better.

Edit: Also, is there proper syntax with 'new' that can be used similar to malloc() to specify the size of the memory you want to reserve? All I know is using datatypes, like 'new int' or 'new <struct name>', but malloc can do things like malloc(sizeof(int) * 10). Can you do that with new?

Ok, thanks for the link. I'll read it.

The problem is, as you said arrays can't grow in size

They can if you use memory allocation.

Can you allocate a specific memory address? ie. The address following the last array element?

You can use realloc in C. In C++, you need to emulate it.

Look:

Code:

int *x = new int[10], i, *n;
/* x is an array of 10 ints here */
n = new int[20];
for(i = 0; i < 10; i ++) n[i] = x[i];
delete [] x;
x = n;
/* x is an array of 20 ints here */
delete [] n;

[edit]
In C:

Code:

int *x = malloc(sizeof(int) * 10), *n;
/* x is an array of 10 ints here */
n = realloc(x, 20);
if(!n) exit(1);
x = n;
/* x is an array of 20 ints here */
free(x);

[/edit]

Originally Posted by dwks

Look:

Code:

int *x = new int[10], i, *n;
/* x is an array of 10 ints here */
n = new int[20];
for(i = 0; i < 10; i ++) n[i] = x[i];
delete [] x;
x = n;
/* x is an array of 20 ints here */
delete [] n;

So your dynamically allocating a new array of the size you want, transferring the info from your old array into the new one, deleting the memory of the old one (leaving a null pointer?) and then switching the pointer of the 20 element array to the old pointer.

Correct?

Thanks for this, by the way.

Yes, that's right. So many people do this sort of thing that in C there's realloc to do it for you.

Code:

if(!n) exit(1);

What causes realloc() to fail that you decided that you should check to see if it's still pointing to null?

realloc() returns NULL, like malloc(), when no memory is available.

This code

Code:

char *i, *p;
p = realloc(i, 20);

is better than this

Code:

char *i;
i = realloc(i, 20);

because if realloc returns NULL and you use the latter, you loose whatever i was pointing to before the realloc call.