Doubly Linked List - ciaabcdefg/lua-dt GitHub Wiki

Doubly Linked List - list.lua


A doubly linked list is a data structure consisting of data holders known as nodes. A node contains the data, the references to the previous and next nodes in the list.

While accessing data on the list is slow, it allows quick front and back insertions and deletions, which is useful for implementing other structures that exclusively rely on these functionalities.

The doubly linked list is similar to the regular singly linked list, except the latter can only be traversed in one direction.

Initialization

List.new(fromTable: table [default: {}]): List

Time complexity: $\Theta(n)$ for $n$ elements in fromTable

  • Initializes a new list. If fromTable is empty, this creates an empty list.
  • Otherwise, the list is initialized according to fromTable.

Examples

This creates an empty list.

local list = require("list")
local myList = list.List.new()

print(myList)

Output: []

On the other hand, this creates an initialized list from a table.

local list = require("list")
local myList = list.List.new({1, 2, 3, "FooBar", 5})

print(myList)

Output: [1, 2, 3, FooBar, 5]

Attributes

Name Type Description
list.size number An integer denoting the size of the list.
list.front Node The node at the front of the list. For empty lists, this is nil by default.
list.back Node The node at the back of the list. Like list.front, this is nil for empty arrays.

Methods

list.pushBack(value: any): void

Time complexity: $\Theta(1)$

  • Inserts a new element value at the back of the list.
  • Increases size by 1.

Example

local list = require("list")
local myList = list.List.new()

print(myList)
myList.pushBack(2)
print(myList)

myList.pushBack("Hello")
print(myList)

Output:

[]
[2]
[2, Hello]

list.pushFront(value: any): void

Time complexity: $\Theta(1)$

  • Inserts a new element value at the front of the list.
  • Increases size by 1.

Example

local list = require("list")
local myList = list.List.new({1, 5, 4, 2})

print(myList)

myList.pushFront("Front")
print(myList)

Output:

[1, 5, 4, 2]
[Front, 1, 5, 4, 2]

list.popBack(value: any): any

Time complexity: $\Theta(1)$

  • Removes the last element from the list and returns it.
  • Decreases size by 1.

Example

local list = require("list")
local myList = list.List.new({5, 5, 2})

print(myList)
print(myList.popBack())
print(myList)

Output:

[5, 5, 2]
2
[5, 5]

list.popFront(value: any): any

Time complexity: $\Theta(1)$

  • Removes the first element from the list and returns it.
  • Decreases size by 1.

Example

local list = require("list")
local myList = list.List.new({5, 7, 2})

print(myList)
print(myList.popFront())
print(myList)

Output:

[5, 7, 2]
5
[7, 2]

list.find(value: any): number

Time complexity: $O(n)$

  • Finds the first matching element and returns its index.
  • If none exists, nil is returned.

Example

local list = require("list")
local myList = list.List.new({1, 2, 3, 4, 5, 6, "Hi"})

print(myList.find("Hi"))
print(myList.find(8))

Output:

7
nil

list.findNode(value: any): Node

Time complexity: $O(n)$

  • Finds the first matching element and returns the node containing it.
  • If none exists, nil is returned.

Example

local list = require("list")
local myList = list.List.new({1, 2, 3, 4, 5, 6, "Hi"})

print(myList.findNode("Hi"))
print(myList.findNode(8))

Output:

Node: value = Hi
nil

list.get(index: number): any

Equivalent to: list(index)
Time complexity: $O(n)$ or $\Theta(index)$ if $index \leq n$

  • Returns the value at index.
  • index ranges from 1 to list.size and additionally, the range -1 to -list.size is also accepted. Having index as -1 and -list.size will return the last and first elements respectively.
  • If index is out of range, nil is returned.

Example

local list = require("list")
local myList = list.List.new({"Mark", "John", "James", "David"})

print(myList.get(-1))
print(myList(2))
print(myList(100))

Output:

David
John
nil

list.getNode(index: number): Node

Time complexity: $O(n)$ or $\Theta(index)$ if $index \leq n$

  • Returns the node at index.
  • index ranges from 1 to list.size and additionally, the range -1 to -list.size is also accepted. Having index as -1 and -list.size will return the last and first elements respectively.
  • If index is out of range, nil is returned.

Example

local list = require("list")
local myList = list.List.new({"Mark", "John", "James", "David"})

print(myList.getNode(2))
print(myList.getNode(-2))
print(myList.getNode(-4))

Output:

Node: value = John
Node: value = James
Node: value = Mark

list.getRange(indexStart: number, indexEnd: number): List

Time complexity: $O(n)$

  • Returns a new (shallowly copied) list of elements from indexStart to indexEnd.
  • Indices are normalized similarly to list.find and list.get.
  • If indexEnd exceeds list.size, the resulting list is a list containing elements from indexStart to the end of the list.

Example

local list = require("list")
local myList = list.List.new({1, 2, 3, 4, 5, 6, 7, 8})

print(myList.getRange(5, 100))
print(myList.getRange(4, 4))

Output:

[5, 6, 7, 8]
[4]

list.getNodeRange(indexStart: number, indexEnd: number): table

Time complexity: $O(n)$

  • Returns a new (shallowly copied) table of nodes from indexStart to indexEnd.
  • Indices are normalized similarly to list.find and list.get.
  • If indexEnd exceeds list.size, the resulting list is a list containing elements from indexStart to the end of the list.

Example

local list = require("list")
local myList = list.List.new({1, 2, 3, 4, 5, 6, 7, 8})

print(table.unpack(myList.getNodeRange(5, 100)))
print(table.unpack(myList.getNodeRange(4, 4)))

Output:

Node: value = 5 Node: value = 6 Node: value = 7 Node: value = 8
Node: value = 4

list.replaceAll(replaceWith: any, predicate: any [default: nil]): void

Time complexity: $\Theta(n)$

  • Replaces elements with respect to predicate.
  • If predicate is nil, all elements will be replaced with replaceWith.
  • If predicate is not a function, a new function that returns true if the value at each element is equal to predicate, otherwise false, is created and assigned to predicate at runtime.
  • If predicate is a single-argument function, it will be used to select which elements to replace. Otherwise, depending on the function itself, this method may or may not work correctly.

Example

local myList = list.List.new({5, 4, 3, 2, "Undefined", "Another One"})

myList.replaceAll(-999, function(value)
    if type(value) == "string" then return true end
    return false
end)
print(myList)

myList.replaceAll(123)
print(myList)

Output:

[5, 4, 3, 2, -999, -999]
[123, 123, 123, 123, 123, 123]

list.set(index: number, value: any): void

Time complexity: $O(n)$

  • Sets the element at index to value.
  • Indices are normalized similarly to list.find and list.get.
  • Improper values of index result in no change.

Example

local list = require("list")
local myList = list.List.new({7, 7, 7})

myList.set(2, 512)
myList.set(1000, 123)
print(myList)

Output:

[7, 512, 7]

list.remove(index: number): void

Time complexity: $O(n)$

  • Removes the element at index and returns it.
  • Indices are normalized similarly to list.find and list.get.
  • Improper values of index result in no change.

Example

local list = require("list")
local myList = list.List.new({"One", 2, "Three", 4, "Five"})

myList.remove(1)
print(myList)

myList.remove(2)
print(myList)

myList.remove(-1)
print(myList)

myList.remove(2315)
print(myList)

Output:

[2, Three, 4, Five]
[2, 4, Five]
[2, 4]
[2, 4]

list.concat(other: List, clean: bool [default: true]): void

Time complexity: $\Theta(1)$

  • Concatenates list with the other.
  • If clean is true, then other will be cleared of its node references (the actual nodes stay), reverting it back to an empty list.

Example

local list = require("list")
local myList1 = list.List.new({5, 5, 2})
local myList2 = list.List.new({9, 8, "End"})
local myList3 = list.List.new({"Front"})

myList1.concat(myList2)
print(myList1)
print(myList2)

myList3.concat(myList1, false)
print(myList3)
print(myList1)

Output:

[5, 5, 2, 9, 8, End]
[]
[Front, 5, 5, 2, 9, 8, End]
[5, 5, 2, 9, 8, End]

list.splice(other: List, index: number, clean: bool [default: true]): void

Time complexity: $\Theta(1)$

  • Transfers all elements in other to the list and places them after the element at position index.
  • If clean is true, then other will be cleared of its node references (the actual nodes stay), reverting it back to an empty list.

Example

local list = require("list")
local myList1 = list.List.new({1, "Start", "End", 7})
local myList2 = list.List.new({4, 5, 6})

myList1.splice(myList2, 2)
print(myList1)

Output:

[1, Start, 4, 5, 6, End, 7]

⚠️ list.clear(deep: bool [default: true]): void ⚠️

Warning: This method is not guaranteed to work correctly; the nodes themselves may not be picked up by the GC at all.
Time complexity: $\Theta(n)$ for $n$ elements if deep is true, otherwise $\Theta(1)$

  • If deep is true, all references to the nodes containing the data are removed one by one. The references to the front and back nodes are removed, then the size is set to zero.
  • Otherwise, only the references to the front and back nodes are removed, then the size is set to zero.

Example

local list = require("list")
local myList1 = list.List.new({5, 4, 2, 1, 10, 2})

print(myList1)

myList1.clear()
print(myList1)

Output:

[5, 4, 2, 1, 10, 2]
[]