Linked Lists

[Magtheridon96]

Linked Lists

This is an easy tutorial that explains the art of using a linked list.

What is a linked list?

A linked list is a data structure.
The name explains it all.
It links nodes in a list.
What I like about linked lists is that allocation/deallocation is childs-play

Where could this be useful?

It's commonly used to link struct instances so you can loop through them easily

What do I require?

For a linked list, you only require 2 global integer arrays ^^

globals
    integer array next
    integer array prev
endglobals

In structs they would look like this:

struct MyStruct
    static integer array next
    static integer array prev
endstruct

Is that it? -_-

No..

You still need to know the algorithms...

A linked list is literally a list.
To add data to a linked list, we have to go to the end of that list, and put the data there

static method create takes nothing returns thistype
    local thistype this = thistype.allocate()
    
    // Add 'this' to the list
    set next[this] = 0
    set prev[this] = prev[0]
    set next[prev[this]] = this
    set prev[0] = this

    return this
endmethod

All these lines can be used to create pseudo code that makes a lot of sense

set next[this] = 0

In this type of linked list, the end is represented by a '0'
Here, we set the next node of this to 0.

set prev[this] = prev[0]

Here, we set the previous node of this to 'prev[0]' which we're using as a reference to the last added node since logically, the previous node of 0 is not needed and will never be used .. lol

set next[prev[this]] = this

This one is quite logical.
This is how you should read it:
We're setting the next one of the previous one to this one.
See how that works?

set prev[0] = this

We're using the 'null' pointer to store the current node because it would count as the last allocated node in the list next time we add a new node ^^


Well, now that you know how to add data to a linked list, I'll teach you how to remove data from a linked list.

method destroy takes nothing returns nothing
    set next[prev[this]] = next[this]
    set prev[next[this]] = prev[this]
    call .deallocate()
endmethod

Well, this can be confusing for some people, and that's why I drew this to help you
'picture' the deallocation algorithm at work.

See, we want to remove 'this' from the list, but how could we do that?
The algorithm is quite easy.

See, the next node of the previous node of this happens to be this,
and the previous node of the next node of this also happens to be this.

So, if we set the next node of the previous node of this to the next node of this
and if we set the previous node of the next node of this to the previous node of this,
'this' will be completely gone from the linked list

Pretty easy huh?
Yeah I know it's confusing, but you'll get used to it

Okay.. I have my linked list.. Now what am I supposed to do with it

Iteration.. DUH!

We use linked lists to loop through nodes.

Look at this linked list:

struct List
    static integer array next
    static integer array prev
    static method create takes nothing returns thistype
        local thistype this = thistype.allocate()

        set next[this] = 0
        set prev[this] = prev[0]
        set next[prev[this]] = this
        set prev[0] = this
        
        return this
    endmethod
    static method iterate takes nothing returns nothing
        local integer index = next[0]
        loop
            exitwhen index==0
            call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,I2S(index))
            set index = next[index]
        endloop
    endmethod
    method destroy takes nothing returns nothing
        set next[prev[this]] = next[this]
        set prev[next[this]] = prev[this]
        call .deallocate()
    endmethod
endstruct

Our iteration algorithm is very pseudo-friendly too ^^

General Iteration:
1- Get the first node
2- If the node is null we stop
3- Go to the next node.
4- Go to number 2

Iteration here:


1- Get the first node.
local integer index = next[0]
next[0] is the first node in this linked list


2- If the node is null we stop
exitwhen index == 0
In our linked list, 0 represents a null node


3- Go to the next node
set index = next[index] Pretty simple :P 4- Go to number 2 In the allocation method we set the next node of the last allocated node to 0 This will allow us to exit when the list ends :) [b][size="2"]Misc Tips[/size][/b] There are lots of cool things you could do with a linked list: [icode=jass]set next[0] = 0

This makes iteration impossible

set prev[0] = 0

This forces the list to begin overwriting itself during further allocation

set next[0] = 0
set prev[0] = 0

This resets the list ^^

Wrap-Up

As you can see, linked lists are easy to use, efficient, and very pseudo-friendly data structures
I recommend using them for anything that requires looping through struct instances ^^

Thank you for reading this tutorial.
Feel free to comment.

~Magtheridon96

 

[BBQ]

1. You are only covering doubly linked lists. You should also cover singly and circularly linked lists.
2. What you have here doesn't even cover the complete functionality of a doubly linked list. This is what a true, fully-functional doubly linked list looks like.
3. All you have is node insertion at the end of the list. You should elaborate on all "kinds" of insertion:
   • After another node.
   • Before another node.
   • At the beginning of the list.
   • At the end of the list.
4. This is rather easy, but you should also explain how to traverse the list in both ways (currently, you're only explaining how to traverse it from the beginning to the end).
5. The "null pointer" is also called a sentinel value here. You can implement a linked list without it just as easily - and even though the insertion / addition wouldn't be as fast, trust me, they'd make much more sense to a new, inexperienced user.
6. Instead of focusing solely on the advantages, focus on the disadvantages as well. For example, linked lists do not allow random access to data, only sequential access. Compare linked lists to other data structures (at least to those than can be sanely implemented in vJass).

 

[PurgeandFire]

Yes, I completely agree that you should cover other list types, especially so people know when to use a single over a double or if they are looking for a circular list.

Also, I believe this should cover some examples of usage, otherwise it is random information that people do not know how to apply.

Essentially, I agree with BBQ's points. While this covers a basic linked list, it would be much better if it covered a broader spectrum.

One thing about the setup of that linked list in particular is that it is restricted to one list if you use thistype(0) as the sentinel value. I think it would be nicer if you would cover both that list and a struct that uses head nodes. (aka multiple lists per struct)

One last thing, I don't know if it is just me, but imo this:

set this.prev.next=this.next
set this.next.prev=this.prev

Is less complicated than:

set next[prev[this]] = next[this]
set prev[next[this]] = prev[this]

Or at least easier in terms of readability, at least for newer users. Although, that is just my opinion, not something you necessarily need to change. Also, you can always make the integers of type thistype instead to simplify the look. eg: next[0].member or thistype(0).next.member looks better (in my opinion) than thistype(next[0]).member.

 

[Magtheridon96]

Well, I'll improve the tutorial

set this.prev.next = this.next
set this.next.prev = this.prev

I know it's less complicated, but to some, it may appear confusing (They get compiled the same way anyways)
I'll add that form anyways


I'll also mention these disadvantages:
- Could be slower than arrays at one point
- Can only access data through iteration

 

[Nestharus]

Could be slower than arrays at one point

It's always going to be slower than iterating over an array unless you just need the node ids. For example, storing units in an array would be a smarter bet than storing them into a stack if you only needed 1 instance.

 

[PurgeandFire]

Waiting on an update for the points I've mentioned. If you are willing to update this, I will approve it, but if you aren't then I can graveyard it.

 

[Nestharus]

Also, ur deallocation is bad ; P. You should cover that the recycler can be merged with the next or previous pointers for instant clearing and or instant destruction or an entire list ^^.

 

[Magtheridon96]

Actually, I have absolutely no time for this
I guess you can graveyard it :/

 

[PurgeandFire]

Okay, just PM me if you want it out.

~Graveyarded.