Fun with lists

[badidea]

I decided to torture my brain a little with some pointer exercise.
Three types of unsorted dynamic lists:
* A "simple list", using a dynamic array with additional array to mark if an index is occupied. Memory never freed.
* A "singly linked list"
* A "doubly linked list"
For all tree, additional members functions could be added. But this is the basics I think.
Let me know if you spot an error. Tomorrow, I will try trees.

Code: Select all

'unsorted simple list / badidea / 2019-05-07

type data_type
	dim as integer x, y
	declare operator cast () as string
end type

operator data_type.cast () as string
  return str(x) & "," & str(y)
end operator

operator =(a as data_type, b as data_type) as boolean
	if a.x <> b.x then return false
	if a.y <> b.y then return false
	return true
end operator

'-------------------------------------------------------------------------------

'a simple dynamic list, grows and schrinks in size
type simple_list
	private:
	dim as data_type myData(any)
	public:
	declare function add(value as data_type) as integer
	declare function find(value as data_type) as integer
	declare function del(index as integer) as integer
	declare sub printAll()
end type

'add new data value, returns the index
function simple_list.add(value as data_type) as integer
	dim as integer ub = ubound(myData) + 1
	redim preserve myData(ub)
	myData(ub) = value
	return ub
end function

'find value in list, return the index
function simple_list.find(value as data_type) as integer
	for i as integer = 0 to ubound(myData)
		if myData(i) = value then return i
	next
	return -1 'not found
end function

'delete value by index
function simple_list.del(index as integer) as integer
	dim as integer ub = ubound(myData)
	if index < 0 or index > ub then return -1 'invalid index
	if ub = 0 then 'one item left
		erase myData
	else
		myData(index) = myData(ub) 'move last in its spot
		redim preserve myData(ub - 1)
	end if
	return 0 'ok, deleted
end function

'loop all and print
sub simple_list.printAll()
	for i as integer = 0 to ubound(myData)
		print i, myData(i)
	next
end sub

'-------------------------------------------------------------------------------

dim as simple_list list

print "=== add some values ==="
print list.add(type(10, 3))
print list.add(type(4, 12))
print list.add(type(5, 22))

print "=== find some values ==="
print list.find(type(5, 21)) 
print list.find(type(6, 22))
print list.find(type(5, 22))

print "=== print all values ==="
list.printAll()

print "=== find a value and delete ==="
print list.del( list.find( type(4, 12) ) )
print list.del( list.find( type(4, 12) ) ) 'try again

print "=== print all values ==="
list.printAll()

print "=== add another value ==="
print list.add(type(7, -4))

print "=== print all values ==="
list.printAll()

Code: Select all

'unsorted singly linked list / badidea / 2019-05-06

type data_type
	dim as integer x, y
	declare operator cast () as string
end type

operator data_type.cast () as string
  return str(x) & "," & str(y)
end operator

operator =(a as data_type, b as data_type) as boolean
	if a.x <> b.x then return false
	if a.y <> b.y then return false
	return true
end operator

'-------------------------------------------------------------------------------

type node_type
	dim as node_type ptr pNext
	dim as data_type myData
end type

'https://en.wikipedia.org/wiki/Linked_list
type singly_linked_list
	private:
	dim as node_type ptr pRoot
	public:
	declare function add(value as data_type) as node_type ptr
	declare function find(value as data_type) as node_type ptr
	declare function del(value as data_type) as integer
	declare sub printAll()
end type

'set root node or insert above, return address of head
function singly_linked_list.add(value as data_type) as node_type ptr
	dim as node_type ptr pNew = new node_type
	if pRoot = 0 then 'set root
		pRoot = pNew
	else
		pNew->pNext = pRoot
		pRoot = pNew
	end if
	pRoot->myData = value
	return pRoot
end function

'find value in list, return the node address
function singly_linked_list.find(value as data_type) as node_type ptr
	dim as node_type ptr pNode = pRoot
	while pNode
		if pNode->myData = value then return pNode
		pNode = pNode->pNext
	wend
	return 0
end function

'find and delete value
function singly_linked_list.del(value as data_type) as integer
	dim as node_type ptr pNode = pRoot, pPrev = 0
	while pNode
		if pNode->myData = value then
			if pPrev = 0 then 'delete head
				pRoot = pRoot->pNext
			else
				pPrev->pNext = pNode->pNext
			end if
			delete pNode
			return 0 'ok, deleted
		end if
		pPrev = pNode
		pNode = pNode->pNext
	wend
	return -1 'not found
end function

'loop all and print
sub singly_linked_list.printAll()
	dim as node_type ptr pNode = pRoot
	while pNode
		print pNode->myData
		pNode = pNode->pNext
	wend
end sub

'-------------------------------------------------------------------------------

dim as singly_linked_list list

print "=== add some values ==="
print list.add(type(10, 3))
print list.add(type(4, 12))
print list.add(type(5, 22))

print "=== find some values ==="
print list.find(type(5, 21)) 
print list.find(type(6, 22))
print list.find(type(5, 22))

print "=== print all values ==="
list.printAll()

print "=== find a value and delete ==="
print list.find(type(4, 12))
print list.del(type(4, 12))
print list.del(type(4, 12)) 'try again

print "=== print all values ==="
list.printAll()

print "=== add another value ==="
print list.add(type(7, -4))

print "=== print all values ==="
list.printAll()

Code: Select all

'unsorted doubly linked list / badidea / 2019-05-06

type data_type
	dim as integer x, y
	declare operator cast () as string
end type

operator data_type.cast () as string
  return str(x) & "," & str(y)
end operator

operator =(a as data_type, b as data_type) as boolean
	if a.x <> b.x then return false
	if a.y <> b.y then return false
	return true
end operator

'-------------------------------------------------------------------------------

type node_type
	dim as node_type ptr pNext, pPrev
	dim as data_type myData
end type

'https://en.wikipedia.org/wiki/Doubly_linked_list
type doubly_linked_list
	private:
	dim as node_type ptr pRoot
	public:
	declare function add(value as data_type) as node_type ptr
	declare function find(value as data_type) as node_type ptr
	declare function del(pNode as node_type ptr) as integer
	declare sub printAll()
end type

'set root node or insert above, return address of head
function doubly_linked_list.add(value as data_type) as node_type ptr
	dim as node_type ptr pNew = new node_type
	if pRoot = 0 then 'set root
		pRoot = pNew
	else
		pNew->pNext = pRoot
		pRoot->pPrev = pNew 'new has become head
		pRoot = pNew
	end if
	pRoot->myData = value
	return pRoot
end function

'find value in list, return the node address
function doubly_linked_list.find(value as data_type) as node_type ptr
	dim as node_type ptr pNode = pRoot
	while pNode
		if pNode->myData = value then return pNode
		pNode = pNode->pNext
	wend
	return 0
end function

'delete by address
function doubly_linked_list.del(pNode as node_type ptr) as integer
	if pNode = 0 then
		return -1 'invalid address
	elseif pNode = pRoot then 'head of list
		pRoot = pRoot->pNext
		pRoot->pPrev = 0 'nothing before head
	else
		pNode->pPrev->pNext = pNode->pNext
		if pNode->pNext <> 0 then 'last one?
			pNode->pNext->pPrev = pNode->pPrev
		end if
	end if
	delete pNode
	return 0 'ok, deleted
end function

'loop all and print
sub doubly_linked_list.printAll()
	dim as node_type ptr pNode = pRoot
	while pNode
		print pNode->myData
		pNode = pNode->pNext
	wend
end sub

'-------------------------------------------------------------------------------

dim as node_type ptr pNode
dim as doubly_linked_list list


print "=== add some values ==="
print list.add(type(10, 3))
print list.add(type(4, 12))
print list.add(type(5, 22))

print "=== find some values ==="
print list.find(type(5, 21)) 
print list.find(type(6, 22))
print list.find(type(5, 22))

print "=== print all values ==="
list.printAll()

print "=== find a value and delete ==="
pNode = list.find(type(4, 12))
print pNode
print list.del(pNode)
'print list.del(pNode) 'do NOT try again

print "=== print all values ==="
list.printAll()

print "=== add another value ==="
print list.add(type(7, -4))

print "=== print all values ==="
list.printAll()

[badidea]

I just read that there is a better way to do the 'simple list'. On deletion, move last item in its place. No need for inUse array.

[fxm]

I just read that there is a better way to do the 'simple list'. On deletion, move last item in its place. No need for inUse array.

Just a inUse Integer?

Otherwise (without any inUse) the myData() array must also be resized:
=> take into account the case where myData() must become empty:

• 'redim preserve myData(upperBound)' is invalid when upperBound = -1,
  to be replaced with 'erase myData' in this case.

[badidea]

First post updated. Simple list much simpler now.
(no trees yet)

[fxm]

In 'simple_list.del', copy the last element of array is not necessary if this is the one to delete:

Code: Select all

'delete value by index
function simple_list.del(index as integer) as integer
   dim as integer ub = ubound(myData)
   if index < 0 or index > ub then return -1 'invalid index
   if ub = 0 then 'one item left
      erase myData
   else
      if index < ub then
         myData(index) = myData(ub) 'move last in its spot
      end if
      redim preserve myData(ub - 1)
   end if
   return 0 'ok, deleted
end function