It is possible and how to do a linked list without the list itself

Question

0.00/5 (No votes)

See more:

Hi everyone,
So my question is this:
It is possible and how to do a linked list without the list itself?

What I mean by this is on every linked list I can find on the net (I may have missed many) is constructed from two parts, the Node class (or struct) and a list class which containts the list of the linked nodes, managing all of the prev and next objects. So my question is can I have a "linked list" only from the Node class. So the Node class should have *prev and *next and should manage the allocation and dellocation of the *prev and *next objects. Is that even managable and a good idea?

Posted 10-Aug-15 0:17am

xumepoc

Add a Solution

2 solutions

Solution 1

Yes, in "pure" C++ that's pretty simple - you just use pointers.
How to create Linked list using C/C++[^]

Posted 10-Aug-15 0:40am

OriginalGriff

Comments

xumepoc 10-Aug-15 6:48am

And for the deep copy function and the operator= I just need to loop over and use the add to back routine? Also the deconstruct function should do the same, but just delete the next correct?

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Ujesh Mohanan · Accepted Answer · 2015-08-13T07:14:00

Solution 3

While I appreciate you thinking in a different way, I would say that is not a good idea to have a linked 'list' without 'list'. A linked list is basically a list of Nodes linked together. When there is no 'List' class where do you plan to keep the reference to the Head and/or End of the linked list? And where do you plan to implement the Linked List specific functionalities such as traversal, insertion, deletion etc.? Without a 'List' eventually you would end up in implementing a procedural oriented linked list program in C++.

The link that 'OriginalGriff' has shared shows the implementation of a linked list in "pure C". While it is a good start to understand the basics of linked list, it is not the best way to implement a linked list in C++.

Quote:
the Node class should have *prev and *next and should manage the allocation and de-allocation of the *prev and *next objects.

Of course the prev and next pointers should be a part of the Node class. But its not the duty of the Node class to allocate memory for them. Actually *prev and *next are pointers to link a Node to its previous and next Nodes respectively. If a Node itself is responsible for allocating and de-allocating its prev and next pointers, then it would be like a Node creating its previous and next Nodes. In that case the most basic question would be 'Who is responsible for creating the first Node?'

Posted 13-Aug-15 7:14am

Ujesh Mohanan

Updated 13-Aug-15 7:16am

v2

Comments

xumepoc 14-Aug-15 1:26am

Is it mandatory to have a reference to the head and tail node? Shouldn't they be just null? Surly I can find them easy with a simple while loop until reaching the null element?

A second class will take care of the insertions to the list. But I need a Node to live beyond the life of that second class. So let say I have the LinkedList class creating a list of 5 nodes. I need to pass the first node to a another class and store it there. But then if the LinkedList is destroyed and it was his responsibility for the memory management it will delete also that first node, resulting in a unexpected behavior.

Can you explain if possible, why is it wrong and not advisable for the node to create it's prev and next elements? And for the creation of the first Node responsible will be the same class from above.

Ujesh Mohanan 15-Aug-15 4:49am

> Is it mandatory to have a reference to the head and tail node? Shouldn't they be just null? Surly I can find them easy with a simple while loop until reaching the null element?

Nothing is mandatory. It is up to you to decide whether you need them in your program or not. Anyways keeping head and tail pointers have their own advantages. Most of the basic operations on linked list such as insertion, deletion, traversal, sorting, searching etc. requires you to know one end of the list. Running a while loop every time would be a bad idea.

Keep that aside for now and let us consider your while loop technique. From which node will you start the iteration of your loop? Where do you plan to keep the reference to that node?

> A second class will take care of the insertions to the list.

Your original question was about avoiding the list class, which is the second class, right?

> But I need a Node to live beyond the life of that second class. So let say I have the LinkedList class creating a list of 5 nodes. I need to pass the first node to a another class and store it there. But then if the LinkedList is destroyed and it was his responsibility for the memory management it will delete also that first node, resulting in a unexpected behavior.

Why do you want that? Basically what you are expecting here is what we call unexpected. You may take the data out of a node and keep that in some other class, but keeping a node is an entirely different thing. A node contains data and pointers to its next and previous nodes in the linked list. How do you plan to ensure that the Next and Previous of such a node are valid pointers? Who will be responsible for deleting this node? How will you ensure that this node is not stored in some other objects too?

> Can you explain if possible, why is it wrong and not advisable for the node to create it's prev and next elements? And for the creation of the first Node responsible will be the same class from above.

Basically Node is a class and previous node, current node and next node are different objects of the same class. When you allocate memory for *prev and *next from node, you are actually asking one 'object' of a class to create other 'objects' of the same class which spoils the basic purpose of classes and objects.
More over how do you plan to implement this functionality in a Node? And how do plan to manage these objects? Who will keep track of the objects and how? Who will be responsible for deleting these objects? What happens to the next and previous of a node when the node dies? When a node, say node1 creates its previous (say node0) and next (node2) nodes, how do you plan to manage the previous and next part of node0 and node2 (the next of node0 and prev of node2 should be node1)?

xumepoc 15-Aug-15 14:37pm

>Your original question was about avoiding the list class, which is the second class, right?
>Why do you want that? Basically what you are expecting here is what we call unexpected. You may take the data out of a node and keep that in some other class, but keeping a node is an entirely different thing. A node contains data and pointers to its next and previous nodes in the linked list. How do you plan to ensure that the Next and Previous of such a node are valid pointers? Who will be responsible for deleting this node? How will you ensure that this node is not stored in some other objects too?

Well regarding the list class, what I meant was that this class will do the insertion, but will not store the nodes and will not be the one responsible for the memory management. The linked list will be created once based on a specific event and on the second event, will remove the entire list and create it again. But after reading you second question I see that this will be a problem, because there is no way as you said that the third party class using one node will have a valid node or one that was deleted on the rise of the event.

>Basically Node is a class and previous node, current node and next node are different objects of the same class. When you allocate memory for *prev and *next from node, you are actually asking one 'object' of a class to create other 'objects' of the same class which spoils the basic purpose of classes and objects.
More over how do you plan to implement this functionality in a Node? And how do plan to manage these objects? Who will keep track of the objects and how? Who will be responsible for deleting these objects? What happens to the next and previous of a node when the node dies? When a node, say node1 creates its previous (say node0) and next (node2) nodes, how do you plan to manage the previous and next part of node0 and node2 (the next of node0 and prev of node2 should be node1)?

This basically was my question if this was possible and if yes how :) :) :)

I really appreciate you taking from your time answering my questions, I guess I really need to use linkedlist class and node class and work with that....:)