circularlist.jl's Introduction

CircularList

Installation

]add CircularList

Features

It is essentially a doubly linked list.

Adding a new node is O(1)
Delete an existing node is O(1)
Ability to handle millions of nodes

How to use?

To construct a circular list, you must start with at least 1 datum element.

h = circularlist(0)      # CircularList.List(0)
h = circularlist([1,2])  # CircularList.List(1,2)

When inserting new data, the new node becomes the head.

h = circularlist(0)      # CircularList.List(0)
insert!(h, 1)            # CircularList.List(1,0)
insert!(h, 2)            # CircularList.List(2,0,1)
insert!(h, 3)            # CircularList.List(3,0,1,2)

When deleting the current node, the previous node becomes the head:

delete!(h)               # CircularList.List(2,0,1)

You can move the head pointer in any direction:

forward!(h)              # CircularList.List(0,1,2)
backward!(h)             # CircularList.List(2,0,1)
shift!(h, 2, :forward)   # CircularList.List(1,2,0)
shift!(h, 2, :backward)  # CircularList.List(2,0,1)

Or, if you have a reference to a specific node, you can jump to that node directly and that node becomes the head!

jump!(h, node)

You can get the current head and tail node as follows:

head(h)                  # CircularList.Node(2)
tail(h)                  # CircularList.Node(1)

You can peek at the data of current, previous, or next nodes:

current(h)               # 2
previous(h)              # 1
next(h)                  # 0

Most methods returns CircularList.List so they are highly chainable:

julia> using Lazy

julia> @> h = circularlist(0) insert!(1) insert!(2) insert!(3) forward!
CircularList.List(0,1,2,3)

It is iteration friendly:

[x for x in h]           # Int[2,0,1]
sum(x for x in h)        # 3

How does it perform?

Ingestion is fairly linear.

julia> @btime addmany(1000);
  24.908 μs (1003 allocations: 54.97 KiB)

julia> @btime addmany(10000);
  255.348 μs (10004 allocations: 547.11 KiB)

julia> @btime addmany(100000);
  2.852 ms (100004 allocations: 5.34 MiB)

julia> @btime addmany(1000000);
  31.802 ms (1000004 allocations: 53.41 MiB)

Recommend Projects