Add features to LinkedList

[oxinabox]

When looking at #442 I noticed just how featureless our LinkedList is. In particular, as pointed out by #442 we have no mutating operations.

I think adding some of the missing methods would be great for someone new to julia. Since implementing a linked list is like DataStructures101.

Here is a list of functions I think should be implemented. Feel free to suggest more.

• [ ] getindex
• [ ] setindex!
• [ ] delete! with overloads both for single indexes and for ranges.
• [ ] append!
• [ ] The iterator traits (or are the defaults right?)

[c-p-murphy]

I think the best option might be to make the current LinkedList immutable and move it to something like FunctionalList and then rewrite a new mutable LinkedList from scratch. With the current functional implementation, there isn't really a good way to make things mutable without changing a lot of code (as far as I can see).

I put this together as a potential starting point (and as an exercise to practice some more julia). If anyone has any advice about improvements and/or style changes, feel free to let me know.

[oxinabox]

Making the current LinkedList immutable is a breaking change.

[c-p-murphy]

Making the current LinkedList immutable is a breaking change.

That's why I also suggested changing the name. I guess there might also need to be a few more changes to accommodate them both in the same package.

I might be wrong, but as far as I can see, with the existing implementation, there isn't really a good way to take advantage of the mutability. If so, then it's probably unlikely that many people are relying on it being mutable, right?

Either way though, the new LinkedList would be mutable. This is what I was suggesting as a possible starting point: https://github.com/c-p-murphy/List.jl/blob/master/src/linkedlist.jl

[c-p-murphy]

I guess this works with the existing implementation:

function setindex!(l::LinkedList{T}, value::T, idx::Int) where T
    0 < idx <= length(l) || throw(ArgumentError("Index out of bounds"))
    node = l
    for i = 1:idx-1
        node = node.tail
    end
    node.head = value
    return l
end

It's kind of slow with the length(l) though.

Is the concern about changing things that people may have built stuff on top of LinkedList that depends on the particulars of the existing implementation? Or is it that breaking changes are discouraged now that v1.0 is out? Or both/neither?

[c-p-murphy]

There also seems to be an issue with the current implementation when trying to delete the first element of a list (it's not a problem for any other element). For example:

function tail!(l::LinkedList)
    l = l.tail
    return l
end

julia> l = list(1:10...)
list(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

julia> tail!(l)
list(2, 3, 4, 5, 6, 7, 8, 9, 10)

julia> l
list(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

I assume this has something to do with the different scopes, but I'm not sure how to work around it (or if there is a way to do so).

[eulerkochy]

Hey all! I was just considering to add the functionality of reverse traversal to LinkedList. It's not absolutely necessary, but its presence won't hurt also. What do you guys think about that?

[HazilMohamed]

I assume this has something to do with the different scopes, but I'm not sure how to work around it

I don't think there is a way to do so, the only way (that I found) is to re assign to another variable.

function tail!(l::LinkedList)
    l = l.tail
    return l
end

julia> l = list(1:10...)
list(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

julia>l = tail!(l)
list(2, 3, 4, 5, 6, 7, 8, 9, 10)

julia> l
list(2, 3, 4, 5, 6, 7, 8, 9, 10)

[BeastyBlacksmith]

Is there still something left to do or can this be closed after #450?