Linked Lists 1.2

This code has been declared by its author to be Public Domain code.
Linked Lists 1.2 by Entity
2001
If you need to have multiple lists of items of the same type, you need custom linked lists, as Blitz' list commands only work on the entire collection of objects of a type.

I didn't implement all Amiga functions (like inserting at specific locations, and inserting by priority), but you could write those yourself if you need them :)
;
; Lists.bb -- Version 1.2 -- Amiga style linked lists
; by Jamie "Entity" van den Berge
;

Type List
	Field lh_Head.Node
	Field lh_Tail.Node
End Type

Type Node
	Field ln_Succ.Node
	Field ln_Pred.Node
	Field ln_List.List
	Field ln_ID
End Type


;______________________________________________________________________________
; Remove
;
; FUNCTION
;	Removes a node from the list it is in
;
; INPUTS
;	node	- node to unlink
;
Function Remove .Node ( node.Node )
	If node\ln_Pred <> Null
		node\ln_Pred\ln_Succ = node\ln_Succ
	Else
		If node = node\ln_List\lh_Head Then node\ln_List\lh_Head = node\ln_Succ
	EndIf
	If node\ln_Succ <> Null
		node\ln_Succ\ln_Pred = node\ln_Pred
	Else
		If node = node\ln_List\lh_Tail Then node\ln_List\lh_Tail = node\ln_Pred
	EndIf
	node\ln_Pred = Null
	node\ln_Succ = Null
	node\ln_List = Null
	Return node
End Function


;______________________________________________________________________________
; RemHead
;
; FUNCTION
;	Removes first node from a list
;
; INPUTS
;	list	- list to remove first node of
;
; RESULT
;	the node that was removed
;
Function RemHead .Node ( list.List )
	Local node.Node = list\lh_Head
	If node <> Null Then list\lh_Head = node\ln_Succ
	If list\lh_Tail = node Then list\lh_Tail = Null ; list is empty?
	node\ln_List = Null
	Return node
End Function


;______________________________________________________________________________
; RemTail
;
; FUNCTION
;	Removes last node from a list
;
; INPUTS
;	list	- list to remove the last node of
;
; RESULT
;	the node that was removed
;
Function RemTail .Node ( list.List )
	Local node.Node = list\lh_Tail
	If node <> Null Then list\lh_Tail = node\ln_Pred
	If list\lh_Head = node Then list\lh_Head = Null ; list is empty?
	node\ln_List = Null
	Return node
End Function


;______________________________________________________________________________
; FindNode
;
; FUNCTION
;	Searches for a node with a particular ID in given list
;
; INPUTS
;	list	- the list to search
;	id		- the id to look for
;
; RESUT
;	the first node that id, or Null.
;
Function FindNode .Node ( list.List, id )
	Local n.Node = list\lh_Head
	While n <> Null
		If n\ln_Id = id Then Return n
		n = n\ln_Succ
	Wend
	Return Null
End Function


;______________________________________________________________________________
; AddHead
;
; FUNCTION
;	Inserts a node before the first in given list
;
; INPUTS
;	list	- the list to put the node in
;	node	- the node to insert
;
Function AddHead( list.List, node.Node )
	node\ln_Succ = list\lh_Head ; current head becomes next node of node one
	If list\lh_Head <> Null Then list\lh_Head\ln_Pred = node ; current head gets node node as prev
	If list\lh_Tail =  Null Then list\lh_Tail = node         ; no tail? then head is tail
	node\ln_Pred = Null ; node is the new head so it cant have prev node
	list\lh_Head = node ; make node node the new head
	node\ln_List = list
End Function


;______________________________________________________________________________
; AddTail
;
; FUNCTION
;	Inserts a node after the last in given list
;
; INPUTS
;	list	- the list to put the node in
;	node	- the node to insert
;
Function AddTail( list.List, node.Node )
	node\ln_Pred = list\lh_Tail ; current tail becomes prev node if node one
	If list\lh_Tail <> Null Then list\lh_Tail\ln_Succ = node ; current tail gets node node as next
	If list\lh_Head =  Null Then list\lh_Head = node         ; no head? then tail is head
	node\ln_Succ = Null ; node is the new tail so it can't have next node
	list\lh_Tail = node ; make node node the new tail
	node\ln_List = list
End Function


; Next 4 are for clarity. It's more efficient to use the type fields directly
Function FirstNode .Node ( list.List ) Return list\lh_Head: End Function
Function LastNode  .Node ( list.List ) Return list\lh_Tail: End Function
Function NextNode  .Node ( node.Node ) Return node\ln_Succ: End Function
Function PrevNode  .Node ( node.Node ) Return node\ln_Pred: End Function


;##############################################################################
; EXAMPLE CODE
;
Graphics 640,480,0,2
SetFont LoadFont("FixedSys", 8)

Function White( a$ )
	Color 255,255,255: Write a
End Function

l.List = New List		; Create a new list

; Now add a few nodes
White "Adding nodes to top         : ": Color 0,255,0
For x = 1 To 10	
	n.Node = New Node	; create the node
	n\ln_ID = x+20		; give it an ID for the example
	Write n\ln_ID + " "
	AddHead( l, n )		; add node to top of list
Next
Print ""


White "How the list looks now      : "
Gosub dumplist

White "Removing 3 nodes from top   : ": Color 255,0,0
For t = 1 To 3
	n = RemHead( l )	; remove from list
	Write n\ln_ID + " "	; print its value (node still exists!)
	Delete n			; destroy node completely
Next
Print ""

White "Removing 2 nodes from bottom: ": Color 255,0,0
For t = 1 To 2
	n = RemTail( l )	; remove from list
	Write n\ln_ID + " "	; print the value (node still exists!)
	Delete n			; destroy node completely
Next
Print ""

; Show what it looks like now
White "Remaining list              : "
Gosub dumplist

; Move first node to the end
AddTail( l, RemHead( l ) )
White "Moved top node to bottom    : "
Gosub dumplist

; Remove a node by its ID
n.Node = FindNode( l, 24 )
If n <> Null Then Remove( n ): Delete n

White "Removed node with id 24     : "
Gosub dumplist

WaitKey
End


.dumplist:
	Color 255,255,0
	n = FirstNode( l )		; get first node in list
	While n <> Null			; while there's nodes
		Write n\ln_ID + " "	; print its value
		n = NextNode( n )	; move to next node
	Wend
	Print ""
Return
Comments

None.

Code Archives Forum