Doubly linked list

This is an implementation of the classic two-linked list in lua.

Example

local dl = DoublyLinkedList()
dl = DoublyLinkedList({1,2,3,4}) --> [1, 2, 3, 4]
dl:popf() --> 1, [2, 3, 4]
dl:pushf(1.5) --> [1.5, 2, 3, 4]
dl:popl() --> 4, [1.5, 2, 3]
dl:push(2, 6) --> [1.5, 2, 6, 3]
dl:sort() --> [1.5, 2, 3, 6]
print(dl[4]) --> 6
dl[1] = 1 --> [1, 2, 3, 6]
for i, v in dl:iter() do
  print(i,v) --> (1, 1), (2, 2), (3, 3), (4, 6)
end
dl:clear() --> []

API

object:pushf(item)

Short for push first. Adds an item to the top of the list. Analogue - object:push(0)

object:pushl(item)

Short for push last. Adds the item to the end of the list. Analogue - object:push(#object) or object:push(-1)

object:push(int index, item)

Adds an item after the given index. If the index is set after the maximum or minimum item, it adds from the edge. Negative indexing is supported, where -1 means the last item.

object:popf() --> item or nil

Short for pop first. Returns the first item or nil. Analogue - object:pop(1)

object:popl() --> item or nil

Short for pop last. Returns the last item or nil. Analogue - object:pop(#object) or object:pop(-1)

object:pop(int index) --> item or nil

Removes and returns an item by index. If the index is set after the maximum or minimum item, it returns nil. Negative indexing is supported, where -1 means the last item.

object:clear()

Deletes all items in the list.

object:clone() --> new object

Creates and returns a copy of the list.

object:iter(boolean isReversed) --> function

This is an iterator that is used instead of pairs()

object:reverse() --> object

Reverses the order of the list items.

object:sort(function compire)

Sorts the list. By default, compire = function(a, b) return a < b end

object[int index] --> item or nil

Returns an item or nil by index. Negative indexing is supported, where -1 means the last item.

object[int index] = item

Replace an item by an index, if such an index exists.

Performance analysis

All tests will be conducted on a computer with a Ryzen 5 3500U processor, which will be limited to a maximum frequency of 1.66 gigahertz.

We will compare by the following categories: create, insert, delete, copy and sort, and we will compare with the standard lua table.

Note that inserting and deleting at the beginning is the best O(1) for a list, but the worst O(N) for an array. Inserting and deleting at the end is the best O(1) for an array and the best O(1) for a list. Both insertion and deletion in the middle is the worst O(N/2) for a list and the average O(N/2) for an array.

Added a python list and a node array at the request of a friend.

Create

We will create items from 1 -> Count item

To insert at the beginning

dl:pushf(value)

table.insert(tbl, 1, value)

arr.unshift(value)

li.insert(0, value)

To insert in the middle

dl:push(math.floor(i/2), value)

table.insert(tbl, math.ceil(i/2), value)

arr.splice(Math.floor(i/2), 0, value)

li.insert(math.floor(i/2), value)

To insert at the end

dl:pushl(value)

table.insert(tbl, value)

arr.push(value)

li.append(value)

Insert

We will expand the list by 10%. For 1000 items it is +100, for 10_000 it is + 1000.

To insert at the beginning To insert in the middle To insert at the end

Delete

We will delete 10% of the list size. That is, from 1000 to 900 or from 10_000 to 9_000.

To remove from the beginning

dl:popf()

table.remove(tbl, 1)

arr.shift()

li.pop(0)

To remove from the middle

dl:pop(math.floor(#dl/2))

table.remove(tbl, math.floor(#tbl/2))

arr.splice(Math.floor(arr.lenght/2), 1)

li.pop(math.floor(len(li)/2))

To remove from the end

dl:popl()

table.remove(tbl)

arr.pop()

li.pop()

Сopy

We will create a copy of the list of different sizes.

local new_list = dl:clone()

local new_table = {}
for i = 1, #tbl do new_table[i] = tbl[i] end

let newArray = arr.slice()

new_list = list(li)

Sort

We will sort the following types of data: ordered, inversely ordered, randomly ordered.

dl:sort()

table.sort(tbl)

arr.sort()

li.sort()

For ordered For inversely ordered For randomly ordered

Conclusions

Only Lua

As you can see, up to 1000 items can be used lua table without problems. In the future, try to avoid inserting at the beginning of the table. A two-linked list is inferior to a table in many ways, this is due to the fact that working with the table is implemented at the C++ level. And as for an algorithm that works in an interpreted language, the result is pretty good. A good practical application would be a case where you need to delete and add items from two edges of the list, for example, a queue.

Total

It's funny that each of their structures: this list, lua table, python list, node array wins in one of the situations.