Linked Lists?

31 posts

Flag Post

Apparently linked lists, as opposed to arrays, have nodes that link to other nodes through pointers, thus disabling random-access memory but improving performance dramatically when applied in the right situations. But how do the pointers – the things that links the nodes to each other- work?

 
Flag Post

In AS3 and Haxe pointers are just variables that “contain” objects (in other words non primitive types). If you were to create a Node class, an instance of Node would be an object. Each Node has a property next, that “contains” another node. Node can then have a property called data, in which one could store information like numbers or reference to game objects.

 
Flag Post

Maybe something like this: (singly linked list example)

EDIT Ban qwerber.

 
Flag Post

EDIT Ban qwerber.

D:

 
Flag Post

A node in a linked list consists of a value and a pointer. The pointer contains the memory address of the next node in the line. An implementation of a linked list would include functions that do things such as retrieve the next node based on the memory address stored in the current node, delete a node while changing the node before it to point to the node after the deleted node to keep the list from breaking, and other such tasks that reassign the order of the list.

Benefits of a linked list over arrays include being much faster to reorganize, faster searching through the list, and the structure being excellent for recursion. Downsides include slightly larger overhead for storage, iteration through the list taking longer than iteration through an array, and less general convenience of useability.

Edit: see UG’s post for a visual representation of the structure of a linked list.

 
Flag Post

If you’re looking for speed, you should just implement a next property in your class that you want to be part of the linked list. This saves the overhead of having a wrapper Node class and function calls such as hasNext, etc.

package {
	public class ILL extends Object {
		public var next:ILL
		public var someProperty:uint
	}
}
//create your linked list
var rootNode:ILL = new ILL()
var l:ILL = rootNode
for(var i:Number = 1; i < 10; i++) {
	l = l.next = new ILL()
	l.someProperty = i
}
//traverse your linked list
l = rootNode
do {
	trace(l.someProperty)
} while(l = l.next)

Sorry for all the Is and Ls…

I seem to remember that this is slightly faster than iterating over an array in AS3.

 
Flag Post

^ I don’t understand how it could be faster to iterate through than an array, since they would be the same without taking account data access times due to the linked list almost certainly not being all in one contiguous block of memory like an array.

 
Flag Post

Me seeming to remember doesn’t mean that it is. Keep in mind that arrays use dynamic references which are slower to access. I think it would be tough to say from a theoretical standpoint which is faster in AS3.

 
Flag Post
Originally posted by BigJM:

Me seeming to remember doesn’t mean that it is. Keep in mind that arrays use dynamic references which are slower to access. I think it would be tough to say from a theoretical standpoint which is faster in AS3.

Oh you’re right, I haven’t worked in AS3 in about a month and I forgot for a minute that AS3 arrays work more like vectors than for example c++ arrays >.>

I’m actually not sure which would be faster on AS3 now, if only skyboy would stop by and solve all our problems.

 
Flag Post

I think I’d need more than skyboy to solve all my problems.

 
Flag Post

So a singly-linked list… would that be like a byte array?

 
Flag Post
Originally posted by jasonjie88:

So a singly-linked list… would that be like a byte array?

A byte array is an array…that has bytes in it :P

Ok but seriously, think of it like this. An array is a bunch of boxes sitting side by side. A linked list is a bunch of boxes sitting all over the place that have a number written on them and a post it note saying which numbered box goes next. The row of boxes side by side is less convenient to move around because you have to keep it all together and physically shift them to reorder them, but the boxes with post it notes just need you to cross out the number on the note and write a different one in order to reorder them.

It’s easier to change things in a list than an array, but if you search through the array (the boxes sitting in a row) you can do it faster because you don’t need to walk around the room trying to find the next box each time like you would for a list.

Does that help?

 
Flag Post
Originally posted by jasonjie88:

So a singly-linked list… would that be like a byte array?

How did you come to this conclusion?

 
Flag Post

Well, all the bytes are arranged in a particular order, and it is sort of easier to sort stuff, but you’d have to look through the byte-array, bit by bit, to find something. I think I got the meaning wrong there. But I understand better now.

 
Flag Post
Originally posted by jasonjie88:

Well, all the bytes are arranged in a particular order, and it is sort of easier to sort stuff, but you’d have to look through the byte-array, bit by bit, to find something. I think I got the meaning wrong there. But I understand better now.

hrrm then you are right. but in a byte array you can also access by index.

 
Flag Post

One byte does not link to the next byte; therefore it is not a linked list.

 
Flag Post

From your posts you appear confused by these high tech explanations.

I made a blog post explaining the usage and functionality of my own linked lists for JavaScript some time back, but it works just as well for ActionScript. You can read it here (mirror pastebin)

It should help you understand how the infernal things work and why you would want to use them. :)

 
Flag Post

It depends on the usage whether you wanna use a vector/array or a linked list!

Linked lists are good for very fast insertion/deletion/splicing (e.g to remove a node from the middle you simply link the 2 at either side of it) where as deleting an entry in the middle of a vector would invole moving half the entries down one.

vector is good for random access (indexing into it ‘vec45’ ) you can’t do this in a linked list, you’d have to start at the beginning and iterate through the list to the entry you want which could be quite expensive!

 
Flag Post

Linked lists are usefull when you already have your data wrapped and can easily extend it to linked list form using next but if you don’t then the wrapping introduces quite an overhead so it is actually slower.

When it comes to iteration array/vector was largely optimized in latest flash players so there is almost zero difference. There is a performance boost when you want to iterate nested lists as opposed to nested arrays simply especially when using length lookup for array iteration.

 
Flag Post
Originally posted by sHTiF:

When it comes to iteration array/vector was largely optimized in latest flash players so there is almost zero difference. There is a performance boost when you want to iterate nested lists as opposed to nested arrays simply especially when using length lookup for array iteration.

Removing elements is still something that linked lists has a very strong advantage in though, and removing elements is kinda essential to a lot of things. For instance, a list over all active enemies (that can die in any random order depending on who the player shoots).

 
Flag Post
Originally posted by JayHobsie:

It depends on the usage whether you wanna use a vector/array or a linked list!

Linked lists are good for very fast insertion/deletion/splicing (e.g to remove a node from the middle you simply link the 2 at either side of it) where as deleting an entry in the middle of a vector would invole moving half the entries down one.

vector is good for random access (indexing into it ‘vec45’ ) you can’t do this in a linked list, you’d have to start at the beginning and iterate through the list to the entry you want which could be quite expensive!

You can run a binary search to find which one you want rather than iterating through.

 
Flag Post

‘Enemies’ is one instance where you’re better off with an array than with a linked list. It is overwhelmingly likely that you’ll want to update every enemy once every frame, so you will need to iterate, but will only need to add or remove enemies once in a while. Additionally, it will likely not matter what the order of the enemies is in the array, so to delete at index i you can just copy the contents at index length-1 to index i and then decrement length.

Linked lists for enemies are the wrong tool for the job.

Edit: \/ Iterating through an array is faster than iterating through a linked list. The frame handler, where you will be iterating over all enemies every frame is the part of your code where you need to be fast.

 
Flag Post
Originally posted by Ace_Blue:

‘Enemies’ is one instance where you’re better off with an array than with a linked list. It is overwhelmingly likely that you’ll want to update every enemy once every frame, so you will need to iterate, but will only need to add or remove enemies once in a while. Additionally, it will likely not matter what the order of the enemies is in the array, so to delete at index i you can just copy the contents at index length-1 to index i and then decrement length.

Linked lists for enemies are the wrong tool for the job.

Wait what? While it’s true that arrays are vastly superior at indexed access, iterating is about the same speed on linked lists and arrays. What would be problematic about updating all enemies in a linked list? I don’t understand.

 
Flag Post

Sure you can iterate over them without a problem but what happens if one of the ones in the middle of your SLL dies? unless your keeping track of the prev node your pretty much boned. An array is a much better choice for such a thing. A doubly linked list is workable here obviously though.

What linked lists are freaking great at are stuff like enqueues and dequeues. For games paths returned from your pathfinder are a good candidate for a SLL because your always going to go through them one at a time front to back. (first in first out) Building queues in RTS games are great for that also. (a stack is a SLL that is ‘last in first out’)

There are lots of places to use linked lists.

 
Flag Post

Um, your iterator keeps track of the previous node?

Just do previous.next = current.next; current.next = null;