This package provides a few implementations of doubly-linked lists in Julia:
DoublyLinkedList, a doubly-linked list with mutable nodes.PairedLinkedList, a doubly-linked list with mutable nodes which also contain a third link to a node in anotherPairedLinkedList.TargetedLinkedList, a doubly-linked list with mutable nodes which also contain a third link to a node in another list, which can be aDoublyLinkedList,PairedLinkedList, or aTargetedLinkedList.
The lists support many of the base methods for arrays:
julia> using PairedLinkedLists
julia> l = DoublyLinkedList{Int}();
julia> push!(l, 1:10...)
DoublyLinkedList{Int64}(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
julia> pushfirst!(l, 0)
DoublyLinkedList{Int64}(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
julia> pop!(l); l
DoublyLinkedList{Int64}(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
julia> popfirst!(l); l
DoublyLinkedList{Int64}(1, 2, 3, 4, 5, 6, 7, 8, 9)
julia> popat!(l, 5); l
DoublyLinkedList{Int64}(1, 2, 3, 4, 6, 7, 8, 9)
julia> insert!(l, 5, -1)
DoublyLinkedList{Int64}(1, 2, 3, 4, -1, 6, 7, 8, 9)List nodes, rather than the data they contain, can be accessed via getnode(). Each node contains data as well as references to the previous and next nodes:
julia> using PairedLinkedLists;
julia> l = DoublyLinkedList{Int}(1:5...)
DoublyLinkedList{Int64}(1, 2, 3, 4, 5)
julia> node = getnode(l,3)
ListNode{Int64, DoublyLinkedList{Int64}}(3)
julia> node.next
ListNode{Int64, DoublyLinkedList{Int64}}(4)
julia> node.prev.data == 2
trueIterating a list returns the data it contains, but nodes can be accessed during iteration by using IteratingListNodes:
julia> for data in l println(data) end
1
2
3
4
5
julia> for node in IteratingListNodes(l) println(node) end
ListNode{Int64, DoublyLinkedList{Int64}}(1)
ListNode{Int64, DoublyLinkedList{Int64}}(2)
ListNode{Int64, DoublyLinkedList{Int64}}(3)
ListNode{Int64, DoublyLinkedList{Int64}}(4)
ListNode{Int64, DoublyLinkedList{Int64}}(5)Skip lists insert new data as appropriate to keep the list sorted, with O(log(n)) insertion and deletion times:
julia> using PairedLinkedLists
julia> sortedby = x -> (-x[2], x[1])
#5 (generic function with 1 method)
julia> data = [(x,y) for x in 1:2 for y in 1:2];
julia> sl = SkipList{eltype(data)}(data...) # using default sorting
SkipList{Tuple{Int64, Int64}, typeof(identity)}((1, 1), (1, 2), (2, 1), (2, 2))
julia> sl2 = SkipList{eltype(data)}(data...; sortedby=sortedby)
SkipList{Tuple{Int64, Int64}, var"#5#6"}((1, 2), (2, 2), (1, 1), (2, 1))
julia> push!(sl, (0,0))
SkipList{Tuple{Int64, Int64}, typeof(identity)}((0, 0), (1, 1), (1, 2), (2, 1), (2, 2))
julia> push!(sl2, (0,0))
SkipList{Tuple{Int64, Int64}, var"#5#6"}((1, 2), (2, 2), (1, 1), (2, 1), (0, 0))