Fun with lists

General FreeBASIC programming questions.
badidea
Posts: 1365
Joined: May 24, 2007 22:10
Location: The Netherlands

Fun with lists

Postby badidea » May 06, 2019 22:02

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()
Last edited by badidea on May 07, 2019 21:03, edited 2 times in total.
badidea
Posts: 1365
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Fun with lists

Postby badidea » May 06, 2019 22:57

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
Posts: 8971
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Fun with lists

Postby fxm » May 07, 2019 5:26

badidea wrote: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
Posts: 1365
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Fun with lists

Postby badidea » May 07, 2019 20:54

First post updated. Simple list much simpler now.
(no trees yet)
fxm
Posts: 8971
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Fun with lists

Postby fxm » May 07, 2019 21:07

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

Return to “General”

Who is online

Users browsing this forum: No registered users and 3 guests