-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0|683|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
SoCoder -> Snippet Home -> Misc


 
JL235
Created : 07 October 2007
Edited : 07 October 2007
System : Windows
Language : Blitz

Algorithms: Linked List Example



Here is an example of how to implement a simple linked list. It also uses recursion to implement some of the functions. For example there are two reverse functions, one which uses iteration and one which uses recursion.


 

Comments


Sunday, 28 October 2007, 12:29
mike_g
Dosent Blitz automatically do lists for you? Everytime you create a new object its added to the end of the list. To put it at the start of the list you just do something like:

Its been a while since i used blitz so that might be wrong, but its something like that.
Sunday, 28 October 2007, 14:24
JL235
Yes, but the point of the example is not how to make your own lists in Blitz Basic, but how to make a linked list in general. I used Blitz Basic as the language for this example since so many people use it.

It's useful to know how to implement things like Linked Lists and Binary Trees yourself because there might be times when you do have to implement your own custom data structure.

Perhaps BB wasn't the best language to chose since most languages don't have lists built directly into the language itself (it's usually in some sort of standard library to the language). Haskell is the only other language I know of which has a linked list built directly into it, although it doesn't support arrays (as far as I am aware).
Tuesday, 30 October 2007, 03:00
JL235
With a single-linked list you can still traverse it in reverse order through using recursion. I do that with the PrintListReverse function.

The reason I have a variable to hold the last item in the list is so if I want to add something to the end of the list I do not have to iterate over the entire list in order to find the last node. I would still have to keep that variable even if it was doubly-linked.

If it was doubly-linked and I wanted to traverse it in reverse without using recursion, again I'd still need the lastNode variable in order to know where to start my iteration.
Tuesday, 30 October 2007, 16:24
JL235
Ok, why is there no point storing the lastNode in a single-linked list but there is for a doubly-linked list?

Also, apart from using a variable to store the last value of the list or iterating through the whole list to find the last variable, how could I know the last element of the list in order to start traversing it in reverse?

The only other option I can see would be to connect the first and last nodes together. However this changes the functionality of the list as null is no longer used for when you run out of items.
Wednesday, 31 October 2007, 11:12
JL235
Well I'm genuinely interested in this topic. However your saying my example could be better and then refusing to explain how.