Linked Lists
I'm a little confused about creating an insert method. What I've discovered is you have to traverse the list to find certain things. What makes this very confusing is if I want to put something in a certain spot, if I don't stop in time, I go too far. And if I go too far, I cannot insert what I want in the right spot. I'm actually more curious about something simpler. If I want to put something in the 3rd position. I need to stop on the second element and do the pointer rearranging, correct?
Correct. Inserting first and last elements are somewhat* special cases. For all other insertions you need to know the two nodes between which you want to insert something.
*You could easily write a function insert(n1, n2) that takes two nodes and inserts one between them in such way that when passed (NULL, first_node) it would correctly insert before first and same for (last_node, NULL), rather than look at 3 different cases.
*You could easily write a function insert(n1, n2) that takes two nodes and inserts one between them in such way that when passed (NULL, first_node) it would correctly insert before first and same for (last_node, NULL), rather than look at 3 different cases.
What if I had a class that abstracted away that and just had a node class, creating the node object, and then a list class that just did the managing of the nodes? Would that still be possible, seeing how your parameters for said function would use an object of node objects as its data?
EDIT:
I MEAN TWO CLASSES, ONE THE NODE, THEN ONE WITH MANAGING THE NODES. MANAGING CLASS WOULD HAVE METHODS TO INSERT, APPEND, SIZE, AND SUCH.
EDIT:
I MEAN TWO CLASSES, ONE THE NODE, THEN ONE WITH MANAGING THE NODES. MANAGING CLASS WOULD HAVE METHODS TO INSERT, APPEND, SIZE, AND SUCH.
Last edited on
That's the right way. You'd have class Node with Node* fields prev, next and a class List with Node* fields head, tail and all the functionality. Although if you're making a singly linked list, one class is enough.
Hamsterman wrote:
In my opinion, not only is that the right way, it is the ONLY way!
I am learning linked lists right now. What broke it open for me was finally understanding that the nodes and the list itself need separate classes. I strongly disagree that one class is enough for even a singly linked list. At least 2 classes are needed.
The person who explained it to me preaches that you need a different class for each object or group of closely related objects, and each task or group of closely related tasks. I am an avid believer in that now.
| That's the right way. You'd have class Node with Node* fields prev, next and a class List with Node* fields head, tail and all the functionality. Although if you're making a singly linked list, one class is enough. |
In my opinion, not only is that the right way, it is the ONLY way!
I am learning linked lists right now. What broke it open for me was finally understanding that the nodes and the list itself need separate classes. I strongly disagree that one class is enough for even a singly linked list. At least 2 classes are needed.
The person who explained it to me preaches that you need a different class for each object or group of closely related objects, and each task or group of closely related tasks. I am an avid believer in that now.
Thanks, I got it to work. I had to draw some memory on my notepad to make sure I had the right stuff being assigned where, but it works!
Just a note. You do not need classes to implement a linked list. I don't believe the first programming languages had classes as a language feature. I also don't believe that OO languages were the first languages to utilize linked lists.
I'm well aware. But what classes allow you to do is abstract out certain things. I could easily have my insert, append, delete, and other class methods as regular functions outside of a class. I however feel that classes is a genuinely useful idea. It allows you to group stuff together allowing more streamline access. Its also easier to debug and better(neater) to code.
@nathan, you're being silly. Classes and even structs are just for comfort. What you can do with them, you can do without them. Although code not using structs will be very unsafe..
A singly linked list of one class is very natural. The second class could only be there to hide utility functions.
A singly linked list of one class is very natural. The second class could only be there to hide utility functions.
@hamsterman,
Then silly I will be! I am not a master professional programmer nor have I mastered linked lists. I only know from the experience of a learner that the use of classes made the understanding of linked lists and my writing of a singly linked list MUCH easier.
I am trying to write a doubly linked list program now and I would be utterly lost if I had not used 2 classes to learn the singly linked list. I do not recommend trying to learn linked lists without classes to any newbie. But YMMV because I am being silly and am not very smart.
PS
I will leave to another thread discussion of whether the objective of the OP and subsequent posters is simply to complete an academic assignment for a grade or to acquire a skill that will be used in a professional programming life.
Then silly I will be! I am not a master professional programmer nor have I mastered linked lists. I only know from the experience of a learner that the use of classes made the understanding of linked lists and my writing of a singly linked list MUCH easier.
I am trying to write a doubly linked list program now and I would be utterly lost if I had not used 2 classes to learn the singly linked list. I do not recommend trying to learn linked lists without classes to any newbie. But YMMV because I am being silly and am not very smart.
PS
I will leave to another thread discussion of whether the objective of the OP and subsequent posters is simply to complete an academic assignment for a grade or to acquire a skill that will be used in a professional programming life.
Topic archived. No new replies allowed.