Linked Lists in Oxygenbasic

[Arnold]

There is another small bug in sub delete(): if I add two values with menu item 1 and try menu item 4 to delete the value of position 2 two times then the app will crash. So I added these lines (258 - 261):

    if (@temp2 == NULL) then
        display 1, 14, " Error : Position out of range to delete"
        return   
    end if

It is reassuring to know that even in other programming languages, not everything works 100% if it is not thoroughly tested (-->null pointer). I substituted the code of message #11.

[Aurel]

here is a so called my version/translation
i don't get it how CB can understand this crazy UDT
but oxygen complain here which is right that is not defined

Charles is there a way that o2 can process this:
error is in RED

WHILE list.node.nxt
   plist = plist.node.nxt
WEND

Code: [Select]

''example of using a double linked list
'translation from Creative Baic by Aurel 27.12.2019.
'A node consists of two pointers
'one for the previous element
'and one for the next
TYPE node
nxt  AS sys
prev AS sys
END TYPE

'our list has a node so we can
'create a linked list
TYPE list
node   AS node
data   AS string
number AS int
END TYPE

print "...UDT node & list created!"

Dim p,ref AS sys 'as pointer

'the function declarations.
! addtail (plist AS sys,data AS string,number AS int) As sys
! addhead (plist AS sys,data AS string,number AS int) As sys
! find    (plist AS sys,data AS string)
! deleteall(plist AS sys)

print "...function declared!"

'main ///////////////////////////////////////////////
p = addtail(p,"entry0",12)



'/////////////////////////////////////////////////////

sub addtail(plist AS sys,data AS string,number AS int) as sys
    'plist.node.nxt as list
if(plist = 0)
'if our list is empty just create
'a new one
plist = new(list)
else'
'find the last element
WHILE list.node.nxt
plist = plist.node.nxt
WEND
'create a new list variable
plist.node.nxt = new(list,1)
'point the new lists prev variable
'to the current last element
'this syntax uses multiple indirection
'both plist and nxt are pointers
plist.node.nxt.node.prev = plist
plist = plist.node.nxt
end if
plist.data = data
plist.number = number
return plist
end sub
'.................................................................
sub addhead(plist AS sys,data AS string,number AS int) as sys
if(plist = 0)
'if our list is empty just create a new one
plist = new(list,1)
else
'create a new list variable and put it first in line
plist.node.prev = new(list,1)
'make our new head point to the old head element
'this syntax uses multiple indirection
'both plist and prev are pointers
plist.node.prev.node.nxt = plist
plist = plist.node.prev
end if
plist.data = data
plist.number = number
return plist
end sub
'.................................................................
sub find(plist AS pointer,data AS string) as sys
Dim preturn AS sys
if(plist = 0)
preturn = 0
else
do
if plist.data = data
preturn = plist
else
plist = plist.node.nxt
endif
if preturn | (plist=0) then exit do
        end do
end if
return preturn
end sub
'..................................................................
sub deleteall(plist AS sys)
Dim temp AS sys
'iterate through the list
'until the end
'deleting elements as we go.
while plist.node.nxt
temp  = plist
plist = plist.node.nxt
delete temp
wend
delete plist
return
end sub


[Charles Pegge]

Hi Aurel,

Something like this:

Code: [Select]

list *vlist
@vlist=plist
WHILE vlist.node.nxt
   @vlist = vlist.node.nxt
WEND

...
return @vlist


[Aurel]

Hi Charles 

You know the best how o2 work.
I never even tried something similar.
I will guess CB can do that way because have POINTER type .
Ok i will try..
thanks

[Charles Pegge]

Also:

Code: [Select]

if(plist = 0)
'if our list is empty just create
'a new one
'plist = new(list)
               plist=getmemory sizeof list
...


[Aurel]

Charles
is this valid in oxygen:

addtail ( *plist AS sys,data AS string,number AS int) as sys

...and is syntax for new valid  ?

new(list)

[Aurel]

Oh i see you use memory ,i would like to avoid memory operation
just one small thing from CBasic help:

[quote]pointer = NEW(type,length)

Type can be any built in or user defined type. Length must be 1 or greater. If length is greater than one then an array is created. NEW supports creating single dimensioned arrays only.

[/quote]

what you think about that ?

[Charles Pegge]

With the o2 Basic syntax, params are passed BYREF as default.

Code: [Select]

functionaddtail ( byval plist AS sys, byval data AS string, byval number AS int) as sys

o2 uses new differently. Normally a constructor for the class is expected, but in o2 0.2.8 this is optional, and new can be used with types


new type variable
new list vlist

this expands to:
list *vlist : @vlist = getmemory sizeof list

[Aurel]

Ahh OK Charles , i never use new before in any of my o2 programs , but i use it in EBasic few years back.
I am not sure, but i think that must be more simple or elegant or easy way to create linked list in Oxygen.
Maybe like dynamic string array or something similar?

[Charles Pegge]

You can use a list array and link with array indexes instead of pointers.

Use member 0 to catch any null indexes. Unlike null pointers, it wont crash the system.

Using redim will allow you to expand the array, and there is only one internal memory allocation per array redim.

Code: [Select]

indexbase 0
redim list vlist(100)


[Aurel]

Yes  i agree that would be easier.
I will try something like that .
By the way i used linked list for variable storage in my old AurelBasic and i remember all troubles i have to get it
to work properly, in fact they are slow even are supported in EBasic and are dynamic but to get element of list
you need to iterate each time trough whole list..not very good..right?
 

[Aurel]

Interesting video with animation of linked list is here:
https://www.youtube.com/watch?v=iNUS9iZwrVA