The LinkedList

Table of contents

The LinkedList

What is a linked list?

A linked list is a container element a bit similar to an array, but differently working. An array is a block of memory split up in many parts which is reserved when it is created, or redimensioned. A linked list doesn't have to be redimensioned: New elements are created elsewhere in the memory and linked to each other (every element contains a reference to the next and, in case of a double-linked list, to the previous element). This way we can create and delete elements when- and whereever we want to.

How to use the LinkedList

You create a linked list with Set ll = New LinkedList If you don't use the BackInserter, you can add an item at the back of the list with

itemRef = ll.AddBack( valueorobject )

or in front of the list with

itemRef = ll.AddFront( valueorobject )

You can also add an item at a various position in the list with

itemRef = ll.Insert( position, valueorobject )

The return values are references to the item object. The item can simply be deleted from the list with using

itemRef.Delete or ll.Delete ( index )


Once an item is in the list, you can access it with

valueorobjectvar = ll( index )

or

valueorobjectvar = ll.Item( index )

Assigning values and objects to a position is done with

ll.Item( index ) = value
Set ll.Item( index ) = object

(It occasionally works without the .Item, but I don't get why. Basically it shouldn't, as VBS doesn't allow more than 1 default method/property.) IMPORTANT: The use of these array-imitating methods is deprecated for several reasons (speed as well as invalidation issues after insertions/deletions) and provided only for compatibility with the array approach. Use iterators instead to walk through lists.

The number of items in the list is returned with

var = ll.Count

Important: Arrays in LinkedLists

If you add an array as an item to a linked list, you can't access it normally with

ll( index, ArrayIndex )

because of VBS's limitations (no optional arguments). Internally the array is packed into an object which handles it. So you have to use

ll( index ).Item( AryIndex )

Because of the same reason currently only 1-dimensional arrays are supported.

The Iterator

What is an iterator?

Basically, the original iterator is an abstraction of a pointer for to point inside containers. This iterator however doesn't have the original pointer interface for obvious reasons (VBS doesn't have any pointers or overloadable operators.)

What do I use it for?

It is useful for performing actions on a sequence of items in a LinkedList. Most basic example is

myIterator = ll.Begin
lastIterator= ll.Last
Do Until myIterator.Object Is lastIterator.Object
	Debug.DebugMsg myIterator.Item
	myIterator.Iterate()
Loop

This will output a list of all values in ll.

How do I use it?

You first have to get an iterator with

it = ll.Begin
it = ll.Last
it = ll.RBegin
it = ll.RLast
it = ll.AtIt ( index )

Begin and Last return the iterators for the first element and the terminator (NOT the last element. The terminator is the position behind the last element, the first element not to be processed anymore.) RBegin and RLast are used to go through the list backwards: RBegin returns the last item and RLast the item before the first (a front terminator). AtIt returns the iterator for the item at position index.

You get the selected item with it.Item and the selected LinkedList object (needed for equivalency comparison) with it.Object. it.Delete() deletes the current item and proceeds to the next one.

With it.Iterate() you proceed forward in the list, with it.Iterate() you step backwards. Both of the functions return a copy of the iterator after the operation. Important: For going through the list backwards, you need IterateBack(), even though the end of the list is in RBegin and the start in RLast. This may change in future versions, if a direction flag is implemented.

You get a copy of the iterator through normal assignment (without Set): it2 = it1 or with it2 = it1.GetCopy

The BackInserter

What is a back inserter?

Originally, the back inserter is a special form of iterator which iterates automatically after having been used and is write-only. It adds the assigned value as item at the end of the list.

How do I use it?

The usage is fairly simple. First you get a BackInserter instance of a LinkedList with bi = ll.BackInserter(). Afterwards you can add items to the list with

bi.Item = valueorobject1
bi.Item = valueorobject2
bi.Item = valueorobject3

You can get a copy of the BackInserter through assignment, i.e. bi2 = bi1 or explicitly with bi2 = bi1.GetCopy.

The ArrayContainer