0
\$\begingroup\$

I'm implementing a SinglyLinkedList struct that uses a private Node class in its implementation. (See this Gist.)

public struct SinglyLinkedList<Element> {
    private var head: Node<Element>?
    ...
}

extension SinglyLinkedList: MutableCollection { ... }
extension SinglyLinkedList: RangeReplaceableCollection { ... }

private class Node<Element> {
    private var value: Element
    private var next: Node?
}

In order to give my linked list value semantics, I want to give it copy on write behaviour, much like Swift's native Array, Set and Dictionary structures. So before any mutation takes place, I need to make a copy of the data in case the data is shared with another list:

extension SinglyLinkedList {
    /// Adds a new element to the front of the list.
    public mutating func prepend(_ element: Element) {
        copyIfNeeded()
        head = Node(value: element, next: head)
    }
}

The only thing left to do is to implement copyIfNeeded(). Clearly I need to use isUniquelyReferencedNonObjC for that. The naive way to do this would be to traverse the whole list and call the isUniquelyReferencedNonObjC function once for each node. However, this would make the time complexity of each mutating operation O(n), defeating the purpose of using a linked list in the first place.

Checking if head is uniquely referenced is not enough, because I made SinglyLinkedList its own subsequence, meaning that any slice of a linked list will be another linked list. The slice and the original list won't necessarily share their head nodes.

In order to be able to run copyIfNeeded() in constant time, I introduce an empty Reference class:

private class Reference {}

I also give my linked list a reference property:

public struct SinglyLinkedList<Element> {
    ...
    private var reference: Reference

    public init() {
        reference = Reference()
        ...
    }
    ...
}

This allows me to implement copyIfNeeded() like this:

extension SinglyLinkedList {
    /// - returns: `true` if a copy was made, `false` otherwise.
    @discardableResult
    private mutating func copyIfNeeded() -> Bool {
        guard !isUniquelyReferencedNonObjC(&reference) else { return false }

        var copy = SinglyLinkedList()
        // add all elements of self to copy
        self = copy
        return true
    }
}

This implementation works fine. I have verified that a copy is only made if two lists reference the same nodes, and only when one of the lists is being mutated. However, it doesn't feel right to implement an empty class that I only use for its reference count.

Are there any alternatives to this approach?

\$\endgroup\$
  • \$\begingroup\$ I think you have to add more code (as your edit makes apparent). Without seeing what operations are done with the list and how it is difficult to judge if your solution is good, or if there are better alternatives. I tried to answer the question based on the initially given information and that answer is useless now. You should include all relevant code in the question to make it self-contained. \$\endgroup\$ – Martin R Jun 27 '16 at 13:41
  • \$\begingroup\$ @MartinR Sorry for the inconvenience. I chose not to make the question self-contained at first, because it takes a lot of code to do that and not all of the code seemed directly relevant to this question. I tried to reduce it to a bare minimum here: gist.github.com/timvermeulen/b0f234fb39ed40bf21822f0bb42ccd14 \$\endgroup\$ – Tim Vermeulen Jun 27 '16 at 18:08
  • \$\begingroup\$ No problem, but your posted code is a bit misleading. You give an example where prepend makes a copy if needed. But actually (if I understand it correctly) two lists can share a common tail, and copying is required only in append. – Anyway, it seems to me that my suggestion still works, only that you check if the tail (_endIndex.node) is uniquely referenced. \$\endgroup\$ – Martin R Jun 27 '16 at 18:44
  • \$\begingroup\$ @MartinR I agree that the original code is misleading, but I just took prepend as an example of a mutating function because I hadn't introduced _endIndex yet... Oh well. For some reason, if I check whether _endIndex.node is uniquely referenced, the function always returns false (even if I don't introduce a second list in the first place). Have you tried it? I can't figure out where the second reference is coming from. \$\endgroup\$ – Tim Vermeulen Jun 27 '16 at 23:04
  • \$\begingroup\$ You are right, far too many copies are made. (I have only verified that the resulting lists are correct.) One problem is that the append in copyIfNeeded calls copyIfNeeded again. The weak references from the indexes might also be a problem. ... I'm giving up for now! \$\endgroup\$ – Martin R Jun 27 '16 at 23:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.