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