Linked List/What Are Linked Lists

What is a Linked List?

A linked list is a list of objects linked together by a series of pointers to another object in that list. This allows for a near unlimited amount of objects to be connected; a worthy substitution for dynamic arrays (arrays of no defined size), which are not present in UnrealScript. This can be used for a variety of purposes: a player's inventory a history of messages, a bunch of pipebombs a player can detonate, or even simply have easier and quicker access to certain actors.

How a List Is Set Up

A linked list requires two parts:

a base object. This part, under strange circumstances, may be omitted which has a pointer to a member of the list (for the purpose of this tutorial – the first
a pointer in every list element to another element

Class ListElement extends object;
Var ListElement Next; // the next list element.

Class SomeImportantActor extends actor;
Var ListElement ListElement; // the first element in the list

SomeImportantActor should be some critical actor in your mod. As an example, Unreal uses the LevelInfo to hold the pointer to the first Pawn and NavigationPoint in the PawnList and NavigationPointList, respectfully. The first inventory item of a player is connected by a pointer residing inside of that player. The Next pointer points to the next element of the list. The list terminates when Next==None.

A third part of the list also exists; contents. This is simply whatever the list elements are supposed to do or store.

Navigating through a List

The easiest to move through the list is simply to use the For loop.

// this is run inside the SomeImportantActor class.
Local ListElement Element;
For (Element=ListElement; Element!=none; Element=Element.Next)
  //here each element's variables can be read, edited, or have functions called on it.

Note how the above works. First the temporary Element pointer is set to the base element. At the end of each loop, the Element pointer is set to its Next pointer. This continues until no more elements are present (i.e. the Element pointer equals None).

Adding to Lists

There are three ways of adding to a list; at the beginning, at the end, or in the middle.

Note: In this example the ListElement class is only an object, but not an actor. If you make a subclass of actor then you should replace new (none) class'ListElement'; with spawn (class'ListElement');.

At the Beginning

Simply instantiate an object, set its Next pointer to the current base (the ListElement pointer), and then set it as the base:

TempElement=New (none) class'ListElement';
TempElement.next=ListElement;
ListElement=TempElement;

At the End

There are two ways that a new element can be added at the end of a list. The loop method inside the SomeImportantActor:

Local ListElement Element;
Element=ListElement;
While (Element.next!=none)
  Element=Element.next;
Element.Next=new (none) class'ListElement';

Note that this loop terminates not when Element is none, but when an Element's next pointer is none. This allows a pointer to the last element of the list to exist when the loop has completed.

The "1337 function in each element" method: I do not know of the "official" name of this method. Nonetheless, this is the simpler method, which is used to add mutators. Remember that list elements are true objects and CAN have functions called on them. This allows for very simple code to exist. Inside SomeImportantActor:

ListElement.AddElement(new (none) class'ListElement');

The class ListElement has the following function:

Function AddElement (ListElement NewElement)
{
  If (Next!=None)
    Next.AddElement(NewElement);
  Else
    Next=NewElement;
}

First a ListElement is instantiated. Then the ListElement's AddElement function is called with a pointer to the new ListElement. If there is another element in the list, it then calls the AddElement function on that element. Eventually, the end of the list is reached, where Next is none. Now Next is set to point to the new ListElement.

In the Middle

Adding an element into the middle of any list obviously requires a pointer to the item one wishes to add after. Assume that Element is some element inside the list:

TempElement=new class'listelement';
TempElement.Next=Element.Next;
Element.Next=TempElement;

Again an element is created. Its Next var is set to whatever the Next var is of the element that this one is being added in front of. Finally, the element that is going to have the new element added after it has its Next var set to the new element.

Removing Items

In the case of actor lists, it is not safe to simply destroy an actor that is part of the list (objects do not apply as they cannot be manually destroyed). This causes any list elements after it to become unlinked. To remove any list item (it is safe to do this in actor.destroyed()), one must do the following:

// in the SomeImportantActor class
Function RemoveElement(ListElement Element)
{
  Local ListElement List;
  If (Element==ListElement)
    Element=ListElement.Next;
  Else
    For (List=Element;List!=none;List=List.Next)
      If (List.Next==Element)
      {
        List.Next=Element.Next;
        Break;
      }
}

First and foremost, a check must be performed to see if the element to be removed is the base pointer. If it is, then the base is simply set to whatever that element's next is. Yet, if this is not the case, the code must go looking for that doomed object. A loop is performed which goes through all the elements. With each loop, it is checked temporary List pointer's Next pointer is the item that should be removed. If this is the case, that element's next pointer is set to the to-be-deleted element's next. The loop can then be terminated.

You can synthesize the above information to conduct some exciting list manipulation. For instance to move a list item, you can simply remove it and then insert it in the middle of something else.

Advanced Lists

The above is only the basics of how a list is constructed. Many other pointers however may exist in a list. For instance, a two-way list can be created by having each item not only have a pointer to the next, but also to the previous. There can also be a pointer in every element to the base or even to the end. While this does mean execution can be faster and frankly easier to set up, it does mean more needs to be done when adding or removing elements. Also note that more pointers allow greater flexibility. For instance, with a pointer to the first or previous element, this allows for the link to the list to be at any element, rather than the first. As an example, in Operation: Na Pali, the translator has a history of all previous messages. I simply have a pointer to the TranslatorHistoryList that holds the current message. If a user wishes to read older or newer messages, the pointer to the TranslatorHistoryList simply changes to the current pointer's Next or Prev pointers, respectfully. This allows for simple and fast executing code.

Note: When variables exist that apply to the list as a whole, rather than a per element basis, they should be placed in the actor that links to the list or the first element. In the latter case, this often means having a pointer to the first element in all elements.

Comments

Sobiwan: Where is this page linked from? I only found it from Recent Changes.

GRAF1K: It's a subpage of Linked List which is linked to from:

AssaultPath
BigHeadRules
Compiler Errors
Controller
GameInfo
GameInfo (UT)
GameObjective
GameRules
IonCannon
Iterator
ListItem
Mutator
NavigationPoint (UT)
SpawnNotify
SquadAI
TeamAI
Terminology
UnrealScript
UnrealScript For CPlusPlus Programmers
Wiki Trail
Writing And Using An Embedded Mutator
ZoneInfo (UT)

Section 1 of 2 – Next Page: /Existing Lists in Unreal Tournament