Doubly Linked List¶

1

import "std/data/doubly-linked-list";

DoublyLinkedList<T> struct¶

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

Time complexity:
Insert at front/back: O(1)
Insert at index: O(n)
Delete at front/back: O(1)
Delete at index: O(n)
Search: O(n)

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

Methods¶

pushBack¶

1

public p DoublyLinkedList.pushBack(const T& value)

Pushes a new item to the back of the list

Parameters

pushFront¶

1

public p DoublyLinkedList.pushFront(const T& value)

Pushes a new item to the front of the list

Parameters

insertAt¶

1

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

Inserts a new item at the given index

Parameters

remove¶

1

public p DoublyLinkedList.remove(const T& valueToRemove)

Removes the first occurrence of the given value

Parameters

removeAt¶

1

public p DoublyLinkedList.removeAt(unsigned long idx)

Removes the item at the given index

Parameters

removeAt¶

1

public p DoublyLinkedList.removeAt(unsigned int idx)

Removes the item at the given index

Parameters

removeFront¶

1

public p DoublyLinkedList.removeFront()

Removes the first item of the list

removeBack¶

1

public p DoublyLinkedList.removeBack()

Removes the last item of the list

getSize¶

1

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

Returns the size of the list

Returns: unsigned long — Size of the list

isEmpty¶

1

public inline f<bool> DoublyLinkedList.isEmpty()

Returns if the list is empty

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

get¶

1

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

Returns the item at the given index

Parameters

Returns: T& — Reference to the item

get¶

1

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

Returns the item at the given index

Parameters

Returns: T& — Reference to the item

getFront¶

1

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

Returns the first item of the list

Returns: T& — Reference to the first item

getBack¶

1

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

Returns the last item of the list

Returns: T& — Reference to the last item