Linked Lists

[recluse]

I'm having trouble finding a good tutorial (in c++) on linked lists. Does anybody have any links?

[EscapeCharacter]

have you looked at the examples at codeexamples.org?

[recluse]

Of course I checked out CCAE. I'm always hitting up the guys over their for info. (praise kmj and TheLinuxDuck) But the only example is a doubly linked list. I'm thinking that's quite a bit different than a regular linked list.

[EscapeCharacter]

its pretty much the same except there is no previous pointer

[liquience]

Originally posted by EscapeCharacter
its pretty much the same except there is no previous pointer

this man speaks truth.. i've written both (neither are really all that hard) and the biggest difference is essentially the fact that there is no previous pointer from a node.

[sans-hubris]

Originally posted by recluse
Of course I checked out CCAE. I'm always hitting up the guys over their for info. (praise kmj and TheLinuxDuck) But the only example is a doubly linked list. I'm thinking that's quite a bit different than a regular linked list. No, actually it's not. A properly implemented linked list will only have a few lines to change to become a doubly linked list. Go ahead and look at the doubly linked list, and realize that the only difference is that a regular linked list can't move backwards.

[DrPizza]

It will only have "only a few lines to change" if your implementation is substandard.

The functionality of a singly-linked list is quite a lot less than a doubly-linked list. Some operations that are simple for the latter -- deletion and insertion at arbitrary locations, for instance -- are complicated for the former. Some operations that are simple for the latter -- bidirectional iteration, for instance -- are grossly inefficient for the latter.

Certain aspects of their implementations will be similar (insertions at the end); certain aspects will be very different (iteration -- no need for look-ahead iterators with a doubly linked list).

[sans-hubris]

Originally posted by DrPizza
It will only have "only a few lines to change" if your implementation is substandard.

The functionality of a singly-linked list is quite a lot less than a doubly-linked list. Some operations that are simple for the latter -- deletion and insertion at arbitrary locations, for instance -- are complicated for the former. Some operations that are simple for the latter -- bidirectional iteration, for instance -- are grossly inefficient for the latter.

Certain aspects of their implementations will be similar (insertions at the end); certain aspects will be very different (iteration -- no need for look-ahead iterators with a doubly linked list). Yeah, you're right. I haven't used a linked list of any type in a very long time. There isn't much use for them after you've learnt about more advanced data structures.

[DrPizza]

Yeah, you're right. I haven't used a linked list of any type in a very long time. There isn't much use for them after you've learnt about more advanced data structures.
I don't agree with that.

I would say that there's not a lot of point in writing a linked list class, when you have std::list there for you to use.

[stuka]

mmmm....prebuilt templated doubly-linked lists....mmmmm

[liquience]

Originally posted by DrPizza
It will only have "only a few lines to change" if your implementation is substandard.

The functionality of a singly-linked list is quite a lot less than a doubly-linked list. Some operations that are simple for the latter -- deletion and insertion at arbitrary locations, for instance -- are complicated for the former. Some operations that are simple for the latter -- bidirectional iteration, for instance -- are grossly inefficient for the latter.

Certain aspects of their implementations will be similar (insertions at the end); certain aspects will be very different (iteration -- no need for look-ahead iterators with a doubly linked list).


you're correct. i was, and i think most other people as well, were refering to the data structure.. not so much operations and iterators.

[DrPizza]

A data structure with no interface with which to use it is no use to anyone. When writing the data structure library one necessary creates an interface for that data structure.

[EscapeCharacter]

Originally posted by DrPizza
A data structure with no interface with which to use it is no use to anyone. When writing the data structure library one necessary creates an interface for that data structure.

well that is normally true but there are these people called lazy(me included) and if its not needed for a particular implementation then they will not waste the time on it.

[darelf]

Lazy Programmer == Good Programmer

The Lazy Programmer not only won't waste time on unneeded functionality, they also will code something that works the first time so that they don't have to go back to it over and over again. The Lazy Programmer tests all of the defined use cases and no more. LP makes sure that it works flawlessly and that the documentation for the program is complete so that Clueless Users don't come to him asking questions (and if they do he just says 'RTFM!') For examples, see the GNU tools such as ls, cp, mv, ln, etc.

[sans-hubris]

I have to disagree with you, darelf. An efficient coder is a good coder, not the lazy one. When I use efficient like that, I mean that the coder's code runs efficiently, not that (s)he can code efficiently, although, that's a nice plus.

[sicarius]

now, from the way I see it a singly linked list is not singly linked because it has no back pointer. singly linked lists are singly linked because they only keep a list in one sorted order. A double linked list on the other hand can keep the same set of data sorted two different ways simultaneously. The previous pointer in any list, singly or doubly linked, is merely a convenience so that you don't have to use a temporary variable to store the previous node.

of course above I said "sorted" but the data doesn't have to be sorted. it could just be in the list as it comes...but if you don't care how the data is sorted just use a stack or queue.

[Strike]

Yes, but true stacks and queues don't allow random access to any element like linked lists do. True stacks and queues only allow you to look at one item at any given time. To look at a different item, you have to pop the "top" item off. Sure you can make an implementation that doesn't do that, but then you're basically making a linked list.

[sicarius]

Since when do linked lists allow random access? To have access to any node in the list it would mean having a pointer to every node in the list. Which of course is a logic circle because you would need a list to keep track of the pointers to each node. True stacks and queues do in fact allow for "random access" to any node.
In a linked list you would step through each element until you found what you were looking for. In a stack you would pop elements from the "search" stack onto a temporary stack, when you found the one you wanted you would do your operation, then pop all the elements from the temporary stack back onto the "search" stack. Handling a queue would be somewhat trickier, but in essence you would dequeue elements from the "search" queue and queue them into a temporary queue. After finding your target and performing your operation you would dequeue all elements from the "search" queue and enqueue them into the temporary queue. After which the temporary queue would become the search queue.
So as you can see you can do anything you like with a stack or queue. In fact most of the time stacks and queues are implemented as linked lists...just very strick linked lists in terms of access methods.

[binaryDigit]

Originally posted by sicarius
Since when do linked lists allow random access? To have access to any node in the list it would mean having a pointer to every node in the list. Which of course is a logic circle because you would need a list to keep track of the pointers to each node. True stacks and queues do in fact allow for "random access" to any node.
In a linked list you would step through each element until you found what you were looking for. In a stack you would pop elements from the "search" stack onto a temporary stack, when you found the one you wanted you would do your operation, then pop all the elements from the temporary stack back onto the "search" stack. Handling a queue would be somewhat trickier, but in essence you would dequeue elements from the "search" queue and queue them into a temporary queue. After finding your target and performing your operation you would dequeue all elements from the "search" queue and enqueue them into the temporary queue. After which the temporary queue would become the search queue.
So as you can see you can do anything you like with a stack or queue. In fact most of the time stacks and queues are implemented as linked lists...just very strick linked lists in terms of access methods.

that's funny becuase you just illustrated Strike's point. in a linked list you bounce off of each item until you find the right one without any work other than moving from one item to the next. on a stack you have to take an item move it out of the way and look at the next one. which is what both of you said, just in a little different way.

[Strike]

sicarius, I guess "random access" isn't exactly the appropriate term - you got me there. It's sequential access, but it's nondestructive, unlike in stacks and queues where you either have to be happy with the one element you have access to, or you have to remove it and look again. So yeah, like binaryDigit said, I think we're both thinking of the same thing, but I just screwed up in my terminology.

[sicarius]

righty o