Code archives/Algorithms/Container: double-linked list
This code has been declared by its author to be Public Domain code.
Download source code
| |||||
This library makes it painless to add many independant linked lists for many different types of objects. This is done by storing Handle()s to your objects. Each container should hold objects of only one type. For more information on containers, an example of how to use them, and a tutorial, click here. A linked list is similar to an array, but you don't have to worry about its size and you cannot reference elements randomly. Removing or inserting an element anywhere in the list is a quick operation because only the adjacent elements need to change. Finding an element at a numbered location is a slow operation because the list must be "walked" to get there. A double linked list can also be used as a queue or a stack. (Blitz provides built-in linked lists for every created object, but they are limited in that you only get one list per custom type and they always contain all the elements of that type.) For an example of how to use this library, scroll down to the test() function at the very bottom. This code will run standalone if you uncomment the line at the top which runs the test code. Please post bugs or feature requests in comments. Fundamentals list_new.listC() - create a new list list_destroy(our_list.listC) - delete a list and all of its nodes Standard Operations list_push.listC_node(our_list.listC, value) - add a new node to the end of a linked list list_unshift.listC_node(our_list.listC, value) - add a new node to the beginning of a linked list list_pop(our_list.listC) - remove an element from the end of a linked list, returning its value list_shift(our_list.listC) - remove an element from the beginning of a linked list, returning its value list_insert_after.listC_node(reference_node.listC_node, value) - add a new node after an existing one list_insert_before.listC_node(reference_node.listC_node, value) - add a new node before an existing one list_remove_node(our_node.listC_node) - remove an arbitrary element from a linked list, returning its value list_count(our_list.listC) - return the number of elements in the list Iterators ; for item.type = each our_list it.listC_iter = list_iterator_begin(our_list) while list_iterator_next(it) item.type = object.type(list_iterator_get(it)) ; do stuff with item wend list_iterator_begin_reverse.listC_iter(our_list.listC) - create a new iterator for traversing the list backwards Convenience list_find_node_by_value.listC_node(our_list.listC, value) - find the first node in a list matching the value given list_find_node_by_position.listC_node(our_list.listC, index) - find the Nth node in a list --- The Code | |||||
;list_test() ; ------------------------------------------------------------------------------ ;= TO DO ; ------------------------------------------------------------------------------ ; iterator sanity checking (try to catch problems which might be caused by deleting elements while iterating) ; ------------------------------------------------------------------------------ ;= CHANGE LOG ; ------------------------------------------------------------------------------ ; 12/11/2005 - iterator sample usage for quick copying and pasting ; 12/11/2005 - list_find_node_by_position() ; 06/11/2005 - new() for forwards compatibility ; 06/11/2005 - dropped humpBack notation in favour of under_score ; 03/11/2005 - renamed class from listType ; 02/11/2005 - iterators now treat null list objects as empty lists ; 12/08/2005 - fixed iterators to work with empty lists, added list_unshift() and list_destroy() ; 16/08/2005 - added list_insertBefore(), list_insertAfter(), list_findNodeByValue(). ; revised iterators to allow: multiple simultaneous iterators, reverse iterators, ; safe deletion of the current node (not safe with multiple iterators!) ; ------------------------------------------------------------------------------ ;= TYPES ; ------------------------------------------------------------------------------ type listC field elements% ; number of elements in list field first_node.listC_node field last_node.listC_node end type type listC_node field list.listC ; parent list field prev_node.listC_node ; or null if this is the first node field next_node.listC_node ; or null if this is the last node field value end type type listC_iter field list.listC field forwards ; bool to keep track of which direction we're going field current_node.listC_node field next_node.listC_node ; keep track of this so we can safely delete the current_node end type ; ------------------------------------------------------------------------------ ;= FUNDAMENTAL ; ------------------------------------------------------------------------------ ; ------------------------------------------------------------------------------ function list_new.listC() ; create a new list return new listC end function ; ------------------------------------------------------------------------------ function list_destroy(our_list.listC) ; delete a list and all of its nodes if our_list = null then runtimeerror("not a valid listC: null") ; walk through the nodes, deleting them this_node.listC_node = our_list\first_node while (this_node <> null) old_node.listC_node = this_node this_node = this_node\next_node delete old_node wend ; finally, delete the list itself delete our_list end function ; ------------------------------------------------------------------------------ function list_push.listC_node(our_list.listC, value) ; add a new node to the end of a linked list if our_list = null then runtimeerror("not a valid listC: null") ; create a new node local our_node.listC_node = new listC_node our_node\list = our_list our_node\value = value ; if the list is empty, set our node as the first and last if (our_list\first_node = null) then our_list\first_node = our_node our_list\last_node = our_node our_list\elements = 1 ; otherwise, add our node after the last else our_list\last_node\next_node = our_node our_node\prev_node = our_list\last_node our_list\last_node = our_node our_list\elements = our_list\elements + 1 endif return our_node end function ; ------------------------------------------------------------------------------ function list_unshift.listC_node(our_list.listC, value) ; add a new node to the beginning of a linked list if our_list = null then runtimeerror("not a valid listC: null") ; create a new node local our_node.listC_node = new listC_node our_node\list = our_list our_node\value = value ; if the list is empty, set our node as the first and last if (our_list\first_node = null) then our_list\first_node = our_node our_list\last_node = our_node our_list\elements = 1 ; otherwise, add our node before the first else our_list\first_node\prev_node = our_node our_node\next_node = our_list\first_node our_list\first_node = our_node our_list\elements = our_list\elements + 1 endif return our_node end function ; ------------------------------------------------------------------------------ function list_pop(our_list.listC) ; remove an element from the end of a linked list, returning its value return list_remove_node(our_list\last_node) end function ; ------------------------------------------------------------------------------ function list_shift(our_list.listC) ; remove an element from the beginning of a linked list, returning its value return list_remove_node(our_list\first_node) end function ; ------------------------------------------------------------------------------ function list_insert_after.listC_node(reference_node.listC_node, value) ; add a new node after an existing one if reference_node = null then runtimeerror("not a valid listC_node: null") ; create a new node local our_node.listC_node = new listC_node our_node\list = reference_node\list our_node\value = value our_node\prev_node = reference_node our_node\next_node = reference_node\next_node reference_node\next_node = our_node if our_node\next_node <> null then our_node\next_node\prev_node = our_node else our_node\list\last_node = our_node endif our_node\list\elements = our_node\list\elements + 1 return our_node end function ; ------------------------------------------------------------------------------ function list_insert_before.listC_node(reference_node.listC_node, value) ; add a new node before an existing one if reference_node = null then runtimeerror("not a valid listC_node: null") ; create a new node local our_node.listC_node = new listC_node our_node\list = reference_node\list our_node\value = value our_node\next_node = reference_node our_node\prev_node = reference_node\prev_node reference_node\prev_node = our_node if our_node\prev_node <> null then our_node\prev_node\next_node = our_node else our_node\list\first_node = our_node endif our_node\list\elements = our_node\list\elements + 1 return our_node end function ; ------------------------------------------------------------------------------ function list_remove_node(our_node.listC_node) ; remove an arbitrary element from a linked list, returning its value ; return 0 if we're trying to return an element that doesn't exist (e.g. empty_list\last_node) if (our_node = null) then return 0 ; if there's a node before this one, it gets our next_node as its new next_node (or null if this is the last node) if (our_node\prev_node <> null) then our_node\prev_node\next_node = our_node\next_node endif ; if there's a node after this one, it gets our prev_node as its new prev_node (or null if this is the first node) if (our_node\next_node <> null) then our_node\next_node\prev_node = our_node\prev_node endif ; if this was the first node, the next node is now the first node (or null if the list is now empty) if (our_node = our_node\list\first_node) then our_node\list\first_node = our_node\next_node endif ; if this was the last node, the prev node is now the last node (or null if the list is now empty) if (our_node = our_node\list\last_node) then our_node\list\last_node = our_node\prev_node endif ; update the number of elements in the list our_node\list\elements = our_node\list\elements - 1 ; destroy the node, returning its value local value = our_node\value delete our_node return value end function ; ------------------------------------------------------------------------------ function list_count(our_list.listC) return our_list\elements end function ; ------------------------------------------------------------------------------ ;= ITERATORS ; ------------------------------------------------------------------------------ ; sample usage ; ; for item.type = each list ; it.listC_iter = list_iterator_begin(list) ; while list_iterator_next(it) ; item.type = object.type(list_iterator_get(it)) ; wend ; ------------------------------------------------------------------------------ function list_iterator_begin.listC_iter(our_list.listC) ; create a new iterator for traversing the list forwards it.listC_iter = new listC_iter if our_list <> null then it\list = our_list it\forwards = true it\current_node = null it\next_node = our_list\first_node endif return it end function ; ------------------------------------------------------------------------------ function list_iterator_begin_reverse.listC_iter(our_list.listC) ; create a new iterator for traversing the list backwards it.listC_iter = new listC_iter if our_list <> null then it\list = our_list it\forwards = false it\current_node = null it\next_node = our_list\last_node endif return it end function ; ------------------------------------------------------------------------------ function list_iterator_next(it.listC_iter) ; advance the iterator to the next item in the list ; drop out immediately if this iterator is void if it\list = null then return false ; if there's a next node, advance to it and return true if it\next_node <> null then it\current_node = it\next_node if it\forwards then it\next_node = it\current_node\next_node else it\next_node = it\current_node\prev_node endif return true ; otherwise, destroy the iterator and return false else delete it return false endif end function ; ------------------------------------------------------------------------------ function list_iterator_get(it.listC_iter) ; return the value of the element the iterator is currently on return it\current_node\value end function ; ------------------------------------------------------------------------------ ;= CONVENIENCE ; ------------------------------------------------------------------------------ function list_find_node_by_value.listC_node(our_list.listC, value) ; find the first node in a list matching the value given if our_list = null then runtimeerror("not a valid listC: null") this_node.listC_node = our_list\first_node while (this_node <> null) if this_node\value = value then return this_node ; advance this_node = this_node\next_node wend return null end function ; ------------------------------------------------------------------------------ function list_find_node_by_position.listC_node(our_list.listC, index) ; find the Nth node in a list if our_list = null then runtimeerror("not a valid listC: null") if index < 0 then index = our_list\elements - index ; make sure there are enough nodes if index < 0 or index > our_list\elements-1 then return null this_node.listC_node = our_list\first_node for i = 0+1 to index this_node = this_node\next_node next return this_node end function ; ------------------------------------------------------------------------------ ;= TESTING ; ------------------------------------------------------------------------------ type list_sample_type_1 field value$ end type type list_sample_type_2 field list_node.listC_node ; keep track of the node in sample_list which points to us field value$ end type function list_test() print "list_test()" ; --- print "example 1: the basics" ; create some objects a.list_sample_type_1 = new list_sample_type_1 : a\value$ = "bar" b.list_sample_type_1 = new list_sample_type_1 : b\value$ = "baaz" c.list_sample_type_1 = new list_sample_type_1 : c\value$ = "quux" ; create a list and add our objects sample_list_1.listC = new listC list_push(sample_list_1, handle(a)) list_push(sample_list_1, handle(b)) list_push(sample_list_1, handle(c)) ; display the objects in the list print "listing all elements..." it.listC_iter = list_iterator_begin(sample_list_1) while list_iterator_next(it) item_1.list_sample_type_1 = object.list_sample_type_1(list_iterator_get(it)) print " " + item_1\value$ wend ; destroy the objects ; for item_1.list_sample_type_1 = each sample_list_1 it.listC_iter = list_iterator_begin(sample_list_1) while list_iterator_next(it) item_1.list_sample_type_1 = object.list_sample_type_1(list_iterator_get(it)) delete item_1 wend ; destroy the list (and its nodes) list_destroy(sample_list_1) ; --- print "example 2: keeping track of nodes" ; create some objects x.list_sample_type_2 = new list_sample_type_2 : x\value$ = "fish" y.list_sample_type_2 = new list_sample_type_2 : y\value$ = "percolator" z.list_sample_type_2 = new list_sample_type_2 : z\value$ = "cheese" ; create a list and add our objects (keeping track of the list nodes) sample_list_2.listC = new listC x\list_node = list_push(sample_list_2, handle(x)) y\list_node = list_push(sample_list_2, handle(y)) z\list_node = list_insert_after(x\list_node, handle(z)) ; display the objects in the list print "listing all elements..." it.listC_iter = list_iterator_begin(sample_list_2) while list_iterator_next(it) item_2.list_sample_type_2 = object.list_sample_type_2(list_iterator_get(it)) print " " + item_2\value$ wend ; remove an object from the list list_remove_node(z\list_node) : z\list_node = null ; shift the remaining elements off the list, displaying their \value$s print "remaining elements..." while (sample_list_2\elements > 0) item_2.list_sample_type_2 = object.list_sample_type_2(list_shift(sample_list_2)) print " " + item_2\value$ wend ; destroy the list (and its nodes) list_destroy(sample_list_2) ; delete the objects delete x delete y delete z ; --- print "press any key to exit..." waitkey end end function |
Comments
None.
Code Archives Forum