• Advertisement
Sign in to follow this  

linked lists

This topic is 4254 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello there, How do linked lists exactly work? Firstly, I thought you just had a pointer to the first node, the head and then in the head a pointer to the next node and in that node a pointer to the next node and... pHead -> Node -> pNode -> pNode -> pNode -> NULL Then, after I tried some simple examples with them, I got totally confused. I thought it was maybe like this: Node -> Node -> Node -> pHead And when you would add a node, it would look like this: Node -> Node -> Node -> Node -> pHead. I'm in a complete state of flux...:S Can someone please explain this clearly? ~ Stenny

Share this post


Link to post
Share on other sites
Advertisement
Well, either would be valid really, depending on how you were managing the list. You would have a pointer to the head, which would be NULL if the list was empty, then each node would contain a pointer to the next node, or NULL if it is the end of the list.

If you wanted to add to the start of the list (e.g. implementing a stack) you would set the new node to point to the head, then set the head pointer to your new node. A more tradiontal list would add at the end by setting the new node's pointer to NULL and setting the last node's pointer to point to the new node.

I've come across some implementations that use a dummy node as the head so there is always at least one node in the list, and even others that have the last node's pointer point back to the head, although I've never really seen the point.

Sorry if this is all clear as mud but I am not sure exactly what you are asking.

Share this post


Link to post
Share on other sites
The ML approach to a list is as follows.

A list can be:
- An empty list, 'NULL'
- A pointer to a pair (v,n) : the first element is the stored value v while the second element is a list.

Therefore, the list [1; 2; 3; 4; 5] can be represented as:


(1,
(2,
(3,
(4,
(5,NULL)
)
)
)
)


The standard contraption in procedural languages is entirely similar, with the first element in a list being labeled "head", but the pointery thing is less intuitive.

Share this post


Link to post
Share on other sites
@EasilyConfused

It was actually quite clear.

@ToohrVyk

What's the "ML" approach?

@Everyone

Let's say I wanted to create a states system with a

main menu-state
in game-state
inventory-state

I would create a head, that points to the main menu-state, since that's the first one I have. Then the 'ingame-state'-node would be added on top of that, and then the inventorystate-node:

head -> main menu -> ingame -> inventory -> NULL

Is this correct?

Share this post


Link to post
Share on other sites
To be honest, with game states, you would be better to implement that as a stack.

Start with your menu state

Head = menu -> NULL

then add the in-game state at the appropriate time to become the head of the list

Head = in-game -> menu -> NULL

then when the inventory is opened, add the inventory at the top

Head = inventory -> in-game -> menu -> NULL

So that you can "pop" the current state off the top whenever you wish to return to the previous one.


node *head=0;

void add_state(node *n)
{
n->next=head; head=n;
}

void pop_state()
{
assert(head); node *n=head; head=head->next; delete n;
}




Before anyone else says it, you should probably prefer std::list or std::vector with the push_back method, although I can't remember how this works to be honest (boo hiss EasilyConfused admits to implementing his own list structures).

Share this post


Link to post
Share on other sites
So this would be correct (at least good enough)?

#include <iostream>
using namespace std;

class State
{
public:
State* pNext;
};

State* pHead = 0;

void add(State* pState)
{
pState->pNext = pHead;
pHead = pState;
}

void pop()
{
State* pState = pHead;
pHead = pHead->pNext;
}

int main()
{
State mainMenu;
State inGame;
State inventory;

add(&mainMenu);
add(&inGame);
add(&inventory);
pop();

return 0;
}




~ Stenny

Share this post


Link to post
Share on other sites
Quote:
Original post by stenny
What's the "ML" approach?


The ML family of languages is a family of functional languages (that is, functions are the core of the language in every possible way). It has a pretty clean outlook on lists, which it sees as a recursive type easily manipulable through recursive functions.

Quote:

@Everyone

Let's say I wanted to create a states system with a

main menu-state
in game-state
inventory-state

I would create a head, that points to the main menu-state, since that's the first one I have. Then the 'ingame-state'-node would be added on top of that, and then the inventorystate-node:

head -> main menu -> ingame -> inventory -> NULL

Is this correct?


No. From a strictly computerish standpoint, then this is almost what would happen: there would be no "head", only a pointer to the head which would be main menu, but otherwise the the links would be as follows:



Head

(list) ---> Main Menu
(tail) ---> Ingame
(tail) ---> Inventory
(tail) ---> NULL


Even then, this is NOT what you should do.

  • If your goal is to implement a states system, you should use an already-implemented list provided by your language libraries. This takes less programming time, contains less errors that what you (as a novice) would write and runs faster. And it's got more features too.
  • If your goal is to learn how linked lists work, create a linked list instead of "something that uses a linked list" first. If you don't, you'll fail that "something" and not learn much in the process either. If learning is your thing, then limit yourself to a linked list, but code it well.

    So, either way, you should not think of the implementation of a linked list when using one: only the general properties should be thought of.

    Share this post


    Link to post
    Share on other sites
    Quote:
    Original post by stenny
    So this would be correct (at least good enough)?


    Nope... first, your State class has an incorrect name. A better name would be StateAndLinkedListNode, which better reflects its real function and also indicates that there's something wrong going on. Namely, that you're mixing storage responsibility (a linked list job) and storee responsibility (whetever you store in the linked list).


    Other than that:


    State* pState = pHead;
    pHead = pHead->pNext;


    Line 1 serves no purpose and can be removed. Line 2 will cause undefined behavior if pHead is NULL, which is a bad thing.

    Share this post


    Link to post
    Share on other sites
    I am just planning on learning about linked lists. The states were just an example.

    Quote:
    State* pState = pHead;


    Now I see that's unnecessary!

    But 0_o...It's getting wackier each post. How can I learn how a proper linked list is made, if there are more ways to create them!

    ~ Stenny

    Share this post


    Link to post
    Share on other sites
    In the real world, designing things requires making design decisions. Not all design decisions have clear-cut answers.

    However, there is often a common set of answers that are accepted as usually being good enough. And the resulting "solutions" will frequently be provided for common tasks.

    In particular, most "real-world" programming languages will offer some sort of linked list in the standard library. C++ is no exception:


    #include <iostream>
    #include <list>

    using namespace std;

    class State {};

    typedef list<State> states;

    states global_states;

    int main()
    {
    State mainMenu;
    State inGame;
    State inventory;

    global_states.push_back(mainMenu);
    global_states.push_back(inGame);
    global_states.push_back(inventory);
    global_states.pop_back();

    return 0;
    }


    You should be aware that "using a linked list" is itself a design decision. There are more ways to represent a "container" than this, and no one container is right for every situation. The std::list behaves like a linked list (actually, a doubly linked list: pointers are added to the "previous" nodes as well as "next" nodes). There is also std::vector, which is like a resizable array, and std::deque, which is a sort of hybrid of the two. Some containers aren't even "sequential". For example, std::set represents a 'set' of objects in the mathematical sense - it excludes multiple equal copies of an object, and sorts the items (in order to make it faster to do that exclusion) rather than keeping things in the order that you put them in.

    You should also note that the std::list holds actual objects, rather than pointers. (It's common in hand-rolled C linked-list implementations to see a node that consists of a 'next' pointer and a 'data' pointer, so that you can store "lists of anything" without having to edit all your other structures to put in the next-pointers. But this loses huge amounts of type-safety and is also actually less efficient). This is done through the magic of templating. Also you should be aware that objects will be *copied* into the std::list (or any other standard library container, actually). Every now and then this fact does require you to make more design decisions. However, it has the huge advantage that calling code never has to think about how the container is implemented - only what the interface semantics are.

    Using the standard library containers is very highly recommended for almost every circumstance regardless of your level of skill. They take care of all kinds of memory management problems that are just plain no fun (and a waste of time) even for people who are capable of handling them correctly (and proving that their handling is correct). And debugging such problems is *really* no fun - trust me.

    Share this post


    Link to post
    Share on other sites
    Sign in to follow this  

    • Advertisement