Jump to content
  • Advertisement
Sign in to follow this  
Ksingh30

linked list

This topic is 4817 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

ok I need to build a linkes list, no prob, but the first part of the node can be apointer to another node called Atom, or it can be a pointer to another list. how do do this in a struct. I tried using enum but that didnt work. http://img385.imageshack.us/img385/4399/14wc.jpg

Share this post


Link to post
Share on other sites
Advertisement
If I understand this right couldn't you just have a pointer to a node, like this:
Node *Next;
Then if it points to a list just make next point to the first element in the list.

EDIT:

Something like this(not tested):

class Node;
class LinkedList
{
public:
Node* GetStart();
Node* GetEnd();
private:
Node* mFirst;
};
class Node
{
public:
void Add(Node* pNode)
{
Node* NextNext = mNext;
mNext = pNode;
mNext->mNext = NextNext;
}
void Add(LinkedList& pList)
{
if( 0 == mNext )
{
mNext = pList.GetStart();
}
else
{
Node* NextNext = mNext;
mNext = pList.GetStart();
pList.GetEnd()->mNext = NextNext;
}
}

Node* mNext;
};


Share this post


Link to post
Share on other sites
so basically have 3 parts to a node. 1 which points to an Atom, 2 which points to another list, 3 which points to the next?

Share this post


Link to post
Share on other sites
Quote:
Original post by Ksingh30
so basically have 3 parts to a node. 1 which points to an Atom, 2 which points to another list, 3 which points to the next?


No. Here's a linked list


Element1---Element2---Element3-----Element4

You want Element3 to point to another list ? Set Element3 to point to the first element of the list and the last of the inserted list's elements to point to Element4:

Element1---Element2---Element3-----NewListEl1-----NewListEl2-----NewListEl3-----Element4.


If What you want is something like this:

Element1---Element2---Element3-----Element4.
|
|---NewListEl1---NewListEl2


You might want to check into other data structures like trees or graphs.

Share this post


Link to post
Share on other sites
Not exactly 3 parts.



[ ] -> [ ] -> [ ] -> ...
data pointer data pointer data pointer ...

OR

[ ] -> [ ] -> [ ] -> ...
[ ] <- [ ] <- [ ] <- ...
data 2ptrs data 2ptrs data 2pts ...

Share this post


Link to post
Share on other sites
Quote:
Original post by xMcBaiNx
Quote:
Original post by Ksingh30
so basically have 3 parts to a node. 1 which points to an Atom, 2 which points to another list, 3 which points to the next?


No. Here's a linked list


Element1---Element2---Element3-----Element4

You want Element3 to point to another list ? Set Element3 to point to the first element of the list and the last of the inserted list's elements to point to Element4:

Element1---Element2---Element3-----NewListEl1-----NewListEl2-----NewListEl3-----Element4.


If What you want is something like this:

Element1---Element2---Element3-----Element4.
|
|---NewListEl1---NewListEl2


You might want to check into other data structures like trees or graphs.


but what if I want to point the element to an Atom, and not a new list?
and I cant use trees, cuz this is the assignment, and I need this to build a LISP interpeter

Share this post


Link to post
Share on other sites
Oh, and what exactly was wrong with a union ?


union pointee {
List* aList
Atom* anAtom
}


Might not be the best solution but it should at least work.

Share this post


Link to post
Share on other sites
Is the "pointer to another list" a pointer to the same type of list (i.e. that list could contain pointers to other lists and so on)? If so, what you *really* have is a binary tree.

Otherwise, I guess you could do something like this: (I will assume, based on your picture, a list of either Nodes or lists of ints):


struct Pointee {
union {
std::list<int> l;
Node n;
}
enum { LIST, NODE } thingPointedTo;
}

std::list<Pointee> theList;

Pointee x = theList.front(); // first thing in the main list
switch (x.thingPointedTo) {
case LIST:
doSomethingWith(x.l.front()); // first int in the sublist
break;
case INT:
doSomethingElseWith(x.n); // the node
break;
}



Unless of course you need to do the actual list implementation yourself for some reason :)

Share this post


Link to post
Share on other sites
a union is a struct where there is only one member stored at a time
( they all have the same memory address )
it occupies as much memory as the largest member

union Value{
int integer;
float floatager;
};

Value value;

if you say

value.integer = 3;

then "floatager" will be garbage( it will assume the bits in value represent a float - they dont )

and if you say

value.floatager = 4.0

then "integer" will be garbage

its a c construct and rarely used.

if you dont know about it then youre probably not ready to use it

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!