Android Tutorial Creating a linked list using Type keyword

The Type keyword is used to create your own types or structures. You can use such types to create simple structures that group some values.
However you can also use it to create more complex collections.
In this tutorial we will create a linked list.
A simpler usage of Type is demonstrated in the currency converter tutorial.

A linked list is a collection of elements. Each element has a value field and a 'next element' object. The 'next element' is actually a reference to the next element in the list.

The type is declared like this:
B4X:
Sub Process_Globals
    Type Element (NextElement As Element, Val As Int)
    Dim Head As Element 'declare a variable of that type.
    Dim Last As Element
End Sub
The interesting thing about this declaration is that we are using the current type as a field. The ability to declare such recursive types is very powerful.
Before we can access any of the type fields, it should be initialized by calling its Initialize method. Note that if the fields were initialized automatically then it would not have been possible to create such recursive types.
Note that if your type only includes numeric fields and strings then there is no need to call Initialize (though nothing bad will happen if you do call it).

Once we declared a type we can use it like any other "regular" types. It can be passed to subs, you can create an array of it and so on.

Lets build our list:
B4X:
Sub InitializeList (Value As Int)
    Head.Initialize
    Head.Val = Value
    Last = Head 'The last item is currently the head.
End Sub
The InitializeList sub initializes the head element, sets its value and sets the Last variable to reference the head element (as this is the only item in the list).

Adding an item:
B4X:
Sub AddElement(Value As Int)
    'create a new element
    Dim e As Element
    e.Initialize
    e.Val = Value
    Last.NextElement = e 'set the NextElement of the current last element to the new one.
    Last = e 'set the last variable to point to the new element.
End Sub
We are creating a new element. The current last element NextElement field is set to the new element and eventually the last variable is updated to the new element.

Going over all the items in the list is done by starting with the head element and then going forward by calling NextElement. When we reach an uninitialized element we stop.
B4X:
Sub ListToString As String
    Dim e As Element
    Dim sb As StringBuilder
    sb.Initialize
    e = Head
    Do While e.IsInitialized = True
        sb.Append(e.Val).Append(CRLF)
        e = e.NextElement
    Loop
    Return sb.ToString
End Sub
The complete code:
B4X:
Sub Process_Globals
    Type Element (NextElement As Element, Val As Int)
    Dim Head As Element
    Dim Last As Element
End Sub

Sub Globals

End Sub
Sub InitializeList (Value As Int)
    Head.Initialize
    Head.Val = Value
    Last = Head 'The last item is currently the head.
End Sub
Sub AddElement(Value As Int)
    'create a new element
    Dim e As Element
    e.Initialize
    e.Val = Value
    Last.NextElement = e 'set the NextElement of the current last element to the new one.
    Last = e 'set the last variable to point to the new element.
End Sub

Sub ListToString As String
    Dim e As Element
    Dim sb As StringBuilder
    sb.Initialize
    e = Head
    Do While e.IsInitialized = True
        sb.Append(e.Val).Append(CRLF)
        e = e.NextElement
    Loop
    Return sb.ToString
End Sub

 Sub Activity_Create(FirstTime As Boolean)
    InitializeList(10)
    AddElement(9)
    AddElement(8)
    AddElement(7)
    AddElement(6)
    AddElement(5)
    Msgbox(ListToString, "List values")
End Sub
 

Attachments

  • LinkedList.zip
    4.9 KB · Views: 1,004

Widget

Well-Known Member
Licensed User
Longtime User
I went through this tutorial and a few questions popped up.

1) How do I clear the list if I want to add new elements to the list?
2) If I want to delete an element from the list I assume I manage the NextElement myself, but how do I free the element? Use element.initialize?
3) Finally is there any advantage in using this element structure instead of LinkedList? Do most people use LinkedList?

TIA
Widget
 
Top