Algorithms: Linked List Example

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|674\|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. Type List Field firstNode.Node Field endNode.Node End Type Type Node Field value Field nextNode.Node End Type ; NewList ; creates and returns a new list type Function NewList.List() Local list.List = New List list\firstNode = Null list\endNode = Null Return list End Function ; AddToStart ; adds the given value onto the beginning of ; the given list Function AddToStart(value, list.List) Local n.Node = New Node n\nextNode = list\firstNode n\value = value list\firstNode = n If list\endNode = Null Then list\endNode = n End Function ; AddToEnd ; adds the given value onto the end of the ; given list Function AddToEnd(value, list.List) Local n.Node = New Node n\nextNode = Null n\value = value If list\firstNode = Null list\firstNode = n list\endNode = n Else list\endNode\nextNode = n list\endNode = n EndIf End Function ; Print List ; prints the given list forwards Function PrintList(list.List) printNode list\firstNode End Function ; don't use, ; this is a helper function ; for the Print List function Function PrintNode(node.Node) If Not node = Null Print node\value printNode node\nextNode EndIf End Function ; Print List Reverse ; prints the given list backwards Function PrintListReverse(list.List) printNodeReverse list\firstNode End Function ; don't use, ; this is a helper function for ; the PrintListReverse function Function PrintNodeReverse(node.Node) If Not node = Null printNodeReverse node\nextNode Print node\value EndIf End Function ; Reverse List ; reverses the given list using iteration Function ReverseList(list.List) Local node.Node = list\firstNode Local lastNode.Node = Null While Not node = Null Local nextNode.Node = node\nextNode node\nextNode = lastNode lastNode.Node = node node = nextNode Wend Local firstNodeCopy.Node = list\firstNode list\firstNode = list\endNode list\endNode = firstNodeCopy End Function ; ReverseListRecursively ; reverses the given list using second ; a recursive function Function ReverseListRecursively(list.List) ; recursively swap each node in the list ReverseNodeRecursively list\firstNode ; make the first node point to null list\firstNode\nextNode = Null ; swap first and end Nodes firstCopy.Node = list\firstNode list\firstNode = list\endNode list\endNode = firstCopy End Function ; Do not use, this is a helper function ; for the above ReverseListRecursively function Function ReverseNodeRecursively(n.Node) ; this line should be if not (n = null and n\nextNode = null) ; but Blitz doesn't do short circuiting If Not n = Null If Not n\nextNode = Null ReverseNodeRecursively n\nextNode n\nextNode\nextNode = n EndIf EndIf End Function ; -------------------- ; example usage ; -------------------- Local myList.List = newList() For i = 1 To 10 AddToEnd i, myList Next Graphics 640, 480, 0, 2 Print "print list forward:" PrintList(myList) Print "reverse list and then print forwards:" ReverseListRecursively(myList) PrintList(myList) Print "print reversed list, backwards:" PrintListReverse(myList) WaitKey End --v

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: Insert n.newThing Before First n --v 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.

Algorithms: Linked List Example

Comments