Linked list

General Usage
1

Is there a package for linked and/or double linked lists?

I only found https://github.com/adolgert/Lists.jl which doesn’t seem to be maintained anymore and isn’t available via Pkg.add(). Vectors are just arrays so deleting from the middle of a vector is slow, right?

1 Like
2

Look at DataStructures.jl

I’m pretty sure it has both.

3

I updated Lists.jl awhile ago to make this:

(it was a PR to fix, update, and “conciseify” but it wasn’t looked at for months so it became a fork, but it all worked so I just registered it).

Don’t assume that.

2 Likes
4

Looks like they have only a normal linked list

http://datastructuresjl.readthedocs.io/en/latest/linked_list.html

And the documentation is quite meager in my opinion.

1 Like
5

Haha ok thanks. Wasn’t able to find that one.

6

I may be wrong on its having a doubly linked list. Nevertheless this package has many very useful classic data structures implemented efficiently. It definitely has a linked list. Documentation here: DataStructures.jl docs

7

I don’t understand this video. Stroustrup compares two algorithms with O(n) operations (linked lists, where search is linear, vs arrays, where insertion/deletion is linear) for repeatedly inserting/deleting in a sorted list, poses a silly question (“For what n is a linked list better?” …which makes no sense because there is no reason to think one algorithm would ever “overtake” the other), and gets the obvious answer (the “constant” factors for arrays are much better, hence they win for all n).

To (eventually) beat arrays, which always have great constant factors (because of their spatial locality, simplicity, and lack of pointer-chasing), you need to have a data structure that has better asymptotic complexity for your problem. For the problem he poses, of maintaining a sorted list, this would be something like a red-black tree.

For ordinary linked lists (single or double) to beat arrays, you need to have a problem that requires repeated insertion/deletion in the middle of the list, but which requires no linear-time searching (i.e. where you have a pointer to the necessary list element already for some reason).

1 Like
8

Yes, there are issues with the video and they are discussed in the comments. But I just wanted to point to the fact that insertion is not always better with a linked list, which is what the OPs question actually was.

I wouldn’t have fixed up the library if they were actually worthless.

9

We used to use a function called swapnpop! that might be helpful if the order of the elements doesn’t matter: basically, to delete an element from a vector by its position, you simply swap it with the element at the end of the vector, and then resize the vector so that it’s now one element smaller. This gave pretty good performance.

function swapnpop!(a::AbstractArray, n::Int)
    n > length(a) && throw(BoundsError())
    a[n] = a[end]
    pop!(a)
 end

Credit for this, IIRC, goes to @CarloLucibello.

4 Likes