First and Last Nodes

This is a discussion on First and Last Nodes within the C++ Programming forums, part of the General Programming Boards category; Hey all, Very quick question, I'm writing a Doubly Linked List, and when it came time to code the Append() ...

  1. #1
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355

    First and Last Nodes

    Hey all,

    Very quick question, I'm writing a Doubly Linked List, and when it came time to code the Append() function, I found I didn't know if the First Node should have its Prev Node set to the Last Node in the list, and visa versa for the Next Node of the Last Node.

    Can someone enlighten me?

    Wow that looks confusing, hope it's not too bad.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  2. #2
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    It depends on if it should be circularly linked or not.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  3. #3
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    Well, in a strange way that's kind of the question I was asking. It just sounds like it would be more efficient when seeking/inserting etc. if I could go quickly from the front to the end, rather than going a long way through.
    But then again also it would probably be just as quick to have a small if statement to check whether it's quicker to go from the First or Last.

    I'm not sure which way to go.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  4. #4
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    Well, you SHOULD have pointers to first and last anyway, and searching would usually go from first to last; why write an algorithm that wrapped around?

    Circularly linked lists are good for circular queues, but if it's just a normal list, I wouldn't.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  5. #5
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    I do have pointers for first and last.
    The thing is if the list was quite large and the user wanted to access the third last node or something it doesn't make sense to go all the way from the first element to the one they want, so I would want to go backwards from the last.

    what I was torn by was whether I should have it check to see which way would be quicker, or if the overhead from that would make it useless, unless the list was REALLY big.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  6. #6
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    If you want to be able to specify "third to the last node" or such, use a std::vector or std::deque, not a doubly linked list.

    In general, linked lists should be used when your only operations are going to be sequential accesses -- "third to the last" works much better with random access structures.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  7. #7
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    Yeah, sorry cat, I just realised while reading my book about List that what I was really doing was a vector, not a list.

    I'm concerned Cat, I can't think of anything decent to program.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  8. #8
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    HybridM:
    what's wrong with doing what you were doing? In this case, who cares if using a vector is "easier". Try to get to where you wanted to go (third node from the back) using the doubly linked list. That's not an unreasonable project. True, it's not the next blockbuster program, but it provides a learning experience, and that's what most of us are after.

    if you really want a project, here's one for you. I thought it was fun and provided me with a valuable learning experience, expecially when alternate source code solutions were posted.

    Assume there is a cube of cheese that consists of 27 cheese cubies, each cubie of size 1 stacked in three layers of 9 cubies each, like a Rubiks cube. You're a mouse trying to eat as much of the cheese as you can by trying eating one cubie at a time starting at any given, arbitrary cubie and going to any adjacent cubie from there, etc. Once you've eaten a cubie you can't go back there again, it's just open space. Eventually you will have eaten all the cubies or end up in a position where there are no more adjacent cubies to eat next even though you haven't eaten all 27 cubies. The solution will be to determine what's the maximum number of cubies you can eat and describe one route to take to reach that number of cubies? Assume you have to start from the exterior of the cube, but you can start at any cubie you wish. Use standard C++ in your program as much as possible.

  9. #9
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    Thanks elad, I might try something like that.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

Popular pages Recent additions subscribe to a feed

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