linked lists, +rep for help

[GFreak45]

ok i had a question, what is better for doubly linked lists?
using next/previous as a normal variable that is just allocated with the struct? or a static array variable?
IE:

struct example extends array
    integer next = 0
    integer previous
endstruct

or

struct example extends array
    variables
    static integer array next
    static integer array previous
endstruct

and how do you reference static array variables inside a struct? is it any different then referencing a method using a function? just structname.variablename?

and for linked lists the best allocation/deallocation method would be this:

struct example extends array
    integer next = 0
    integer previous
    static integer array recycleList
    static integer listSize
    static integer lastRecycled
    
    static method allocate takes nothing returns thistype
        local integer i = 0
        if (recycleList[0] = 0) then
            set listSize = listSize + 1
            return listSize
        else
            set i = recycleList[0]
            set example<i>.next = 0
            set example<i>.previous = example[0].previous
            set example[0].previous = i
            set example[example<i>.previous].next = i
            set recycleList[0] = recycleList[recycleList[0]]
            set recycleList<i> = 0
            if recycleList[0] == 0 then
                set lastRecycled = 0
            endif
            return i
        endif
    endmethod

    method deallocate takes integer i returns nothing
        set example[example<i>.previous].next = example<i>.next
        set example[example<i>.next].previous = example<i>.previous
        set example<i>.previous = 0
        set example<i>.next = 0
        set recycleList[lastRecycled] = i
        set recycleList<i> = 0
        set lastRecycled = i
    endmethod
endstruct</i></i></i></i></i></i></i></i></i></i></i>

 

[Laiev]

>>and how do you reference static array variables inside a struct?

[ljass]set thistype.variable[array] = value[/ljass]

or simple

[ljass]set variable[array] = value[/ljass]

 

[GFreak45]

ok i thought so, but in the past, assumptions have made an ass out of me

 

[Dirac]

You no longer have to worry on how to code linked lists
LinkedListModule

 

[GFreak45]

im not trying to reinvent the wheel but i would rather learn about something before i use it rather than blindly follow... not saying i wont use it, probably will, but id like to know how/why it does what it does before i use it, know what i mean?

 

[Dirac]

I know exactly what you mean, the fact is that linked lists are common across programming languages and there are many guides that explain how do they work, and not just on this forum.
It doesn't really matter which way you use to build one, but using a pointer (this.) is more common than array use ([this])

Imagine a list of numbers that go from one to ten:

1-2-3-4-5-6-7-8-9-10

Now imagine you have an array called next that stores the following data

next[1]=2
next[2]=3
next[3]=4... and so on

Another array called "prev" stores different kind of data

prev[1]=0
prev[2]=1
prev[3]=2... and so on

You can ask any of those arrays which is the following or previous number to any index, example
I want to know which numbers goes after and before "7"

next[7] would return 8
prev[7] would return 6

Not so hard, the things get messy when you want to add new values to the list, as you can see in the list above nothing goes after "10" so if you ask the array what values goes after it

next[10] would return 0

Because 0 is the default value to all arrays, same goes for the previous value to 1.

Lets say you want to add "11" to the list, and you want to place it after "10"

First you would tell the following number to "10" that it's new previous value is going to be "11"

next[10] is currently equal to 0
prev[next[10]]=11

Ok now you tell "11" that it's previous value is going to be 10

prev[11]=10

And that it's next value is now what was after "10"

next[10] is currently equal to 0
next[11]=next[10]

Finally you tell "10" that it's next value is "11"

next[10]=11

And there you go, you just added another value to your list

 

[GFreak45]

i think you missed my update, i have most of that in the allocation/deallocation methods

 

[Dirac]

Please write something that compiles before posting it, it makes no sense

EDIT: even if it compiled your deallocation method has some extra unnecessary lines and your allocation method is just plain wrong, you need to read what i wrote in the post above and take a look at the LinkedListModule i provided

 

[GFreak45]

at work... was freehand so no JNPG to check if it compiles
ill look into it more in a bit

EDIT:
i just realized i had a local variable with no initial value
mind re-checking if it compiles?

 

[GFreak45]

how about this one using aids:

struct Example extends array
    unit thisUnit
    static integer array next
    static integer array previous

    static method linkUnit takes unit u returns thistype
        local integer i = GetUnitUserData(u)
        if (next[previous<i>] != i) then
            set previous<i> = previous[0]
            set next[previous<i>] = i
            set next<i> = 0
            set previous[0] = i
            set Example<i>.thisUnit = u
        else
            call BJDebugMsg(&quot;Example ERROR: You have attempted to register a unit that has already been registered.&quot;)
        endif
        return i
    endmethod

    static method linkRemove takes integer i returns nothing
        if Example<i>.thisUnit != null then
            set Example<i>.thisUnit = null
            set next[previous<i>] = next<i>
            set previous[next<i>] = previous<i>
        else
            call BJDebugMsg(&quot;Example ERROR: You have attempted to remove a non-existant unit.&quot;)
        endif
    endmethod

    //! runtextmacro AIDS()
endmethod</i></i></i></i></i></i></i></i></i></i></i>

again, freehand

 

[PurgeandFire]

For linkUnit you need to add this at the end:
[ljass]set previous[0] = i[/ljass]

But otherwise it seems correct.

 

[GFreak45]

oh ya, nice catch ty

 

[Dirac]

Unit Indexer + Unit List already keeps a track of indexed units using a linked list.
Also, you're adding AIDS to that structs with no meanings to an end

 

[GFreak45]

i must have missed it, and i did go through all your posts and still dont see where you explain that that is wrong

 

[Ayanami]

Why use static arrays when you can use [ljass]thistype[/ljass]?

struct Example
    private thistype next
    private thistype prev
endstruct

I personally find arrays a lot more confusing to read compared to using [ljass]thistype[/ljass].

 

[GFreak45]

so thistype only references the struct that encapsules it? when it was explained to me no one ever said that, so i thought it was a "struct" variable type

 

[Ayanami]

so thistype only references the struct that encapsules it? when it was explained to me no one ever said that, so i thought it was a "struct" variable type

[ljass]thistype[/ljass] refers to the current struct. That keyword can only be used within a struct. Like:

struct Main
    private static method test takes nothing returns nothing
        local Main a
        local thistype b

        // the both above has the same data type, "Main"
    endmethod
endstruct

So for a linked list (using thistype(0) as the sentinel node):

struct LinkedList
	private thistype next
	private thistype prev

	private static method linkExample takes nothing returns nothing
		local thistype this = thistype.allocate()
		
		set this.next = thistype(0).next
		set this.prev = thistype(0)
		set thistype(0).next.prev = this
		set thistype.next = this
	endmethod
	
	private method delinkExample takes nothing returns nothing
		set this.next.prev = this.prev
		set this.prev.next = this.next
	endmethod
endstruct

Better readability than arrays, at least for me.

 

[GFreak45]

what does the .allocate method do when it is not defined in the struct?

and in your private method you dont define this
do you not have to?

 

[Dirac]

All structs have default allocation methods, unless you have it [ljass]extends array[/ljass], then it wont have any kind of default allocation method and you would have to write one on your own

 

[GFreak45]

so how about this for an allocation method:

struct Example extends array
    real someVariable

    static integer array allocationRecycler
    static integer allocationCount

    private method allocate takes nothing returns thistype
        local integer i = allocationRecycler[0]
        if (allocationRecycler[0] == 0) then
            set allocationCount = allocationCount + 1
            return allocationCount
        endif
        set allocationRecycler[0] = allocationRecycler<i>
        set allocationRecycler<i> = 0
        return i
    endmethod
endstruct</i></i>