OSDev.org

Posted: **Sat Feb 26, 2011 1:05 pm**

Maybe it's just be being tired or something, but it would seem I've gotten my self in to something that I can't handle.

For the fun of it I decided to experiment with some versatile linked list, or whatever it's called, but things don't work quite as expected. My guess is that there's something I've forgotten or simply don't have a proper understanding of.

Code: Select all

#include <vector>

struct Data {
    // Data
};

class Node {
  public:
    std::vector<Node*> next, prev;
    Data data;
    Node() {}
    Node(Node* ptr) {
        prev.push_back(ptr);
    }
    ~Node() {
        for(int i = next.size() - 1; i >= 0; i--) {
            delete next[i];
        }
        for(int i = prev.size() - 1; i >= 0; i--) {
            delete prev[i];
        }
    }
    void NewNode() {
        next.push_back(new Node(this));
    }
};

int main() {
    Node test;
    test.NewNode(); // This makes things act up.
}

I do hope you can point out my bummer because I've tried everything I could think about.

Best regards.

Edit:
Problem solved by removing the destructor.

I'm not quite sure why as I've learned that manually allocated memory must also be manually freed.

Posted: **Sat Feb 26, 2011 1:33 pm**

A linked list structure should look something like this (in C; I know C++ but I'm not good with OOP):

Code: Select all

struct node* {
	void*			data;
	struct node*	next;
};

or

Code: Select all

struct node* {
	void*			data;
	struct node*	prev;
	struct node*	next;
};

for a doubly-linked list.

I'll explain how doubly linked lists work. I have yet to find a use for a singly-linked list.

The idea is that you start with a single node:

Code: Select all

struct node* list;

To add a node, you do something like

Code: Select all

void add_node(void* data)
{
	struct node* new_node = malloc(sizeof(struct node));
	new_node->data = data;
	new_node->prev = list;
	new_node->next = NULL;
	list->next = new_node;
	list = new_node;
}

Then new_node is at the end of the list.

To traverse the list you can do something like:

Code: Select all

void cycle_left(void)
{
	if (list->prev)
		list = list->prev;
}

void cycle_right(void)
{
	if (list->next)
		list = list->next;
}

Out of those three functions you can build a pretty flexible linked list implementation. And if you add an identifying string (called a keystring) to each node, you can implement something like Perl's hashes or Python's dictionaries.

Posted: **Sat Feb 26, 2011 1:46 pm**

Thank you very much for the walk through, however, I have read quite a bit about linked lists and I'm afraid I didn't learn anything new here.

The whole idea was to allow for and unknown number of "links", for which I've chosen to use vectors. What I've posted has only been in the works for an hour or so and thus is nowhere near anything useful. Still, the basics should be there.

I'm quite sure that I've messed up with some pointers, but as I wrote earlier, I've been unable to locate the error.

Obviously my approach isn't like the usual that you have described, but I see no reason why it shouldn't be possible to do it my way. Of course if there's a fundamental flaw in my think, I'd very much like to know.

Posted: **Sat Feb 26, 2011 1:57 pm**

If you just want to use a linked list to implement a structure on top of it, then use the STL list class, just #include <list> and you can declare one like:

Code: Select all

std::list<int> a;
a.push_back(3);

If you want to implement one, you don't need to use vectors, since you will be able to tell if a given link is the last one if its next pointer is NULL. This allows for an arbitrary amount of nodes. Bi-directional linked lists work in a similar way. I would prototype a basic one like this:

Code: Select all

class node
{
public:
    node(int data, node *next);
    ~node();

    void insert_end(int data);
private:
    int data;
    node *next;
};

//As an example, here is an implementation of insert_end
// I didn't test it so I don't know if it works though
void node::insert_end(int edata)
{
    node *cur;

    cur = this;
    while(cur->next != NULL)
        cur = cur->next;

    //Insert a new node at the end
    cur->next = new node(edata, NULL);
}

You could use templates to enable holding a generic data type, but I didn't want to clutter up the code with template<typename T>'s.

Posted: **Sat Feb 26, 2011 2:07 pm**

Zacariaz wrote:Thank you very much for the walk through, however, I have read quite a bit about linked lists and I'm afraid I didn't learn anything new here.

The whole idea was to allow for and unknown number of "links", for which I've chosen to use vectors. What I've posted has only been in the works for an hour or so and thus is nowhere near anything useful. Still, the basics should be there.

I'm quite sure that I've messed up with some pointers, but as I wrote earlier, I've been unable to locate the error.

Obviously my approach isn't like the usual that you have described, but I see no reason why it shouldn't be possible to do it my way. Of course if there's a fundamental flaw in my think, I'd very much like to know.

Well, I don't understand why you would use vectors. A linked list is a container in itself, it shouldn't need to use another container.

Maybe it would help you to visualise it. Look at this: http://i55.tinypic.com/erym92.png
Forwards: NODE1->next = NODE2; NODE2->next = NODE3; NODE3->next = NODE4; NODE4->next = NULL
Backward: NODE4->prev = NODE3; NODE3->prev = NODE2; NODE2->prev = NODE1; NODE1->prev = NULL

It took me a while to understand linked lists, too. It just sort of clicked one day.

Posted: **Sat Feb 26, 2011 2:13 pm**

I'm not sure we understand each other here.

I'm talking here about a doubly linked list (obviously), but with the options for multiple links in both directions allowing for a rather advanced tree structure with the possibility for loops, circularity or whatever it's called, thus the need for the possibility for multiple links back.

I'll be sure to check out std:list in any case. Never have before and that's probably a rather big mistake.

@Synon:

The vectors are to allow for an undefined number of links.

ex.

Code: Select all

  a 
/   \__
b   c  \
/\  |  |
e f g  |
|  /|\_/
h i j

I'll take a look at the link anyway.

Thanks

Posted: **Sat Feb 26, 2011 2:33 pm**

So, you want to make graph? Directed graph to be more precise.
About your code, your destructor looks very weird and it should produce double free-s. I'm not sure if destructor is actually necessary.

Posted: **Sat Feb 26, 2011 2:40 pm**

jrepan wrote:So, you want to make graph? Directed graph to be more precise.
About your code, your destructor looks very weird and it should produce double free-s. I'm not sure if destructor is actually necessary.

Neither was I. I know that the vector cleans up after it self, but as the vector is not responsible for allocation memory for the data it self, I should think that this will have to be handled somewhere else, however, removing the destructor all together seem to solve the problem, so thank you for that hint. Don't know why I didn't think of it my self

Regarding the term "graph" I've never heard that used in combination with this subject, but you can be sure I'll see what google can find for me

Thanks again.

edit:

"graph" was really the keyword here. I can't tell you how long I've been searching for it

Thanks a bunch.

Posted: **Sat Feb 26, 2011 2:43 pm**

Zacariaz wrote:
The vectors are to allow for an undefined number of links.

So does a normal linked list.

Posted: **Sat Feb 26, 2011 2:49 pm**

Synon wrote:
Zacariaz wrote:
The vectors are to allow for an undefined number of links.
So does a normal linked list.

Please correct me if I'm wrong.

Linked lists as they're normally viewed, got a static number of links, ex. 2 back 6 forward, but normal examples will a maximum of one in each direction. I could make an implementation with a billion links, but what if I need one more?

In any case I think that jrepan is right. "graph" is the term I'm looking for here.

Posted: **Sat Feb 26, 2011 3:05 pm**

Zacariaz wrote:
Synon wrote:
Zacariaz wrote:
The vectors are to allow for an undefined number of links.
So does a normal linked list.
Please correct me if I'm wrong.

Linked lists as they're normally viewed, got a static number of links, ex. 2 back 6 forward, but normal examples will a maximum of one in each direction. I could make an implementation with a billion links, but what if I need one more?

A linked list can have a theoretically infinite number of nodes (I say theoretically because you are limited by available memory). All you do is add another one (hence my add_node function in the above example).

Posted: **Sat Feb 26, 2011 3:14 pm**

I'm not talking about the number of nodes here, but the structure of the list. http://en.wikipedia.org/wiki/Graph_(data_structure)

Posted: **Sat Feb 26, 2011 3:23 pm**

Zacariaz wrote:I'm not talking about the number of nodes here, but the structure of the list. http://en.wikipedia.org/wiki/Graph_(data_structure)

But your argument for why you're using vectors is that vectors have a dynamic number of links/nodes. I'm telling you that linked lists do as well. You start with one node, and then you add as many as you want to. And then you can remove some. Or add some more.

Posted: **Sat Feb 26, 2011 3:28 pm**

In my language links and nodes are two different things. I don't think we will come to an understanding here. It may or may not be my fault as I'm not always the best at explaining things, but the problem is solves and furthermore I now know the name of the concept that I'm actually interested in.

edit:
Oh and I might as well use an array instead of a vector, if it weren't so damn difficult to expand it.

Maybe that explains a bit.

Posted: **Sat Feb 26, 2011 3:31 pm**

Zacariaz wrote:In my langu7age links and nodes are two different things. I don't think we will come to an understanding here. It may or may not be my fault as I'm not always the best at explaining things, but the problem is solves and furthermore I now know the name of the concept that I'm actually interested in.

By links, I assume you mean a link between two nodes? I thought you were trying to understand the concept of a linked list...

OSDev.org

Linked lists and stuff (C++)

Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)

Re: Linked lists and stuff (C++)