Author Topic: Linked Lists in Oxygenbasic  (Read 1659 times)

0 Members and 1 Guest are viewing this topic.

Arnold

  • Hero Member
  • *****
  • Posts: 941
Linked Lists in Oxygenbasic
« on: July 20, 2019, 02:01:42 PM »
Hi Charles,

maybe you or Mike can give some advice with this topic. I have started to experiment a bit with linked lists and I found this message:

https://www.oxygenbasic.org/forum/index.php?topic=430.msg3169#msg3169

This example works ok, but I would like to apply an approach more similar to C / Pascal. This is my first attempt:

Code: [Select]
'LinkList_1.o2bas
'Singly linked List

uses console

type record
   int num
   string name
   record *nextptr 'pointer to next record
end type

record startRecord
record *List

int start=100

sub createRecords(int n)
    sys address
    int num = start, i
   
    address = getmemory(sizeof(record))
    @startRecord.nextptr = address

    @List = @startRecord.nextptr
    List.num = start
    List.name = "Name " + chr(num-32)
    printl "Input data for node 1 = " + List.num + " " + List.name
    address=getmemory(sizeof(record))
    @List.nextptr = address
           
    for i = 2 to n
        @List = @List.nextptr
        num += 1
        List.num = num
        List.name = "Name " + chr(num-32)
        printl "Input data for node " + i + " = " + List.num + " " + List.name
        address = getmemory(sizeof(record))
        @List.nextptr = address         
    next i               
end sub

sub displayList()
   @list = @startRecord.nextptr

   int ix = 0
   while @List.nextptr != null
       ix += 1     
       printl "Data Node " + ix + " = " + List.num + " " + List.name
       @List = @List.nextptr
   wend       
end sub


sub main()
   'int n = 9
   
   print  "Create and display Singly Linked List"
   printl "-------------------------------------" + cr

   createRecords(9)
   printl
   displayList()
   
   printl
   printl "Enter ..."
   waitkey
end sub

main()

The code was developed by trial and error, the app seems to work ok, but I am not sure if my logic is really correct. In particular I am not sure if I could omit startRecord, which is a placeholder for the first address of List. I would like to use List directly, but somehow this did not work. I am also surprised that displyList() will only show 9 records. I expected to see one more (empty) record.

Maybe there is a more straightforward solution when using the C-like approach for linked lists? It seems to me that I have not yet found the best way. But all beginning is difficult.

Roland
« Last Edit: July 21, 2019, 12:48:07 AM by Arnold »

Arnold

  • Hero Member
  • *****
  • Posts: 941
Re: Linked Lists in Oxygenbasic
« Reply #1 on: July 21, 2019, 02:07:56 AM »
In the meantime I noticed that I have to build the while loop a bit different in sub displayList() to see the empty record:

Code: [Select]
   while 1
       ix += 1     
       printl "Data Node " + ix + " = " + List.num + " " + List.name + ", nextptr = " + @List.nextptr
       @List = @List.nextptr
       if @List.nextptr = null then
          ix += 1
          printl "Data Node " + ix + " = " + List.num + " " + List.name + ", nextptr = " + @List.nextptr
          exit while
       end if   
   wend       

Of course every getmemory needs a freememory at some time. But at the moment  I did not pay attention to this issue.

Charles Pegge

  • Admin Support Member
  • *****
  • Posts: 4276
    • Oxygen Basic
Re: Linked Lists in Oxygenbasic
« Reply #2 on: July 21, 2019, 05:52:07 AM »
Hi Roland,

Here is an adaptation of your code using a LinkedList class. The start record is only used as a base.

A destructor is also included.

Note that your list.name problems were caused by the garbage collector, thinking that List was a local UDT, so I've used bstring instead of string

Code: [Select]
'LinkList_1.o2bas
'Singly linked List

uses console

type record
===========
  int num
  bstring name 'not string
  record *nextptr 'pointer to next record
end type

class LinkedList
================

  record startRecord
  int start

  sub constructor(int n)
  start=n
  end sub

  sub destructor()
    record *List
    @list = @startRecord.nextptr
    while @List
      frees list.name
      sys p=@list
      @List = @List.nextptr
      freememory p 'free prior record
    wend       
  end sub

  function newRecord() as record*
    return getmemory sizeof(record)
  end function

  sub createRecords(int n)
    record *List
    int num = start
    int i
    '
    @List=@StartRecord       
    for i = 1 to n
      @List.nextptr = newRecord()
      @List = @List.nextptr
      List.num = num
      List.name = "Name " + chr(num-32)
      printl "Input data for node " + i + " = " + List.num + " " + List.name
      num += 1
    next i               
  end sub

  sub displayList()
    record *List
    @list = @startRecord.nextptr
    int ix = 0
    while @List
      ix += 1     
      printl "Data Node " + ix + " = " + List.num + " " + List.name
      @List = @List.nextptr
    wend       
  end sub

end class 'LinkedList


sub main()
   new linkedList li(100)
   int n = 3
   
   print  "Create and display Singly Linked List"
   printl "-------------------------------------" + cr

   li.createRecords(9)
   printl
   li.displayList()
   
   printl
   printl "Enter ..."
   del li
   waitkey
end sub

main()

Arnold

  • Hero Member
  • *****
  • Posts: 941
Re: Linked Lists in Oxygenbasic
« Reply #3 on: July 21, 2019, 07:14:57 AM »
Hi Charles,

thank you for the help. This is really helpful. Your solution is (as always) much clearer and more precise than my approach. I will use this code as a template for my next experiments (add, insert, delete, modify etc. nodes; double linked lists, circular linked lists).

Roland

Arnold

  • Hero Member
  • *****
  • Posts: 941
Re: Linked Lists in Oxygenbasic
« Reply #4 on: July 22, 2019, 09:41:46 AM »
Hi Charles,

I modified the code slightly to check if allocating memory will work, and modified in displayList() the while loop to see the empty node. Does it matter if I use in sub main simply this statement:

new linkedList li(1)

I tried n with the value 100000, and there seems to be no memory problems with Oxygenbasic. But I am not sure.

Roland 

Code: [Select]
'LinkList_1.o2bas
'Singly linked List

uses console

type record
===========
  int num
  bstring name 'not string
  record *nextptr 'pointer to next record
end type

class LinkedList
================

  record startRecord
  int start

  sub constructor(int n)
  start=n
  end sub

  sub destructor()
    record *List
    @list = @startRecord.nextptr
    while @List
      frees list.name
      sys p=@list
      @List = @List.nextptr
      freememory p 'free prior record
    wend       
  end sub

  function newRecord() as record*
    sys address = getmemory sizeof(record)
    if address = 0 then printl "Cannot allocate memory for record"
    return address
  end function

  sub createRecords(int n)
    record *List
    int num = 100
    int i
    '
    @List=@StartRecord
    for i = 1 to n
      @List.nextptr = newRecord()
      @List = @List.nextptr
      List.num = num
      List.name = "Name" + str(num)
      printl "Input data for node " + i + " = " + List.num + " " + List.name  + ", nextptr = " + @List
      num += 1
    next i               
  end sub

  sub displayList()
    record *List
    @list = @startRecord.nextptr
    int ix = 0
    while @List
      ix += 1     
      printl "Data Node " + ix + " = " + List.num + " " + List.name  + ", nextptr = " + @List
      sys *tmp : @tmp = @List
      @List = @List.nextptr
      if @List = 0 then
         printl
         printl "nextptr " + @tmp + ": Empty List, nextptr = " + @List
         exit while
      end if   
    wend       
  end sub

end class 'LinkedList


sub main()
   new linkedList li(1)
   int n = 5
   
   print  "Create and display Singly Linked List"
   printl "-------------------------------------" + cr

   li.createRecords(n)
   printl
   li.displayList()
   
   printl
   printl "Enter ..."
   del li
   waitkey
end sub

main()

Output:
Create and display Singly Linked List
-------------------------------------

Input data for node 1 = 100 Name100, nextptr = 40773716
Input data for node 2 = 101 Name101, nextptr = 40773916
Input data for node 3 = 102 Name102, nextptr = 40773756
Input data for node 4 = 103 Name103, nextptr = 40773876
Input data for node 5 = 104 Name104, nextptr = 40772876

Data Node 1 = 100 Name100, nextptr = 40773716
Data Node 2 = 101 Name101, nextptr = 40773916
Data Node 3 = 102 Name102, nextptr = 40773756
Data Node 4 = 103 Name103, nextptr = 40773876
Data Node 5 = 104 Name104, nextptr = 40772876

nextptr 40772876: Empty List, nextptr = 0

Enter ...

Charles Pegge

  • Admin Support Member
  • *****
  • Posts: 4276
    • Oxygen Basic
Re: Linked Lists in Oxygenbasic
« Reply #5 on: July 23, 2019, 06:29:35 AM »
Hi Roland,

The memory problems were entirely due to the garbage collector, which only deals with strings and wstrings. Bstrings and Wbstrings have no volatility, but must be freed explicitly, usually with the destructor.

Have you tried backward linkage yet :).

It is more useful in storage/retrieval situations.

Arnold

  • Hero Member
  • *****
  • Posts: 941
Re: Linked Lists in Oxygenbasic
« Reply #6 on: August 19, 2019, 03:05:23 AM »
Hi Charles,

this is what I have achieved so far with singly linked lists, and perhaps you would like to check the result for logical errors or improvement before I start experimenting with double linked lists.

My main focus was testing the pointers of the records. I added some basic functions for managing the list, but there is no serious examination for entry errors. Nevertheless with some adjustments and some additions a small database could be created. I suppose I would use double linked lists for this purpose.

Roland

Code: (o2) [Select]
'Singly linked List, basic functions, no checks

$ filename "SinglyLinkedList.exe"
'uses rtl32
'uses rtl64

uses console

type record
===========
    int num
    bstring name    'not string
    record *nextptr 'pointer to next record
end type

class SinglyLinkedList
======================
record startRecord

sub constructor()
end sub

sub destructor()
    record *List
    @list = @startRecord.nextptr
    while @List
        frees list.name
        sys p=@list
        @List = @List.nextptr
        freememory p         'free prior record
    wend
end sub

function newRecord() as record*
    sys address = getmemory sizeof(record)
    return address
end function

sub createRecords(int n)
    record *List
    int num = 51
    int i
    '
    @List=@StartRecord
    for i = 1 to n
        @List.nextptr = newRecord()
        @List = @List.nextptr
        List.num = num
        List.name = "NewName_" + str(num)
        printl "Created data for node " + i + " = " + List.num + " " + List.name  + ", nextptr = " + @List
        num += 1
    next i
end sub

sub prependRecord()
    static int num=100
    record *prepend, *temp

    @prepend = newRecord()
    num+=1
    prepend.num = num
    prepend.name = "PrependName_" + str(num)

    @temp = @startRecord.nextptr
    @startRecord.nextptr = @prepend
    @prepend.nextptr = @temp

    printl "Prepend data at beginning " + " = " + prepend.num + " " + prepend.name  + ", nextptr = " + @prepend.nextptr
end sub

sub appendRecord()
    static int num=400
    record *append, *temp

    @append = newRecord()
    num+=1
    append.num = num
    append.name = "AppendName_" + str(num)

    @temp = startRecord.nextptr
    while @temp.nextptr
        @temp = @temp.nextptr
    wend
    @temp.nextptr = @append

    printl "Append data at end" + " = " + append.num + " " + append.name  + ", nextptr = " + @append
end sub

sub insertRecord(int pos)
    static int num=1000
    record *insert, *temp

    @insert = newRecord()
    num+=1
    insert.num = num
    insert.name = "InsertName_" +str(num)

    @temp = startRecord.nextptr
    if pos = 1 then
        @startRecord.nextptr = @insert
        @insert.nextptr = @temp
    else
        int i
        'no check if valid pos
        for i=2 to pos-1
            @temp = @temp.nextptr
        next i
        @insert.nextptr = @temp.nextptr
        @temp.nextptr = @insert
    end if
    printl "Insert data at position " + pos " = " + insert.num + " " + insert.name  + ", nextptr = " + @insert.nextptr
end sub

sub deleteRecord(int pos)
    record *delRecord, *previous

    @delRecord = startRecord.nextptr
    @previous = startRecord.nextptr
    int i
    for i=2 to pos
        'no check if valid pos
        @previous = @delRecord
        @delRecord = @delRecord.nextptr
    next i
    if @delRecord = @startRecord.nextptr then
        @startRecord.nextptr = @delRecord.nextptr
    else
        @previous.nextptr = @delRecord.nextptr
        @delRecord.nextptr = 0
    end if

    printl "Delete data at position " + pos " = " + delRecord.num + " " + delRecord.name  + ", nextptr = " + @delRecord.nextptr
    frees delRecord.name
    freememory @delRecord
end sub

sub reverseRecords()
    record *previous, *current, *temp

    @current = startRecord.nextptr
    while @current
        @temp = @current
        @current = @current.nextptr
        @temp.nextptr = @previous
        @previous = @temp
    wend
    @startRecord.nextptr = @previous
    printl : printl "Reverse List"
end sub

sub displayList()
    record *List
    @list = @startRecord.nextptr

    printl : printl "Display List"
    int ix = 0
    while @List
        ix += 1
        printl "Data Node " + ix + " = " + List.num + " " + List.name  + ", nextptr = " + @List
        sys *tmp : @tmp = @List
        @List = @List.nextptr
        if @List = 0 then
            printl "nextptr " + @tmp + ": Empty List, nextptr = " + @List
            exit while
        end if

    wend
end sub

end class 'Singly LinkedList
============================

sub main()
    new SinglyLinkedList li
    int n = 5   'number of created Records

    print  "Create and manage Singly Linked List -- basic functions, no checks"
    printl "------------------------------------------------------------------" + cr

    li.createRecords(n)
    printl
    li.displayList()
    printl "Enter ... " : waitkey

    li.reverseRecords()
    printl
    li.displayList()
    printl "Enter ... " : waitkey

    li.reverseRecords()
    li.prependRecord()
    li.prependRecord()
    li.displayList()
    printl "Enter ... " : waitkey
    printl

    li.appendRecord()
    li.appendRecord()
    li.displayList()
    printl "Enter ... " : waitkey
    printl

    li.insertRecord(1)
    li.insertRecord(4)
    li.displayList()
    printl "Enter ... " : waitkey
    printl

    li.deleteRecord(1)
    li.deleteRecord(5)
    li.displayList()
    printl "Enter ... " : waitkey

    li.reverseRecords()
    printl
    li.displayList()

    printl
    printl "Enter to end ..."
    del li
    waitkey
end sub

main()


Aurel

  • Sr. Member
  • ****
  • Posts: 443
Re: Linked Lists in Oxygenbasic
« Reply #7 on: August 19, 2019, 11:21:55 AM »
Data base
what is that ?
It is something like Excell
so what we need is  arrays is 2D space , right?
2 data x.y = content
my site:BLOG and FORUM
https://aurelsoft.ucoz.com/

Charles Pegge

  • Admin Support Member
  • *****
  • Posts: 4276
    • Oxygen Basic
Re: Linked Lists in Oxygenbasic
« Reply #8 on: August 22, 2019, 03:09:35 AM »
Thanks Roland,

I think linked-lists are rather restrictive for databases, so I would not invest too much time on them. The indexed-list is a more flexible model, since a single index will provide linkage in both directions, and you can have any number of indexes into the same data-records, with differents orders and filters.

Another issue is that our contemporary computer architecture handles contiguous memory blocks more efficiently than scattered pieces of memory.

John

  • Hero Member
  • *****
  • Posts: 3643
Re: Linked Lists in Oxygenbasic
« Reply #9 on: August 22, 2019, 03:29:13 AM »
ScriptBasic uses linked lists for its dynamic array structure. While flexible there is a performance price to pay. I highly recommend you get ODBC working in O2 and learn SQL

Arnold

  • Hero Member
  • *****
  • Posts: 941
Re: Linked Lists in Oxygenbasic
« Reply #10 on: August 22, 2019, 05:21:53 AM »
Hi Charles,

my goal with this learning exercise was to provide proof that linked lists are possible with O2 too, and thanks to your help they work quite nice. For a small project (certainly no database, but also interesting), I have to check if linked lists should be used or if a simple array of structs will be sufficient. The structures will contain addresses of functions, and I am still investigating how you did this with FuncPointers1(2).o2bas and the examples in folder ..\Lingage. These demos are very inspiring.

Roland

Arnold

  • Hero Member
  • *****
  • Posts: 941
Re: Linked Lists in Oxygenbasic
« Reply #11 on: December 26, 2019, 02:40:27 PM »
Hi Charles,

during the Christmas holidays and between visits to relatives, I might have had an idea - maybe it is just crap. Inspired by Mike's implementing pointers to structures in o2scm.o2bas I tried to do this more C-like. I ported this example of doubly linked lists to Oxygenbasic:

C Program to Implement a Doubly Linked List & provide Insertion, Deletion & Display Operations
https://www.sanfoundry.com/c-program-doubly-linked-list/

This is the idea to declare a pointer and allocate memory for a structure:
Code: [Select]
/*
struct node
{
    struct node *prev;
    int n;
    struct node *next;
}*h,*temp,*temp1,*temp2,*temp4;
*/
 
type node
    node *prev
    int n
    node *after
end type
node *h, *temp, *temp1,*temp2,*temp4


def -> .

macro getstructmemory(structure)
    sys _temp_ = getmemory(sizeof(structure))
    @structure = _temp_
end macro

...

I ported the demo to Oxygenbasic and I got the same results when running the test run of the website. Nevertheless I am not quite sure if I did everything correctly.

These lines look so unusual to me:

line 223:
        @temp2->after->prev = @temp
line 263:
        @temp2->prev->after = NULL
line 268:
    @temp2->after->prev = @temp2->prev
line 271:
        @temp2->prev->after = @temp2->after

If the demo worked correctly, there would be a way to emulate pointers to memory structures quite comfortably. What do you think?

Roland

Edit:
It seems there is a small error in sub insert3(). I found the wrong behavior in the original C program too. I tried to correct this (line 210 - 214).
Edit2:
There is another bug in sub delete(). Therefore I inserted line 258-261.

Code: (o2) [Select]
' https://www.sanfoundry.com/c-program-doubly-linked-list/
/*
 *  Program to Implement a Doubly Linked List & provide Insertion,
 *  Deletion & Display Operations
 */

$ filename "Dbl_LinkedList.exe"
'uses rtl32
'uses rtl64

uses corewin
uses console

indexbase 0

type CONSOLE_CURSOR_INFO ' cci 
  dword dwSize
  bool  bVisible
end type

sub setcolor(int fg, bg)
  SetConsoleTextAttribute (ConsOut, fg+bg*16)
end sub

sub locate(int row,int col, optional int cursor_visible=0,int shape=12)
  CONSOLE_CURSOR_INFO cci
  SetPos(col-1,row-1)
  cci.bVisible = cursor_visible
  cci.dwSize   = shape
  SetConsoleCursorInfo(ConsOut, cci)
end sub

sub display(int col, row, string txt, optional int cursor_visible=0,int shape=12)
  locate(row, col, cursor_visible, shape)
  print txt
end sub 

/*
struct node
{
    struct node *prev;
    int n;
    struct node *next;
}*h,*temp,*temp1,*temp2,*temp4;
*/
 
type node
    node *prev
    int n
    node *after
end type
node *h, *temp, *temp1,*temp2,*temp4


def -> .

macro getstructmemory(structure)
    sys _temp_ = getmemory(sizeof(structure))
    @structure = _temp_
end macro

 
declare sub insert1()
declare sub insert2()
declare sub insert3()
declare sub traversebeg()
declare sub traverseend(int)
declare sub sort()
declare sub search()
declare sub update()
declare sub delete()
 
int count = 0
string empty = "                                                               "
 
sub main()
    int ch
 
    @h = NULL
    @temp = @temp1 := NULL
   
    SetConsoleTitle "Doubly linked lists in Oxygenbasic"
     
    do
start:   
        setcolor(11, 0)       
        display(1, 1, "  1 - Insert Integer at beginning")
        display(1, 2, "  2 - Insert Integer at end")
        display(1, 3, "  3 - Insert Integer at position Ix")
        display(1, 4, "  4 - Delete at position Ix")
        display(1, 5, "  5 - Display from beginning")
        display(1, 6, "  6 - Display from end")
        display(1, 7, "  7 - Search for a value element")
        display(1, 8, "  8 - Sort the list")
        display(1, 9, "  9 - Update a value element")
        display(1,10, " 10 - Exit")

        display(16,12, "     ")
        display(1,12, " Enter choice : ", 1)
        ch = val(input())
        setcolor(7,0)
        display(1,14, empty)
        display(1,15, empty)
       

        select case ch
        case 0
            cls
        case 1
            insert1()
        case 2
            insert2()
        case 3
            insert3()
        case 4
            delete() 
        case 5
            traversebeg()
        case 6
            @temp2 = @h
            if (@temp2 == NULL) then
                display 1, 14, " Error : List empty to display "
            else
                display 1, 14, " Reverse order of linked list is : "
                traverseend(temp2->n)
            end if
        case 7
            search()
        case 8
            sort()
        case 9
            update()
        case 10
            terminate
            end
        case else
            display 1,14, " Wrong choice menu"
        end select
        goto start
    end do
end sub
 
/* TO create an empty node */
sub create()
    int data
 
    // temp =(struct node *)malloc(1*sizeof(struct node))
    'sys _temp_ = getmemory(sizeof(node))
    '@temp = _temp_
    getstructmemory(temp)
   
    @temp->prev = NULL
    @temp->after = NULL
    display 1,15, " Enter value to node : ", 1
    data = val(input())
    temp->n = data
    count++
end sub

/*  TO insert at beginning */
sub insert1()
    if (@h == NULL) then
        create()
        @h = @temp
        @temp1 = @h
    else
        create()
        @temp->after = @h
        @h->prev = @temp
        @h = @temp
    end if
end sub

/* To insert at end */
sub insert2()
    if (@h == NULL) then
        create()
        @h = @temp
        @temp1 = @h
    else
        create()
        @temp1->after = @temp
        @temp->prev = @temp1
        @temp1 = @temp
    end if
end sub
 
/* To insert at any position */
sub insert3()
    int pos, i = 2
 
    display 1, 14, " Enter position to be inserted : ", 1
    pos = val(input())
    @temp2 = @h
    display 1,15, empty
 
    if ((pos < 1) || (pos >= count + 1)) then
        display 1, 15, " Position out of range to insert"
        return
    end if
    if ((@h == NULL) && (pos != 1)) then
        display 1, 15, " Empty list cannot insert other than 1st position"
        return
    end if
    if ((@h == NULL) && (pos == 1)) then
        create()
        @h = @temp
        @temp1 = @h
        return
    elseif pos = 1 then
        create()
        @temp->after = @h
        @h->prev = @temp
        @h = @temp       
    else
        while (i < pos)
            @temp2 = @temp2->after           
            i++
        wend
        create()
        @temp->prev = @temp2
        @temp->after = @temp2->after       
        @temp2->after->prev = @temp       
        @temp2->after = @temp
    end if
end sub

/* To delete an element */
sub delete()
    int i = 1, pos

    if (@h == NULL) then
        display 1, 14, " Error : Empty list no elements to delete"
        return
    end if
 
    display 1, 14, " Enter position to be deleted : ", 1
    pos = val(input())
    @temp2 = @h
 
    if ((pos < 1) || (pos >= count + 1)) then
        display 1, 14, " Error : Position out of range to delete"
        return
    end if
   
    while (i < pos)
            @temp2 = @temp2->after
            i++
    wend
    if (i == 1) then
        if (@temp2->after == NULL) then
           display 1,15, "Node deleted from list"
           freememory(@temp2)       
           @temp2 = @h := NULL
           return
        end if
    end if
    if (@temp2 == NULL) then
        display 1, 14, " Error : Position out of range to delete"
        return   
    end if
    if (@temp2->after == NULL) then
        @temp2->prev->after = NULL
        freememory(@temp2)
        display 1,15, "Node deleted from list"
        return
    end if
    @temp2->after->prev = @temp2->prev
    if (i != 1) then
        /* Might not need this statement if i == 1 check */
        @temp2->prev->after = @temp2->after
    end if   
    if (i == 1) then
        @h = @temp2->after
    end if   
    display 1, 15, " Node deleted"
    freememory(@temp2)
 
    count--
end sub

/* Traverse from beginning */
sub traversebeg()
    @temp2 = @h
 
    if (@temp2 == NULL) then
        display 1,14, "List empty to display"
        return
    end if
    display 1,14,  " Linked list elements from begining : "
 
    while (@temp2->after != NULL)
        print temp2->n " "
        @temp2 = @temp2->after
    wend
    print temp2->n
end sub

/* To traverse from end recursively */
sub traverseend(int i)
    if (@temp2 != NULL) then
        i = temp2->n
        @temp2 = @temp2->after
        traverseend(i)
        print " " i
    end if
end sub
 
/* To search for an element in the list */
sub search()
    int data, count = 0
    @temp2 = @h
 
    if (@temp2 == NULL) then
        display 1, 14, " Error : List empty to search for data"
        return
    end if
    display 1, 14, " Enter value to search : ", 1
    data = val(input())
    while (@temp2 != NULL)
        if (temp2->n == data) then
            display 1, 15, " Data found in position " (count+1)
            return
        else
             @temp2 = @temp2->after
             count++
        end if     
    wend
    display 1, 15, " Error : " data " not found in list"
end sub
 
/* To update a node value in the list */
sub update()
    int data, data1

    @temp2 = @h
    if (@temp2 == NULL) then
        display 1, 14, " Error : List empty no node to update"
        return
    end if
 
    display 1, 14, " Enter data of node to be updated : ", 1
    data = val(input())
    display 1, 15, " Enter new data : ", 1
    data1 = val(input())
   
    while (@temp2 != NULL)
        if (temp2->n == data) then
            temp2->n = data1
            traversebeg()
            return
        else
            @temp2 = @temp2->after
        end if   
    wend
    display 1, 15, " Error : " data " not found in list to update"
end sub
 
/* To sort the linked list */
sub sort()
    int i, j, x
 
    @temp2 = @h
    @temp4 = @h
 
    if (@temp2 == NULL) then
        display 1, 14, " List empty to sort"
        return
    end if
 
    'for (temp2 = h; temp2 != NULL; temp2 = temp2->after)
    @temp2 = @h
    while (@temp2 != NULL)
        'for (temp4 = temp2->after; temp4 != NULL; temp4 = temp4->after)
        @temp4 = @temp2->after
        while (@temp4 != NULL)
            if (temp2->n > temp4->n) then
                x = temp2->n
                temp2->n = temp4->n
                temp4->n = x
            end if
            @temp4 = @temp4->after
        wend
        @temp2 = @temp2->after
    wend
    traversebeg()
end sub
 
main()
« Last Edit: December 28, 2019, 03:58:56 AM by Arnold »

Aurel

  • Sr. Member
  • ****
  • Posts: 443
Re: Linked Lists in Oxygenbasic
« Reply #12 on: December 27, 2019, 12:57:39 PM »
I will try translate one old program from Creative Basic...
i hope that will work

Quote
''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)
! addhead (plist AS sys,data AS string,number AS int)
! find    (plist AS sys,data AS string)
! deleteall(plist AS sys)

print "...function declared!"
my site:BLOG and FORUM
https://aurelsoft.ucoz.com/

Arnold

  • Hero Member
  • *****
  • Posts: 941
Re: Linked Lists in Oxygenbasic
« Reply #13 on: December 28, 2019, 02:29:21 AM »
Sometimes it is bewitched. There is a small bug in the app which shows up after using choice 1 (enter an integer) the first time and then enter choice 3 (insert value) - which will crash the program. My first attempt to correct this was also not correct. I now tried (line 210-214):

    elseif pos = 1 then
        create()
        @temp->after = @h
        @h->prev = @temp
        @h = @temp

and this seems to work. This gives me some hope that the pointer calculations are not completely wrong, but I am not really qualified to verify this.


Charles Pegge

  • Admin Support Member
  • *****
  • Posts: 4276
    • Oxygen Basic
Re: Linked Lists in Oxygenbasic
« Reply #14 on: December 28, 2019, 03:24:03 AM »
Hi Roland, Thanks.

I am a bit wary of multiple pointers in case there is a null pointer lurking in the expression.


In the next release, I will make it possible to instantiate variables directly at the end of a struct:
Code: [Select]
struct node {
    struct node *prev;
    int n;
    struct node *next;
} *h,*temp,*temp1,*temp2,*temp4;