Module: lib-tde.datastructure.linkedList

Lua Implementation of a double linked list

This module describes the api usage of the double linked list You can traverse the list in both directions, add items, remove items etc

local linkedList = require("lib-tde.datastructure.linkedList")
local list = linkedList()
list.setHead("This is the value of head")
for i = 1, 50 do
     -- set the value of next
     list.setNext(i)
     -- traverse the list
     list.next()
end
-- this prints out 50
print(list.head.value)

-- this prints out 49
print(list.head.previous.value)
-- this prints out 48
print(list.head.previous.previous.value)

Alternatively you can do the same with previous

local linkedList = require("lib-tde.datastructure.linkedList")
local list = linkedList()
list.setHead("This is the value of head")
for i = 1, 50 do
     -- set the value of next
     list.setPrevious(i)
     -- traverse the list
     list.previous()
end

Time complexity:

  • Lookup element O(n)
  • Insert element O(1)
  • Remove element O(1)
  • update element 0(1)

Linked lists are extremely good to update values and read them They are however bad at searching/traversing lists

Class Hierarchy

  • lib-tde.datastructure.linkedList

Info:

  • Copyright: 2020 Tom Meyers
  • Author: Tom Meyers

Static module functions

lib-tde.datastrucuture.linkedList () -> table Create a new Double Linked List
lib-tde.datastrucuture.linkedList.setHead (value) Update the value of the current head to value
lib-tde.datastrucuture.linkedList.setNext (value) Update the value of the next object in the list (create on if it doesn't exist yet)
lib-tde.datastrucuture.linkedList.setPrevious (value) Update the value of the previous object in the list (create on if it doesn't exist yet)
lib-tde.datastrucuture.linkedList.next () Move the current pointer to the next value
lib-tde.datastrucuture.linkedList.previous () Move the current pointer to the previous value
lib-tde.datastrucuture.linkedList.insertNext (value) Insert a new item in between list.head and list.head.next
lib-tde.datastrucuture.linkedList.insertPrevious (value) Insert a new item in between list.head and list.head.previous
lib-tde.datastrucuture.linkedList.removeNext () Remove the next value and replace it by list.head.next.next
lib-tde.datastrucuture.linkedList.removePrevious () Remove the previous value and replace it by list.head.previous.previous

Object properties

head table The current pointer in the linked list
next table The next pointer in the linked list
previous table The previous pointer in the linked list
value object The value that is stored in the linked list


Static module functions

lib-tde.datastrucuture.linkedList () -> table
Create a new Double Linked List

Returns:

    table An empty linked list

Usage:

    -- This will create a new empty linked list
 lib-tde.datastrucuture.linkedList()
lib-tde.datastrucuture.linkedList.setHead (value)
Update the value of the current head to value

Parameters:

  • value object The value to put into the head

Usage:

    -- update the value of head to value
 linkedList.setHead("tde") -- updates list.head.value
lib-tde.datastrucuture.linkedList.setNext (value)
Update the value of the next object in the list (create on if it doesn't exist yet)

Parameters:

  • value object The value to put into next

Usage:

    -- update the value of next to value
 linkedList.setNext("tde") -- updates list.head.next.value
lib-tde.datastrucuture.linkedList.setPrevious (value)
Update the value of the previous object in the list (create on if it doesn't exist yet)

Parameters:

  • value object The value to put into previous

Usage:

    -- update the value of previous to value
 linkedList.setPrevious("tde") -- updates list.head.previous.value
lib-tde.datastrucuture.linkedList.next ()
Move the current pointer to the next value

Usage:

    -- Move head to the value of next
 linkedList.next() -- list.head is now list.head.next
lib-tde.datastrucuture.linkedList.previous ()
Move the current pointer to the previous value

Usage:

    -- Move head to the value of previous
 linkedList.previous() -- list.head is now list.head.previous
lib-tde.datastrucuture.linkedList.insertNext (value)
Insert a new item in between list.head and list.head.next

Parameters:

  • value object The value to put between head and next

Usage:

    -- Insert a new item with value "tde" between list.head and list.head.next
 linkedList.insertNext("tde") -- updates list.head.next.value -> goes to list.head.next.next.value and list.head.next.value = "tde"
lib-tde.datastrucuture.linkedList.insertPrevious (value)
Insert a new item in between list.head and list.head.previous

Parameters:

  • value object The value to put between head and previous

Usage:

    -- Insert a new item with value "tde" between list.head and list.head.previous
 linkedList.insertPrevious("tde") -- updates list.head.previous.value -> goes to list.head.previous.previous.value and list.head.previous.value = "tde"
lib-tde.datastrucuture.linkedList.removeNext ()
Remove the next value and replace it by list.head.next.next

Usage:

    -- Remove the entry associated with list.head.next
 linkedList.removeNext() -- list.head.next becomes list.head.next.next
lib-tde.datastrucuture.linkedList.removePrevious ()
Remove the previous value and replace it by list.head.previous.previous

Usage:

    -- Remove the entry associated with list.head.previous
 linkedList.removePrevious() -- list.head.previous becomes list.head.previous.previous

Object properties

head table
The current pointer in the linked list
next table
The next pointer in the linked list
previous table
The previous pointer in the linked list
value object
The value that is stored in the linked list
generated by LDoc 1.4.6 Build with 💜 By F0xedb Last updated 2021-05-21 03:30:15