Linked List¶

1

import "std/data/linked-list";

LinkedList<T> struct¶

Implements: IIterable<T>

A linked list is a common, dynamically resizable data structure to store uniform data in order. It is characterized by the pointer for each item, pointing to the next one.

E.g. for a LinkedList:
1234 -> 4567 -> 7890 -> 4567 -> nil
tail head

Time complexity:
Insert: O(1)
Delete: O(1)
Search: O(n)

Beware that each add operation allocates memory and every remove operation frees memory.

Methods¶

pushBack¶

1

public p LinkedList.pushBack(const T& value)

Pushes a new item to the back of the list

Parameters

pushFront¶

1

public p LinkedList.pushFront(const T& value)

Pushes a new item to the front of the list

Parameters

insertAt¶

1

public p LinkedList.insertAt(unsigned long idx, const T& value)

Inserts a new item at the given index

Parameters

insertAt¶

1

public inline p LinkedList.insertAt(unsigned int idx, const T& value)

Inserts a new item at the given index

Parameters

remove¶

1

public p LinkedList.remove(const T& valueToRemove)

Removes the first occurrence of the given value

Parameters

removeAt¶

1

public p LinkedList.removeAt(unsigned long idx)

Removes the first occurrence of the given value

Parameters

removeAt¶

1

public inline p LinkedList.removeAt(unsigned int idx)

Removes the first occurrence of the given value

Parameters

removeFront¶

1

public inline p LinkedList.removeFront()

Removes the first item of the list

removeBack¶

1

public inline p LinkedList.removeBack()

Removes the last item of the list

getSize¶

1

public inline f<unsigned long> LinkedList.getSize()

Returns the size of the list

Returns: unsigned long — Size of the list

isEmpty¶

1

public inline f<bool> LinkedList.isEmpty()

Returns if the list is empty

Returns: bool — true if the list is empty, false otherwise

get¶

1

public f<T&> LinkedList.get(unsigned long idx)

Returns the item at the given index

Parameters

Returns: T& — Reference to the item

get¶

1

public inline f<T&> LinkedList.get(unsigned int idx)

Returns the item at the given index

Parameters

Returns: T& — Reference to the item

getFront¶

1

public inline f<T&> LinkedList.getFront()

Returns the first item of the list

Returns: T& — Reference to the first item

getBack¶

1

public inline f<T&> LinkedList.getBack()

Returns the last item of the list

Returns: T& — Reference to the last item

clear¶

1

public inline p LinkedList.clear()

Clears the list

getIterator¶

1

public f<LinkedListIterator<T>> LinkedList.getIterator()

Retrieve a forward iterator for the linked list

Returns: LinkedListIterator<T>

LinkedListIterator<T> struct¶

Implements: IIterator<T>

Iterator to iterate over a linked list data structure

Constructors¶

ctor¶

1

public p LinkedListIterator.ctor<T>(LinkedList<T>& list)

Construct a linked list iterator over the given linked list

Parameters

Methods¶

get¶

1

public inline f<T&> LinkedListIterator.get()

Returns the current item of the linked list

Returns: T& — Reference to the current item

getIdx¶

1

public inline f<Pair<unsigned long, T&>> LinkedListIterator.getIdx()

Returns the current index and the current item of the linked list

Returns: Pair<unsigned long, T&> — Pair of current index and reference to current item

isValid¶

1

public inline f<bool> LinkedListIterator.isValid()

Check if the iterator is valid

Returns: bool — true or false

next¶

1

public inline p LinkedListIterator.next()

Returns the current item of the linked list iterator and moves the cursor to the next item

Operators¶

operator++¶

1

public inline p operator++<T>(LinkedListIterator<T>& it)

Advances the cursor by one

Parameters

operator--¶

1

public inline p operator--<T>(LinkedListIterator<T>& it)

Move the cursor back by one

Parameters

operator+=¶

1

public inline p operator+=<T, Numeric>(LinkedListIterator<T>& it, Numeric offset)

Advances the cursor by the given offset

Parameters

operator-=¶

1

public inline p operator-=<T, Numeric>(LinkedListIterator<T>& it, Numeric offset)

Move the cursor back by the given offset

Parameters