# The Better Way To Remove a Value From a Table?

• A long time ago before the Roblox forums were removed, I asked a question about what `table.remove` does when removing a value from a table. What was responded with was that that blank would be filled in. For example:

``````local Table = {1, 2, 3}
table.remove(Table, 2)
``````

Instead of becoming `1, nil, 3` it would bump up the `3`, or `1, 3`. (Something like this, anyways.)

Now here comes the question. Because it does this, is it better to go from the end of the table to the beginning?

``````local Table = {1, 2, 3}
for i = #Table, 1, -1 do
if Table[i] == 2 then
table.remove(Table, i)
end
end
``````

Or from start to end?

``````local Table = {1, 2, 3}
for i = 1, #Table do
if Table[i] == 2 then
table.remove(Table, i)
end
end
``````

• It does not matter at all.

• @kingdom5 Wdym?

• @TheAlphaStigma What kingdom mean is that either way it will require a linear traversal of the table, which you should avoid if possible.

Consider using a different data structure, like a set. But of course if that's not possible or if your collection is going to contain few elements then a linear traversal is fine.

A linear traversal has a worst case time complexity of `O(n)`, where `n` is your input size; the length of your list. In other words in the worst case scenario -- that is if the value you are searching for is located at the end of your list -- then it will take exactly `n` steps.

A linear complexity `O(n)` means the amount of steps is directly tied to the input size, which consequently means that for larger and larger lists it will take more time and more time.

I mentioned using a different data structure earlier. Specifically sets. A set data structure is a collection that provides insertion, removal, and membership test operations in constant time complexity `O(1)`, but it has no notion of ordering*, and does not allow duplicate elements*. While sets have no notion of ordering, it is still possible to iterate through their elements. However the order these elements are browsed in is unspecified.

Constant time complexity `O(1)`, quickly followed by logarithmic time complexity `O(log(n))`, are the best you can hope to achieve, while factorial `O(n!)` and exponential `O(k^n)` (where `k` is some constant) are the worst time complexity you can achieve.

* : depending on the implementation.

• @Link150 Just to make sure, is this what kingdom5 and you are talking about?

• @TheAlphaStigma Yes, that is an implementation of a set.

• @Link150 Nice. I'll study more on it. • A set in Lua will, for the most part, have an `O(1)` time complexity for membership tests. A membership test such as

``````function Set:Contains(x)
return self.Set[x] == true
end
``````

will work for many values `(1, "Hello world!", math.pi)`, but not for all.

Say you have some class `Vector1`, not too exciting but it's excellent for this example

``````local Vector1 = {}
Vector1.__index = Vector1
Vector1.new = function(X)
return setmetatable({X = X}, Vector1)
end
function Vector1:__eq(Other)
return self.X == Other.X
end
``````

Now, we know that these hold true

``````local v0 = Vector1.new(9)
local v1 = Vector1.new(9)
print(v0 == v1) --true
``````

and these hold false

``````local v0 = Vector1.new(9)
local v1 = Vector1.new(7)
print(v0 == v1) --false
``````

since `Vector1.new(9) == Vector1.new(9)` is true, that means if we were to put it into a set, it should be a member, correct?

``````Set:Add(Vector1.new(9))
print(Set:Contains(Vector1.new(9))) --false
``````

But our naive set says that, no, `Vector1.new(9)` isn't a member of this set because while `Vector1.new(9) == Vector1.new(9)`, they aren't the same objects. If you want a set that works for objects such as our `Vector1` here, we can do a linear search for them.

``````function Set:Contains(X)
local Contains = self.Set[X]
if Contains then
return Contains
end
for Key in pairs(self.Set) do
if Key == X then
return true
end
end
end
``````

It depends on what you consider equal or what you consider different.

• @LegitimatlyMe That ruins the whole point of sets. If the value is not present then your `set:Contains(x)` method will perform an unsuccessful linear search for it anyway.

There's a better solution: hashes. Compute a hash of your set elements and use that as the key. Two vectors that compare equal should return the same hash.

Any value that is to be able to be added to a set should define a `hash()` method. Primitive types can be hashed by some global `hash()` function. This function should just fallback to the `hash()` method of its argument for complex objects.

Looks like your connection to Scripting Helpers was lost, please wait while we try to reconnect.