linked lists
Author
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
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.
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.
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:
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.
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.
Author
@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?
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?
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.
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).
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).
Author
So this would be correct (at least good enough)?
~ Stenny
#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
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) ---> NULLEven then, this is NOT what you should do.
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.
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.
Author
I am just planning on learning about linked lists. The states were just an example.
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
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
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:
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
