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

0 Members and 1 Guest are viewing this topic.

Arnold

  • Hero Member
  • *****
  • Posts: 973
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: 973
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: 4409
    • 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: 973
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: 973
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: 4409
    • 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: 973
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: OxygenBasic
  1. 'Singly linked List, basic functions, no checks
  2.  
  3. $ filename "SinglyLinkedList.exe"
  4. 'uses rtl32
  5. 'uses rtl64
  6.  
  7. uses console
  8.  
  9. type record
  10. ===========
  11.     int num
  12.     bstring name    'not string
  13.    record *nextptr 'pointer to next record
  14. end type
  15.  
  16. class SinglyLinkedList
  17. ======================
  18. record startRecord
  19.  
  20. sub constructor()
  21. end sub
  22.  
  23. sub destructor()
  24.     record *List
  25.     @list = @startRecord.nextptr
  26.     while @List
  27.         frees list.name
  28.         sys p=@list
  29.         @List = @List.nextptr
  30.         freememory p         'free prior record
  31.    wend
  32. end sub
  33.  
  34. function newRecord() as record*
  35.     sys address = getmemory sizeof(record)
  36.     return address
  37. end function
  38.  
  39. sub createRecords(int n)
  40.     record *List
  41.     int num = 51
  42.     int i
  43.     '
  44.    @List=@StartRecord
  45.     for i = 1 to n
  46.         @List.nextptr = newRecord()
  47.         @List = @List.nextptr
  48.         List.num = num
  49.         List.name = "NewName_" + str(num)
  50.         printl "Created data for node " + i + " = " + List.num + " " + List.name  + ", nextptr = " + @List
  51.         num += 1
  52.     next i
  53. end sub
  54.  
  55. sub prependRecord()
  56.     static int num=100
  57.     record *prepend, *temp
  58.  
  59.     @prepend = newRecord()
  60.     num+=1
  61.     prepend.num = num
  62.     prepend.name = "PrependName_" + str(num)
  63.  
  64.     @temp = @startRecord.nextptr
  65.     @startRecord.nextptr = @prepend
  66.     @prepend.nextptr = @temp
  67.  
  68.     printl "Prepend data at beginning " + " = " + prepend.num + " " + prepend.name  + ", nextptr = " + @prepend.nextptr
  69. end sub
  70.  
  71. sub appendRecord()
  72.     static int num=400
  73.     record *append, *temp
  74.  
  75.     @append = newRecord()
  76.     num+=1
  77.     append.num = num
  78.     append.name = "AppendName_" + str(num)
  79.  
  80.     @temp = startRecord.nextptr
  81.     while @temp.nextptr
  82.         @temp = @temp.nextptr
  83.     wend
  84.     @temp.nextptr = @append
  85.  
  86.     printl "Append data at end" + " = " + append.num + " " + append.name  + ", nextptr = " + @append
  87. end sub
  88.  
  89. sub insertRecord(int pos)
  90.     static int num=1000
  91.     record *insert, *temp
  92.  
  93.     @insert = newRecord()
  94.     num+=1
  95.     insert.num = num
  96.     insert.name = "InsertName_" +str(num)
  97.  
  98.     @temp = startRecord.nextptr
  99.     if pos = 1 then
  100.         @startRecord.nextptr = @insert
  101.         @insert.nextptr = @temp
  102.     else
  103.         int i
  104.         'no check if valid pos
  105.        for i=2 to pos-1
  106.             @temp = @temp.nextptr
  107.         next i
  108.         @insert.nextptr = @temp.nextptr
  109.         @temp.nextptr = @insert
  110.     end if
  111.     printl "Insert data at position " + pos " = " + insert.num + " " + insert.name  + ", nextptr = " + @insert.nextptr
  112. end sub
  113.  
  114. sub deleteRecord(int pos)
  115.     record *delRecord, *previous
  116.  
  117.     @delRecord = startRecord.nextptr
  118.     @previous = startRecord.nextptr
  119.     int i
  120.     for i=2 to pos
  121.         'no check if valid pos
  122.        @previous = @delRecord
  123.         @delRecord = @delRecord.nextptr
  124.     next i
  125.     if @delRecord = @startRecord.nextptr then
  126.         @startRecord.nextptr = @delRecord.nextptr
  127.     else
  128.         @previous.nextptr = @delRecord.nextptr
  129.         @delRecord.nextptr = 0
  130.     end if
  131.  
  132.     printl "Delete data at position " + pos " = " + delRecord.num + " " + delRecord.name  + ", nextptr = " + @delRecord.nextptr
  133.     frees delRecord.name
  134.     freememory @delRecord
  135. end sub
  136.  
  137. sub reverseRecords()
  138.     record *previous, *current, *temp
  139.  
  140.     @current = startRecord.nextptr
  141.     while @current
  142.         @temp = @current
  143.         @current = @current.nextptr
  144.         @temp.nextptr = @previous
  145.         @previous = @temp
  146.     wend
  147.     @startRecord.nextptr = @previous
  148.     printl : printl "Reverse List"
  149. end sub
  150.  
  151. sub displayList()
  152.     record *List
  153.     @list = @startRecord.nextptr
  154.  
  155.     printl : printl "Display List"
  156.     int ix = 0
  157.     while @List
  158.         ix += 1
  159.         printl "Data Node " + ix + " = " + List.num + " " + List.name  + ", nextptr = " + @List
  160.         sys *tmp : @tmp = @List
  161.         @List = @List.nextptr
  162.         if @List = 0 then
  163.             printl "nextptr " + @tmp + ": Empty List, nextptr = " + @List
  164.             exit while
  165.         end if
  166.  
  167.     wend
  168. end sub
  169.  
  170. end class 'Singly LinkedList
  171. ============================
  172.  
  173. sub main()
  174.     new SinglyLinkedList li
  175.     int n = 5   'number of created Records
  176.  
  177.     print  "Create and manage Singly Linked List -- basic functions, no checks"
  178.     printl "------------------------------------------------------------------" + cr
  179.  
  180.     li.createRecords(n)
  181.     printl
  182.     li.displayList()
  183.     printl "Enter ... " : waitkey
  184.  
  185.     li.reverseRecords()
  186.     printl
  187.     li.displayList()
  188.     printl "Enter ... " : waitkey
  189.  
  190.     li.reverseRecords()
  191.     li.prependRecord()
  192.     li.prependRecord()
  193.     li.displayList()
  194.     printl "Enter ... " : waitkey
  195.     printl
  196.  
  197.     li.appendRecord()
  198.     li.appendRecord()
  199.     li.displayList()
  200.     printl "Enter ... " : waitkey
  201.     printl
  202.  
  203.     li.insertRecord(1)
  204.     li.insertRecord(4)
  205.     li.displayList()
  206.     printl "Enter ... " : waitkey
  207.     printl
  208.  
  209.     li.deleteRecord(1)
  210.     li.deleteRecord(5)
  211.     li.displayList()
  212.     printl "Enter ... " : waitkey
  213.  
  214.     li.reverseRecords()
  215.     printl
  216.     li.displayList()
  217.  
  218.     printl
  219.     printl "Enter to end ..."
  220.     del li
  221.     waitkey
  222. end sub
  223.  
  224. main()
  225.  


Aurel

  • Guest
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

Charles Pegge

  • Admin Support Member
  • *****
  • Posts: 4409
    • 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: 3779
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: 973
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: 973
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: OxygenBasic
  1. ' https://www.sanfoundry.com/c-program-doubly-linked-list/
  2. /*
  3.  *  Program to Implement a Doubly Linked List & provide Insertion,
  4.  *  Deletion & Display Operations
  5.  */
  6.  
  7. $ filename "Dbl_LinkedList.exe"
  8. 'uses rtl32
  9. 'uses rtl64
  10.  
  11. uses corewin
  12. uses console
  13.  
  14. indexbase 0
  15.  
  16. type CONSOLE_CURSOR_INFO ' cci  
  17.  dword dwSize
  18.   bool  bVisible
  19. end type
  20.  
  21. sub setcolor(int fg, bg)
  22.   SetConsoleTextAttribute (ConsOut, fg+bg*16)
  23. end sub
  24.  
  25. sub locate(int row,int col, optional int cursor_visible=0,int shape=12)
  26.   CONSOLE_CURSOR_INFO cci
  27.   SetPos(col-1,row-1)
  28.   cci.bVisible = cursor_visible
  29.   cci.dwSize   = shape
  30.   SetConsoleCursorInfo(ConsOut, cci)
  31. end sub
  32.  
  33. sub display(int col, row, string txt, optional int cursor_visible=0,int shape=12)
  34.   locate(row, col, cursor_visible, shape)
  35.   print txt
  36. end sub  
  37.  
  38. /*
  39. struct node
  40. {
  41.     struct node *prev;
  42.     int n;
  43.     struct node *next;
  44. }*h,*temp,*temp1,*temp2,*temp4;
  45. */
  46.  
  47. type node
  48.     node *prev
  49.     int n
  50.     node *after
  51. end type
  52. node *h, *temp, *temp1,*temp2,*temp4
  53.  
  54.  
  55. def -> .
  56.  
  57. macro getstructmemory(structure)
  58.     sys _temp_ = getmemory(sizeof(structure))
  59.     @structure = _temp_
  60. end macro
  61.  
  62.  
  63. declare sub insert1()
  64. declare sub insert2()
  65. declare sub insert3()
  66. declare sub traversebeg()
  67. declare sub traverseend(int)
  68. declare sub sort()
  69. declare sub search()
  70. declare sub update()
  71. declare sub delete()
  72.  
  73. int count = 0
  74. string empty = "                                                               "
  75.  
  76. sub main()
  77.     int ch
  78.  
  79.     @h = NULL
  80.     @temp = @temp1 := NULL
  81.    
  82.     SetConsoleTitle "Doubly linked lists in Oxygenbasic"
  83.      
  84.     do
  85. start:    
  86.         setcolor(11, 0)      
  87.         display(1, 1, "  1 - Insert Integer at beginning")
  88.         display(1, 2, "  2 - Insert Integer at end")
  89.         display(1, 3, "  3 - Insert Integer at position Ix")
  90.         display(1, 4, "  4 - Delete at position Ix")
  91.         display(1, 5, "  5 - Display from beginning")
  92.         display(1, 6, "  6 - Display from end")
  93.         display(1, 7, "  7 - Search for a value element")
  94.         display(1, 8, "  8 - Sort the list")
  95.         display(1, 9, "  9 - Update a value element")
  96.         display(1,10, " 10 - Exit")
  97.  
  98.         display(16,12, "     ")
  99.         display(1,12, " Enter choice : ", 1)
  100.         ch = val(input())
  101.         setcolor(7,0)
  102.         display(1,14, empty)
  103.         display(1,15, empty)
  104.        
  105.  
  106.         select case ch
  107.         case 0
  108.             cls
  109.         case 1
  110.             insert1()
  111.         case 2
  112.             insert2()
  113.         case 3
  114.             insert3()
  115.         case 4
  116.             delete()  
  117.         case 5
  118.             traversebeg()
  119.         case 6
  120.             @temp2 = @h
  121.             if (@temp2 == NULL) then
  122.                 display 1, 14, " Error : List empty to display "
  123.             else
  124.                 display 1, 14, " Reverse order of linked list is : "
  125.                 traverseend(temp2->n)
  126.             end if
  127.         case 7
  128.             search()
  129.         case 8
  130.             sort()
  131.         case 9
  132.             update()
  133.         case 10
  134.             terminate
  135.             end
  136.         case else
  137.             display 1,14, " Wrong choice menu"
  138.         end select
  139.         goto start
  140.     end do
  141. end sub
  142.  
  143. /* TO create an empty node */
  144. sub create()
  145.     int data
  146.  
  147.     // temp =(struct node *)malloc(1*sizeof(struct node))
  148.     'sys _temp_ = getmemory(sizeof(node))
  149.    '@temp = _temp_
  150.    getstructmemory(temp)
  151.    
  152.     @temp->prev = NULL
  153.     @temp->after = NULL
  154.     display 1,15, " Enter value to node : ", 1
  155.     data = val(input())
  156.     temp->n = data
  157.     count++
  158. end sub
  159.  
  160. /*  TO insert at beginning */
  161. sub insert1()
  162.     if (@h == NULL) then
  163.         create()
  164.         @h = @temp
  165.         @temp1 = @h
  166.     else
  167.         create()
  168.         @temp->after = @h
  169.         @h->prev = @temp
  170.         @h = @temp
  171.     end if
  172. end sub
  173.  
  174. /* To insert at end */
  175. sub insert2()
  176.     if (@h == NULL) then
  177.         create()
  178.         @h = @temp
  179.         @temp1 = @h
  180.     else
  181.         create()
  182.         @temp1->after = @temp
  183.         @temp->prev = @temp1
  184.         @temp1 = @temp
  185.     end if
  186. end sub
  187.  
  188. /* To insert at any position */
  189. sub insert3()
  190.     int pos, i = 2
  191.  
  192.     display 1, 14, " Enter position to be inserted : ", 1
  193.     pos = val(input())
  194.     @temp2 = @h
  195.     display 1,15, empty
  196.  
  197.     if ((pos < 1) || (pos >= count + 1)) then
  198.         display 1, 15, " Position out of range to insert"
  199.         return
  200.     end if
  201.     if ((@h == NULL) && (pos != 1)) then
  202.         display 1, 15, " Empty list cannot insert other than 1st position"
  203.         return
  204.     end if
  205.     if ((@h == NULL) && (pos == 1)) then
  206.         create()
  207.         @h = @temp
  208.         @temp1 = @h
  209.         return
  210.     elseif pos = 1 then
  211.         create()
  212.         @temp->after = @h
  213.         @h->prev = @temp
  214.         @h = @temp        
  215.     else
  216.         while (i < pos)
  217.             @temp2 = @temp2->after            
  218.             i++
  219.         wend
  220.         create()
  221.         @temp->prev = @temp2
  222.         @temp->after = @temp2->after        
  223.         @temp2->after->prev = @temp      
  224.         @temp2->after = @temp
  225.     end if
  226. end sub
  227.  
  228. /* To delete an element */
  229. sub delete()
  230.     int i = 1, pos
  231.  
  232.     if (@h == NULL) then
  233.         display 1, 14, " Error : Empty list no elements to delete"
  234.         return
  235.     end if
  236.  
  237.     display 1, 14, " Enter position to be deleted : ", 1
  238.     pos = val(input())
  239.     @temp2 = @h
  240.  
  241.     if ((pos < 1) || (pos >= count + 1)) then
  242.         display 1, 14, " Error : Position out of range to delete"
  243.         return
  244.     end if
  245.    
  246.     while (i < pos)
  247.             @temp2 = @temp2->after
  248.             i++
  249.     wend
  250.     if (i == 1) then
  251.         if (@temp2->after == NULL) then
  252.            display 1,15, "Node deleted from list"
  253.            freememory(@temp2)      
  254.            @temp2 = @h := NULL
  255.            return
  256.         end if
  257.     end if
  258.     if (@temp2 == NULL) then
  259.         display 1, 14, " Error : Position out of range to delete"
  260.         return    
  261.     end if
  262.     if (@temp2->after == NULL) then
  263.         @temp2->prev->after = NULL
  264.         freememory(@temp2)
  265.         display 1,15, "Node deleted from list"
  266.         return
  267.     end if
  268.     @temp2->after->prev = @temp2->prev
  269.     if (i != 1) then
  270.         /* Might not need this statement if i == 1 check */
  271.         @temp2->prev->after = @temp2->after
  272.     end if    
  273.     if (i == 1) then
  274.         @h = @temp2->after
  275.     end if    
  276.     display 1, 15, " Node deleted"
  277.     freememory(@temp2)
  278.  
  279.     count--
  280. end sub
  281.  
  282. /* Traverse from beginning */
  283. sub traversebeg()
  284.     @temp2 = @h
  285.  
  286.     if (@temp2 == NULL) then
  287.         display 1,14, "List empty to display"
  288.         return
  289.     end if
  290.     display 1,14,  " Linked list elements from begining : "
  291.  
  292.     while (@temp2->after != NULL)
  293.         print temp2->n " "
  294.         @temp2 = @temp2->after
  295.     wend
  296.     print temp2->n
  297. end sub
  298.  
  299. /* To traverse from end recursively */
  300. sub traverseend(int i)
  301.     if (@temp2 != NULL) then
  302.         i = temp2->n
  303.         @temp2 = @temp2->after
  304.         traverseend(i)
  305.         print " " i
  306.     end if
  307. end sub
  308.  
  309. /* To search for an element in the list */
  310. sub search()
  311.     int data, count = 0
  312.     @temp2 = @h
  313.  
  314.     if (@temp2 == NULL) then
  315.         display 1, 14, " Error : List empty to search for data"
  316.         return
  317.     end if
  318.     display 1, 14, " Enter value to search : ", 1
  319.     data = val(input())
  320.     while (@temp2 != NULL)
  321.         if (temp2->n == data) then
  322.             display 1, 15, " Data found in position " (count+1)
  323.             return
  324.         else
  325.              @temp2 = @temp2->after
  326.              count++
  327.         end if    
  328.     wend
  329.     display 1, 15, " Error : " data " not found in list"
  330. end sub
  331.  
  332. /* To update a node value in the list */
  333. sub update()
  334.     int data, data1
  335.  
  336.     @temp2 = @h
  337.     if (@temp2 == NULL) then
  338.         display 1, 14, " Error : List empty no node to update"
  339.         return
  340.     end if
  341.  
  342.     display 1, 14, " Enter data of node to be updated : ", 1
  343.     data = val(input())
  344.     display 1, 15, " Enter new data : ", 1
  345.     data1 = val(input())
  346.    
  347.     while (@temp2 != NULL)
  348.         if (temp2->n == data) then
  349.             temp2->n = data1
  350.             traversebeg()
  351.             return
  352.         else
  353.             @temp2 = @temp2->after
  354.         end if    
  355.     wend
  356.     display 1, 15, " Error : " data " not found in list to update"
  357. end sub
  358.  
  359. /* To sort the linked list */
  360. sub sort()
  361.     int i, j, x
  362.  
  363.     @temp2 = @h
  364.     @temp4 = @h
  365.  
  366.     if (@temp2 == NULL) then
  367.         display 1, 14, " List empty to sort"
  368.         return
  369.     end if
  370.  
  371.     'for (temp2 = h; temp2 != NULL; temp2 = temp2->after)
  372.    @temp2 = @h
  373.     while (@temp2 != NULL)
  374.         'for (temp4 = temp2->after; temp4 != NULL; temp4 = temp4->after)
  375.        @temp4 = @temp2->after
  376.         while (@temp4 != NULL)
  377.             if (temp2->n > temp4->n) then
  378.                 x = temp2->n
  379.                 temp2->n = temp4->n
  380.                 temp4->n = x
  381.             end if
  382.             @temp4 = @temp4->after
  383.         wend
  384.         @temp2 = @temp2->after
  385.     wend
  386.     traversebeg()
  387. end sub
  388.  
  389. main()
  390.  
« Last Edit: December 28, 2019, 03:58:56 AM by Arnold »

Aurel

  • Guest
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!"

Arnold

  • Hero Member
  • *****
  • Posts: 973
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: 4409
    • 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;