Suphi's Linked List Module

Suphi's Linked List Module

Download | Video Tutorial | Discord Server

Features

Edit While Iterating     "Its safe to insert and remove links while iterating"
Fast Batch Remove        "Remove multiple links efficently"

Support My Work

If you liked my work and want to donate to me you can do so here


SourceCode

You can get the sourcecode to this module here

Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted.


Documentation

CONSTRUCTOR

new()
"Creates a new linked list"

LIST METHODS

InsertFront(link: table)  link
"Converts a table to a link and adds it to the front of the list"
InsertAfter(link: table)  link
"The same as InsertFront"
InsertBack(link: table)  link
"Converts a table to a link and adds it to the back of the list"
InsertBefore(link: table)  link
"The same as InsertBack"
GetNext(link: link?)  link?
"Gets the next link in the list if its the last link returns nil, if no link is passed into the method returns the first link"
GetPrevious(link: link?)  link?
"Gets the previous link in the list if its the first link returns nil, if no link is passed into the method returns the last link"
IterateForward(link: link?)  function list link?
"Returns a iterator that can be used in a for loop if a link is passed into this function it will start interating from that link"
IterateBackward(link: link?)  function list link?
"Returns a iterator that can be used in a for loop if a link is passed into this function it will start interating from that link"
RemoveFirst() link?
"Removes the first link in the list and returns that link, returns nil if there are no links in the list"
RemoveLast()  link?
"Removes the last link in the list and returns that link, returns nil if there are no links in the list"
RemoveUpTo(link: link?)  nil
"Removes all links before the passed in link making the passed in link now the first link in the list"
RemoveDownTo(link: link?)  nil
"Removes all links after the passed in link making the passed in link now the last link in the list"
RemoveAll()  nil
"Removes all links"

LINK METHODS

InsertAfter(link: table)  link
"Converts a table to a link and adds it after the link"
InsertBefore(link: table)  link
"Converts a table to a link and adds it before the link"
GetNext()  link?
"Gets the next link after this link if this link is the last link then nil is returned"
GetPrevious()  link?
"Gets the previous link before this link if this link is the first link then nil is returned"
Remove()  nil
"Removes this link from the list"
Clean()  nil
"This method should almost never be used but it removes the links metatable and sets Next and Previous to nil"

Example

-- Require the ModuleScript
local linkedList = require(16633916047)

-- Make a new linked list
local list = linkedList.new()

-- Insert 4 links
local link1 = list:InsertBack({Value = "A"})
local link2 = list:InsertBack({Value = "B"})
local link3 = list:InsertBack({Value = "C"})
local link4 = list:InsertBack({Value = "D"})

-- Iterate links forwards
for link in list:IterateForward() do print(link.Value) end

-- Remove link3 from the list
link3:Remove()

-- Remove the first link in the list
local removedLink = list:RemoveFirst()
print("Removed:", removedLink.Value)

-- Get the first link in the list
local firstLink = list:GetNext()
print("First:", firstLink.Value)

-- Get the second link in the list
local secondLink = firstLink:GetNext()
print("Second:", secondLink.Value)

-- Remove all links
list:RemoveAll()

One of the reasons why you might want to use a linked list

-- This will not work for a array
local array = {"A", "B", "C", "D", "E", "F"}
for index, value in array do
    print(index, value)
    if value == "D" then table.remove(array, 2) end
end
-- This will not work for a dictionary
local dictionary = {A = true, B = true, C = true, D = true, E = true, F = true}
for key, value in dictionary do
    print(key, value)
    if key == "D" then dictionary.G = true end
end
-- This will work for a linked list
local link1 = list:InsertBack({Value = "A"})
local link2 = list:InsertBack({Value = "B"})
local link3 = list:InsertBack({Value = "C"})
local link4 = list:InsertBack({Value = "D"})
local link5 = list:InsertBack({Value = "E"})
local link6 = list:InsertBack({Value = "F"})

for link in list:IterateForward() do
    print(link.Value)
    if link.Value == "D" then link2:Remove() end
end

for link in list:IterateForward() do
    print(link.Value)
    if link.Value == "D" then list:InsertBack({Value = "G"}) end
end

Example of a linked list in the wild

local link1 = rs.Heartbeat:Connect(function() end)
local link2 = rs.Heartbeat:Connect(function() end)
local link3 = rs.Heartbeat:Connect(function() end)
local link4 = rs.Heartbeat:Connect(function() link2:Disconnect() end) -- safe to disconnect
local link5 = rs.Heartbeat:Connect(function() rs.Heartbeat:Connect(function() end) end) -- safe to connect
local link6 = rs.Heartbeat:Connect(function() end)

Other Projects

Infinite Terrain
Suphi’s DataStore Module
Infinite Scripter
Mesh Editor
Toggle Block Comment
Toggle Decomposition Geometry
Tag Explorer
Suphi’s Linked List Module
Suphi’s Hybrid Linked List Module
Suphi’s RemoteFunction Module

16 Likes

Looks super complex cant wait to try this out!

Let’s goooo, new sushi tutorial! This seems super interesting :thinking:

1 Like

whats the point of this? a table could do the exact same thing way simpler with way less overhead

There are some applications for linked lists, mostly for “ordered” data structures. I’m personally not a fan of them but they have their uses.

A table cannot do the exact same things
here is a example

-- This will not work for a array
local array = {"A", "B", "C", "D", "E", "F"}
for index, value in array do
    print(index, value)
    if value == "D" then table.remove(array, 2) end
end
-- This will not work for a dictionary
local dictionary = {A = true, B = true, C = true, D = true, E = true, F = true}
for key, value in dictionary do
    print(key, value)
    if key == "D" then dictionary.G = true end
end
-- This will work for a linked list
local link1 = list:InsertBack({Value = "A"})
local link2 = list:InsertBack({Value = "B"})
local link3 = list:InsertBack({Value = "C"})
local link4 = list:InsertBack({Value = "D"})
local link5 = list:InsertBack({Value = "E"})
local link6 = list:InsertBack({Value = "F"})

for link in list:IterateForward() do
    print(link.Value)
    if link.Value == "D" then link2:Remove() end
end

for link in list:IterateForward() do
    print(link.Value)
    if link.Value == "D" then list:InsertBack({Value = "G"}) end
end

and here is a example that is commonly used in Roblox

local link1 = rs.Heartbeat:Connect(function() end)
local link2 = rs.Heartbeat:Connect(function() end)
local link3 = rs.Heartbeat:Connect(function() end)
local link4 = rs.Heartbeat:Connect(function() link2:Disconnect() end) -- safe to disconnect
local link5 = rs.Heartbeat:Connect(function() rs.Heartbeat:Connect(function() end) end) -- safe to connect
local link6 = rs.Heartbeat:Connect(function() end)

because connections are stored in a linked list and not in a array or dictionary its ok to disconnect or connect when a event is fired

Yet another amazing resource by sushi. Truly one of the consumables of all time.