GitHub

PairedLinkedLists

This package provides doubly-linked list and sorted skip-list implementations in Julia, with support for reciprocal inter-list node links.

List types:

  • DoublyLinkedList — a standard doubly-linked list.
  • PairedLinkedList — a doubly-linked list whose nodes each carry a reciprocal link to a node in a second PairedLinkedList. Adding a link from node A to node B automatically sets the reverse link from B to A.
  • TargetedLinkedList — a doubly-linked list whose nodes carry a one-way link to a node in any other list type.
  • SkipList — a sorted skip list with O(log n) insertion and deletion.
  • PairedSkipList — a sorted skip list whose nodes carry reciprocal inter-list links.

Installation

using Pkg
Pkg.add("PairedLinkedLists")

Inter-list linking

The distinctive feature of this package is the ability to link nodes across two lists. A paired link is reciprocal: addtarget!(node_a, node_b) sets node_a.target = node_b and node_b.target = node_a in a single call, and removetarget! clears both ends. A targeted link is one-way: only the source node's target field is set, leaving the destination unchanged.

Linking works at both the list level (pairing two lists together so their nodes can be linked) and the node level (pairing individual nodes within already-paired lists).

Usage

Basic list operations

julia> l = DoublyLinkedList{Int}(1, 2, 3, 4, 5);

julia> push!(l, 6)
DoublyLinkedList{Int64}(1, 2, 3, 4, 5, 6)

julia> pop!(l)
6

julia> popat!(l, 2)
2

julia> insert!(l, 2, 10)
DoublyLinkedList{Int64}(1, 10, 3, 4, 5)

julia> collect(l)
5-element Vector{Int64}:
  1
 10
  3
  4
  5

Node access and iteration

getnode returns the node at a given index. Nodes hold data and prev/next references. ListNodeIterator iterates over nodes rather than data values:

julia> l = DoublyLinkedList{Int}(10, 20, 30);

julia> node = getnode(l, 2)
ListNode{Int64, DoublyLinkedList{Int64}}(20)

julia> node.prev.data
10

julia> node.next.data
30

julia> [n.data for n in ListNodeIterator(l)]
3-element Vector{Int64}:
 10
 20
 30

julia> [n.data for n in ListNodeIterator(l; rev=true)]
3-element Vector{Int64}:
 30
 20
 10

Inter-list linking with PairedLinkedList

julia> l1 = PairedLinkedList{Int}(1, 2, 3);

julia> l2 = PairedLinkedList{Int}(10, 20, 30);

julia> addtarget!(l1, l2);

julia> l1.target === l2
true

julia> addtarget!(getnode(l1, 1), getnode(l2, 2));

julia> getnode(l1, 1).target.data
20

julia> getnode(l2, 2).target.data
1

julia> removetarget!(getnode(l1, 1));

julia> hastarget(getnode(l1, 1))
false

julia> hastarget(getnode(l2, 2))
false

Sorted skip lists

SkipList keeps elements in sorted order and supports O(log n) insertion and deletion. A custom sort key can be supplied via the sortedby keyword:

julia> sl = SkipList{Int}(5, 3, 1, 4, 2);

julia> collect(sl)
5-element Vector{Int64}:
 1
 2
 3
 4
 5

julia> push!(sl, 0); collect(sl)
6-element Vector{Int64}:
 0
 1
 2
 3
 4
 5

julia> negate(x) = -x;

julia> sl2 = SkipList{Int}(5, 3, 1, 4, 2; sortedby=negate);

julia> collect(sl2)
5-element Vector{Int64}:
 5
 4
 3
 2
 1

API Reference

PairedLinkedLists.DoublyLinkedList — Type
l = DoublyLinkedList{::Type}()
l = DoublyLinkedList(elts...)

Create a DoublyLinkedList made up of ListNodes with nodes containing data of a specified type.

The list contains its length len, a "dummy" node head at the beginning of the list, and a "dummy" node tail at the end of the list.

The first "real" node of a list l can be accessed with l.head.next or head(l). Similarly, the last "real" node can be accessed with l.tail.prev or tail(l).

See also ListNode, SkipList, PairedLinkedList, TargetedLinkedList

source
PairedLinkedLists.ListDataIterator — Type
ListDataIterator(start; rev=false)
ListDataIterator(start, stop; rev=false)

Return an iterator over the data values of a linked list, beginning at node start.

If stop is provided, iteration halts when that node is reached (the stop node itself is not yielded). start and stop must belong to the same list.

If rev is true, the iterator advances toward the head of the list; otherwise it advances toward the tail.

source
PairedLinkedLists.ListDataIterator — Method
ListDataIterator(list; rev=false)

Return an iterator over the data values of a linked list.

If rev is true, the iterator starts at the tail and advances toward the head; otherwise it starts at the head and advances toward the tail.

source
PairedLinkedLists.ListNodeIterator — Type
ListNodeIterator(start; rev=false)
ListNodeIterator(start, stop; rev=false)

Return an iterator over the nodes of a linked list, beginning at node start.

If stop is provided, iteration halts when that node is reached (the stop node itself is not yielded). start and stop must belong to the same list.

If rev is true, the iterator advances toward the head of the list; otherwise it advances toward the tail.

source
PairedLinkedLists.ListNodeIterator — Method
ListNodeIterator(list; rev=false)

Return an iterator over the nodes of a linked list.

If rev is true, the iterator starts at the tail and advances toward the head; otherwise it starts at the head and advances toward the tail.

Examples

julia> l = DoublyLinkedList{Int}(1, 2, 3, 4, 5);

julia> [node.data for node in ListNodeIterator(l)]
5-element Vector{Int64}:
 1
 2
 3
 4
 5

julia> [node.data for node in ListNodeIterator(l; rev=true)]
5-element Vector{Int64}:
 5
 4
 3
 2
 1

julia> [node.data for node in ListNodeIterator(getnode(l, 2), getnode(l, 4))]
2-element Vector{Int64}:
 2
 3
source
PairedLinkedLists.PairedLinkedList — Type
l = PairedLinkedList{::Type}()
l = PairedLinkedList{::Type}(elts...)

Create a PairedLinkedList made up of PairedListNodes containing data of a specified type. Each node can have an inter-list link to a node belonging to the list's target.

The list contains its length len, a "dummy" node head at the beginning of the list, and a "dummy" node tail at the end of the list.

The first "real" node of a list l can be accessed with l.head.next or head(l). Similarly, the last "real" node can be accessed with l.tail.prev or tail(l).

See also PairedListNode, PairedSkipList, DoublyLinkedList, TargetedLinkedList

Examples

julia> l1 = PairedLinkedList{Int}(1, 2, 3);

julia> l2 = PairedLinkedList{Int}(10, 20, 30);

julia> addtarget!(l1, l2);

julia> l1.target === l2
true

julia> l2.target === l1
true
source
PairedLinkedLists.PairedListNode — Type
node = PairedListNode(list::PairedLinkedList, data)

Create a PairedListNode belonging to the specified list. The node contains a reference list to the parent list and contains the provided data, but it has no specific insertion point into list (see insertafter!).

node.prev and node.next represent the previous and next nodes, respectively, of a list.

A node's target should always either be a reference to itself (denoting an unpaired node) or a node belonging to the target of its parent list.

The target link is assumed to be reciprocated for a PairedListNode. For example, node === node.target.target should be true. For one-way inter-list links, see TargetedListNode.

See also PairedLinkedList, ListNode, TargetedListNode.

source
PairedLinkedLists.PairedSkipList — Type
l = PairedSkipList{::Type}(; sortedby=identity, skipfactor=2)
l = PairedSkipList{::Type}(elts...; sortedby=identity, skipfactor=2)

Create a PairedSkipList with nodes containing data of a specified type. Each node can have an inter-list link to a node belonging to the list's target.

The list contains its length len, a "dummy" node head at the beginning of the list, and a "dummy" node tail at the end of the list. The list also contains a reference to its "target" list.

The first "real" node of a list l can be accessed with l.head.next or head(l). Similarly, the last "real" node can be accessed with l.tail.prev or tail(l).

The skipfactor controls the average branching ratio between levels (default: 2). The sortedby function determines the sort key applied to each element (default: identity).

See also SkipList, PairedSkipNode

source
PairedLinkedLists.PairedSkipNode — Type
node = PairedSkipNode(list::PairedSkipList [, data])

Create a PairedSkipNode belonging to the specified list. The node contains a reference list to the parent skip list and contains the provided data, but it has no specific insertion point into list (see insertafter!).

node.prev and node.next represent the previous and next nodes, respectively, of a list. node.up and node.down represent the nodes in adjacent levels within the skip list data structure.

A node's target should always either be a reference to itself (denoting unpaired node) or a node belonging to the target of its parent list.

The target link is assumed to be reciprocated for a PairedSkipNode. For example, node === node.target.target should be true.

See also PairedSkipList, SkipNode

source
PairedLinkedLists.SkipList — Type
l = SkipList{::Type}(; sortedby=identity, skipfactor=2)
l = SkipList{::Type}(elts...; sortedby=identity, skipfactor=2)

Create a SkipList made up of SkipNodes containing data of a specified type.

The list contains a "dummy" node head at the beginning of the list and a "dummy" node tail at the end of the list.

The node at the head of the topmost level of the datastructure can be accessed by l.top.

The first "real" node of a list l can be accessed with l.head.next or head(l). Similarly, the last "real" node can be accessed with l.tail.prev or tail(l).

The skipfactor controls the average branching ratio between levels (default: 2). The sortedby function determines the sort key applied to each element (default: identity).

See also PairedSkipList, SkipNode

Examples

julia> l = SkipList{Int}(3, 1, 4, 1, 5, 9);

julia> collect(l)
6-element Vector{Int64}:
 1
 1
 3
 4
 5
 9
source
PairedLinkedLists.SkipNode — Type
node = SkipNode(list::SkipList [, data])

Create a SkipNode belonging to the specified list. The node contains a reference list to the parent skip list and contains the provided data, but it has no specific insertion point into list (see insertafter!).

node.prev and node.next represent the previous and next nodes, respectively, of a list. node.up and node.down represent the nodes in adjacent levels within the skip list data structure.

See also SkipList, PairedSkipNode

source
PairedLinkedLists.TargetKind — Type
TargetKind

Trait describing how a node or list participates in cross-list target links — the defining feature of this package. The kinds are Reciprocal (two-way links), OneWay (one-way links), and Untargeted (no links). TargetKind(x) reports the kind for a node or list x, and hastarget, addtarget!, and removetarget! dispatch on it.

A type opts into targeting by defining TargetKind(::Type{MyType}) to return Reciprocal() or OneWay() and providing a target field initialized to the object itself; pointing target at the object encodes the unlinked state.

See also target, hastarget, addtarget!, removetarget!.

source
PairedLinkedLists.TargetedLinkedList — Type
l = TargetedLinkedList{T,R}()
l = TargetedLinkedList{T,R}(elts...)
l = TargetedLinkedList(list)

Create a TargetedLinkedList made up of TargetedListNodes containing data of a specified type. Each node can have an inter-list link to a node belonging to the list's target.

The list contains its length len, a "dummy" node head at the beginning of the list, and a "dummy" node tail at the end of the list. The list also contains a reference to its "target" list.

The first "real" node of a list l can be accessed with l.head.next or head(l). Similarly, the last "real" node can be accessed with l.tail.prev or tail(l).

See also TargetedListNode, DoublyLinkedList, PairedLinkedList

Examples

julia> base = DoublyLinkedList{Int}(1, 2, 3);

julia> tl = TargetedLinkedList(base)
TargetedLinkedList{Int64, DoublyLinkedList{Int64}, ListNode{Int64, DoublyLinkedList{Int64}}}()

julia> push!(tl, 10); push!(tl, 20); push!(tl, 30);

julia> collect(tl)
3-element Vector{Int64}:
 10
 20
 30

julia> addtarget!(getnode(tl, 1), getnode(base, 2));

julia> getnode(tl, 1).target.data
2
source
PairedLinkedLists.TargetedListNode — Type
node = TargetedListNode(list::AbstractTargetedLinkedList, data, [target::AbstractListNode])

Create a TargetedListNode belonging to the specified list. The node contains a reference list to the parent list and contains the provided data, but it has no specific insertion point into list (see insertafter!).

node.prev and node.next represent the previous and next nodes, respectively, of a list.

A node's target should always either be a reference to itself (denoting an unpaired node) or a node belonging to the target of its parent list.

The target link is not assumed to be reciprocated for a TargetedListNode, as the targeted node may not even have a target field. For guaranteed two-way inter-list links, see PairedListNode.

See also TargetedLinkedList, PairedListNode, ListNode.

source
Base.map — Method
map(f, l::DoublyLinkedList)

Apply f to each element of l, returning a new DoublyLinkedList.

map is defined only for DoublyLinkedList. It is intentionally not provided for the other list types: an arbitrary f need not preserve a SkipList's sortedby ordering, and mapping a PairedLinkedList or TargetedLinkedList would leave the new list's nodes without the cross-list target links that define those types. Build such a list explicitly instead.

source
Base.popat! — Method
popat!(l::AbstractList, idx::Int) -> data
popat!(l::AbstractList, idx::Int, default) -> data_or_default

Remove and return the element at index idx of l. Throws BoundsError if idx is out of range.

The two-argument form is the same as Base.popat!. The three-argument form returns default instead of throwing when idx is out of range; no element is removed in that case.

source
PairedLinkedLists.addtarget! — Method
addtarget!(node, target_node)
addtarget!(list, target_list)

Link the provided node or list to target, assigning it as the object's target, and return the object.

For a Reciprocal object (such as a PairedListNode or PairedLinkedList) the reverse link is established as well, and any prior target of either object is removed first. For a OneWay object (such as a TargetedListNode or TargetedLinkedList) only the object's own link is set and target is left unchanged.

Examples

julia> l1 = PairedLinkedList{Int}(1, 2, 3);

julia> l2 = PairedLinkedList{Int}(10, 20, 30);

julia> addtarget!(l1, l2);

julia> hastarget(l1)
true

julia> l1.target === l2
true

julia> addtarget!(getnode(l1, 1), getnode(l2, 2));

julia> getnode(l1, 1).target.data
20

julia> getnode(l2, 2).target.data
1

See also TargetKind, hastarget, removetarget!.

source
PairedLinkedLists.athead — Method
athead(node) -> Bool

Return true if the node is the "dummy" sentinel at the beginning of the list, and false otherwise.

source
PairedLinkedLists.attail — Method
attail(node) -> Bool

Return true if the node is the "dummy" sentinel at the end of the list, and false otherwise.

source
PairedLinkedLists.copyfromcache — Method
copyfromcache(c::SkipListCache)

Returns a skip list created from a SkipListCache. This adds and removes entries as speficied by the cache.

source
PairedLinkedLists.copyfromcache — Method
copyfromcache(l::AbstractSkipLinkedList)

Returns a copy of a skip list created from its cache. This adds and removes entries in the same order as had been previously done in original list.

source
PairedLinkedLists.deletenode! — Method
deletenode!(node::SkipNode)

Remove node from the list to which it belongs, update the list's length, and return the node.

The node can be at any level of the skip list, and all nodes directly above or below will also be removed.

source
PairedLinkedLists.head — Method
node = head(list)

Return the first real node in list. This is list.head.next, not list.head itself, which is a dummy sentinel.

Throws ArgumentError if the list is empty.

source
PairedLinkedLists.insertafter! — Method
insertafter!(node, prev)

Insert node into a list after the preceding node prev, update the list's length, and return the node.

node and prev must belong to the same list.

source
PairedLinkedLists.insertbefore! — Method
insertbefore!(node, next)

Insert node into a list before the subsequent node next, update the list's length, and return the node.

node and next must belong to the same list.

source
PairedLinkedLists.listtype — Method
t = listtype(::AbstractNode)
t = listtype(::Type{<:AbstractNode})

Return the type of list that can contain the provided type of node.

source
PairedLinkedLists.removetarget! — Method
removetarget!(node) -> node
removetarget!(list) -> list
removetarget!(list, idx::Int) -> node

Remove the target link of the node or list (or of the idx-th node of list) and return the object whose link was removed. An object without a target is returned unchanged.

For a Reciprocal object the reverse link is removed as well. Removing a list's target also removes the target link of each of its nodes.

Note

removetarget!(list) removes both the list-level link and all node-level target links within that list.

See also TargetKind, hastarget, addtarget!.

source
PairedLinkedLists.skiplistsidentical — Method
skiplistsidentical(l1::AbstractSkipLinkedList, l2::AbstractSkipLinkedList)

Returns true if the two skip lists are identical, false otherwise.

The lists are considered identical if the values of their nodes are the same at each "level" of the list. Because nodes are typically added at a random level, two skip lists constructed from the same data will generally not be identical unless generated using copyfromcache.

See also copyfromcache

source
PairedLinkedLists.tail — Method
node = tail(list)

Return the last real node in list. This is list.tail.prev, not list.tail itself, which is a dummy sentinel.

Throws ArgumentError if the list is empty.

source
PairedLinkedLists.target — Method
target(node) -> node_or_nothing
target(list) -> list_or_nothing

Return the target of node or list, or nothing if no target is currently linked. For Reciprocal objects (PairedListNode, PairedSkipNode, PairedLinkedList, PairedSkipList) the link is bidirectional; for OneWay objects (TargetedListNode, TargetedLinkedList) it is one-directional. Untargeted objects always return nothing.

This is the public accessor for the cross-list link; callers should use it rather than reading the .target field directly, as the unlinked state is encoded by a self-reference which target hides.

See also TargetKind, hastarget, addtarget!, removetarget!.

source