LinkedList

Inherits: Reference < Object

A doubly linked list data structure.

Description

A data structure which consists of a set of sequentially linked elements called nodes. Uses ListNode as a basic building block. Each node contains a reference to the previous node, the next node, and the data associated with the node. Insertion and deletion operations are faster O(1) compared to Array, but performs worse for random access O(n).

ListNodes are constructed by inserting values to the list, and are not meant to be instantiated directly:

var list = LinkedList.new()
var node = list.push_back("Goost")
var same_node = list.find("Goost")

Traversing a list can be done using a for loop:

for node in list:
    print(node)

or by manually walking the list using the nodes themselves:

# Forward!
var node = list.front
while node:
    print(node)
    node = node.next

# Backward!
var node = list.back
while node:
    print(node)
    node = node.prev

Nodes can be passed around throughout the code, and values can be changed dynamically for nodes which are already inserted into the list.

Methods

void clear ( )
void create_from ( Variant value )
bool empty ( ) const
bool erase ( Variant value )
ListNode find ( Variant value )
Array get_elements ( )
Array get_nodes ( )
ListNode insert_after ( ListNode node, Variant value )
ListNode insert_before ( ListNode node, Variant value )
void invert ( )
void move_before ( ListNode node, ListNode before_node )
void move_to_back ( ListNode node )
void move_to_front ( ListNode node )
void pop_back ( )
void pop_front ( )
ListNode push_back ( Variant value )
ListNode push_front ( Variant value )
int size ( ) const
void sort ( )
void swap ( ListNode node_A, ListNode node_B )

Property Descriptions

Getter get_back()

The last node in the list. Can be null if the list is empty.

Getter get_front()

The first node in the list. Can be null if the list is empty.

Method Descriptions

  • void clear ( )

Erases all nodes from the list.

  • void create_from ( Variant value )

Initializes the list from a Variant compatible type. Clears all nodes before copying.

If value is null, just clears the contents of the list.

If value is Array, each element in the array is converted to a ListNode. Pool*Arrays are converted similarly to Array.

If value is Dictionary, each key in the dictionary is converted to a ListNode, and the values are encoded as ListNode meta variables using Object.set_meta. Values can be retrieved later with node.get_meta("value") for each node.

Any other type is simply pushed back to the list.

  • bool empty ( ) const

Returns true if the list doesn’t contain any nodes.

Erases (deletes) the first found node with a matching value in the list.

Returns a node if a list contains a node with specified value, otherwise returns null.

An alias for get_nodes.

Returns all nodes as an Array, preserving front-to-back order.

Constructs a new ListNode and places it after existing node in the list. If node is null, then the value is pushed at the end of the list, making the behavior equivalent to push_back.

Constructs a new ListNode and places it before existing node in the list. If node is null, then the value is pushed at the end of the list, making the behavior equivalent to push_back.

  • void invert ( )

Inverts the order of nodes in the list.

Moves a node before the other one within the list.

Moves a node to the back of the list (back node will point to node).

Moves a node to the front of the list (the front node will point to node).

  • void pop_back ( )

Erases the last node of the list. Make sure to preserve the ListNode.value if you’re interested in the data associated with the node:

var value = list.back.value
list.pop_back()
  • void pop_front ( )

Erases the first node of the list. Make sure to preserve the ListNode.value if you’re interested in the data associated with the node:

var value = list.front.value
list.pop_front()

Constructs a new ListNode and pushes it at the end of the list.

Constructs a new ListNode and pushes it at the beginning of the list.

  • int size ( ) const

Returns the total number of nodes in the list.

  • void sort ( )

Sorts the list in alphabetical order if the list contains Strings. If the list contains nodes with different types of values, these are sorted according to the order of type in Variant.

Moves node_A to the position of node_B, and moves node_B to the original position of node_A. If node_A == node_B, does nothing.