Linked Lists Question

This is a discussion on Linked Lists Question within the C++ Programming forums, part of the General Programming Boards category; I'm getting into learning linked lists, and I have a fairly decent grasp on some of it. There is something ...

  1. #1
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,074

    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?
    Last edited by SlyMaelstrom; 11-11-2005 at 09:08 PM.
    Sent from my iPadŽ

  2. #2
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    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.
    Last edited by 7stud; 11-11-2005 at 10:36 PM.

  3. #3
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,074
    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?
    Last edited by SlyMaelstrom; 11-11-2005 at 10:50 PM.
    Sent from my iPadŽ

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    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.
    There are ways to order the nodes that make lookups faster, but the lookups still start at the root node, see here:

    http://cslibrary.stanford.edu/110/BinaryTrees.html

  5. #5
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,074
    Ok, thanks for the link. I'll read it.
    Sent from my iPadŽ

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    The problem is, as you said arrays can't grow in size
    They can if you use memory allocation.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,074
    Can you allocate a specific memory address? ie. The address following the last array element?
    Sent from my iPadŽ

  8. #8
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    You can use realloc in C. In C++, you need to emulate it.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  9. #9
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    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]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  10. #10
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,074
    Quote 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.
    Sent from my iPadŽ

  11. #11
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    Yes, that's right. So many people do this sort of thing that in C there's realloc to do it for you.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  12. #12
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,074
    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?
    Sent from my iPadŽ

  13. #13
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    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.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question regarding comparing two linked lists
    By cyberfish in forum C++ Programming
    Replies: 2
    Last Post: 08-23-2007, 04:28 AM
  2. Linked Lists Question
    By panfilero in forum C Programming
    Replies: 4
    Last Post: 11-22-2005, 12:33 AM
  3. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  4. eof in fstream & singly linked lists
    By mazo in forum C++ Programming
    Replies: 3
    Last Post: 06-03-2002, 09:50 AM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21