Category talk:Wren-llist

From Rosetta Code

Linked Lists[edit]

Many tasks on RC require the use of linked lists which are generally implemented as a chain of nodes with each node containing a pointer to the next (and in the case of a doubly-linked list a pointer to the previous) node in the chain. As is well known, linked lists can be more efficient than dynamic arrays (in which the elements are stored contiguously) in cases where a large number of insertions and/or removals are required though are less efficient when it comes to operations involving indexing.

This module therefore adds linked list support to Wren in the form of two classes, LinkedList and DLinkedList, which represent singly and doubly-linked lists respectively. Each of these has a corresponding Node or DNode class to represent the nodes themselves. The design of these classes has been guided by the following principles:

1. The user should not have to deal with the Node objects directly, just their data members. The creation of Nodes is therefore done internally and independently, which avoids problems with cycles and Node identity when the same Node objects (which are reference types in Wren) are added directly or indirectly to the linked list.

2. Even though the underlying implementations are completely different, the interface of the linked list classes should follow closely that of the built-in List class which reduces the learning curve. However, given the nature of linked lists, additional methods have been provided where needed.

3. The linked list classes should inherit from the built-in Sequence class to automatically enjoy the functionality it provides.

For various reasons (efficient indexing, smaller memory footprint, more cache friendly) dynamic arrays tend to be preferred to linked lists nowadays and it is not expected that this module will see much use outside of RC particularly as it is written entirely in Wren whereas the built-in List class is written mostly in C. Consequently, only limited effort has been made to optimize the implementation.

Source code[edit]

/* Module "llist.wren" */

/* Node is a building block for a singly linked list. As such it consists of two fields:
   a data member, which can be of any type, and a link to the next Node_ object.
*/
class Node {
    // Constructs a new Node object.
    construct new(data) {
        _data = data
        _next = null
    }

    // Public properties.
    data { _data }
    data=(d) { _data = d }

    next { _next }
    next=(n) { 
        _next = (n.type == Node || n == null) ? n : Fiber.abort("Invalid argument.")
    }

    // Private setters, no checks.
    next_=(n) { _next = n }
    prev_=(n) { _prev = n }

    // Returns the string representation of this instance.
    toString { _data.toString }
}

/* LinkedList represents a singly linked list of Node_ objects.
   The 'elements' of the list generally refer to their data members,
   not the Nodes themselves. Indexing operations support negative
   indices which count backwards from the end of the list.
*/
class LinkedList is Sequence {

    // Constructs a new, empty LinkedList object.
    construct new() {
        _count = 0
        _head = null
        _tail = null
    }

    // Constructs a new LinkedList object and adds the elements of a sequence to it.
    construct new(a) {
        _count = 0
        _head = null
        _tail = null
        addAll(a)
    }

    // Creates a new LinkedList with 'size' elements, all set to 'd'.
    static filled(size, d) {
        if (size.type != Num || !size.isInteger || size < 0) {
            Fiber.abort("Size cannot be negative.")
        }
        var ll = LinkedList.new()
        if (size == 0) return ll
        for (i in 1..size) ll.add(d)
        return ll
    }

    // Copies the current instance to a new LinkedList.
    copy() { LinkedList.new(this) }

    // Basic properties.
    head { _head ? _head.data : null }  // returns the first element
    tail { _tail ? _tail.data : null }  // returns the last element

    count { _count }                    // returns the number of elements

    // Returns whether or not the current instance is empty.
    isEmpty { _count == 0 }

    // Adds an element at the tail of the current instance and returns it.
    add(d) {
        var node = Node.new(d)
        if (!_head) {
            _head = node
            _head.next_ = null
            _count = 1
        } else {
            var n = _tail
            n.next_ = node
            node.next_ = null
            _count = _count + 1
        }
        _tail = node
       return d
    }

    // Adds a sequence of elements at the tail of the current instance and returns them.
    addAll(a) {
        if (!(a is Sequence)) Fiber.abort("Argument must be a Sequence.")
        for (e in a) add(e)
        return a
    }

    // Inserts an element at the head of the current instance and returns it.
    prepend(d) { insert_(0, d) }

    // Inserts a sequence of elements at the head of the current instance and returns them.
    prependAll(a) {
        if (!(a is Sequence)) Fiber.abort("Argument must be a Sequence.")
        var i = 0
        for (e in a) {
            insert_(i, e)
            i = i + 1
        }
        return a
    }

    // Private helper method to check whether an index is valid.
    checkIndex_(index, inc, s) {
        if (index.type != Num || !index.isInteger) Fiber.abort("%(s) must be an integer.")
        var c = _count + inc
        if (index >= c || index < -c) Fiber.abort("%(s) is out of bounds.")
    }

    // Inserts an element at a specified index of the current instance
    // and returns the inserted element.
    insert(index, d) {
        checkIndex_(index, 1, "Index")
        return insert_(index, d)
    }

    // Private helper method for 'insert' which avoids type and bounds checks.
    insert_(index, d) {
        if (index <  0) index = _count + index + 1
        if (index == _count) {
            add(d)
            return d
        }
        var node = Node.new(d)
        if (index == 0) {
            node.next_ = _head
            _head = node
        } else {
            var n = _head
            for (i in 1...index) n = n.next
            node.next_ = n.next
            n.next_ = node
        }
        _count = _count + 1
        return d
    }

    // Inserts an element 'e' immediately after the first occurrence of an element 'd'
    // in the current instance and returns the inserted element. Returns null if 'd'
    // not found.
    insertAfter(d, e) {
        var ix = indexOf_(d, 0)
        return (ix >= 0) ? insert_(ix+1, e) : null
    }

    // Inserts an element 'e' immediately before the first occurrence of an element 'd'
    // in the current instance and returns the inserted element. Returns null if 'd'
    // not found.
    insertBefore(d, e) {
        var ix = indexOf_(d, 0)
        return (ix >= 0) ? insert_(ix, e) : null
    }

    // Removes the element at the specified index of the current instance and returns it.
    removeAt(index) {
        checkIndex_(index, 0, "Index")
        return removeAt_(index) 
    }

    // Private helper method for 'removeAt' which avoids type and bounds checks.
    removeAt_(index) {
        if (index < 0) index = _count + index
        var removed
        if (index == 0) {
            removed = _head.data
            _head = _head.next
        } else {
            var n = _head
            var pred = null
            for (i in 0...index) {
                pred = n
                n = n.next
            }
            removed = n.data
            pred.next_ = n.next
        }
        _count = _count - 1
        return removed
    }

    // Removes the first 'k' elements of the current instance and returns a list of them.
    removeFirst(k) {
        if (k.type != Num || !k.isInteger || k < 0) {
            Fiber.abort("Argument must be a non-negative integer.")
        }
        if (k == 0) return []
        if (k >= _count) {
            var removed = this.toList
            clear()
            return removed
        }
        var removed = this.take(k).toList
        var n = _head
        for (i in 1..k) n = n.next
        _head = n
        _count = _count - k
        return removed
    }

    // Removes the last 'k' elements of the current instance and returns a list of them.
    removeLast(k) {
        if (k.type != Num || !k.isInteger || k < 0) {
            Fiber.abort("Argument must be a non-negative integer.")
        }
        if (k == 0) return []
        if (k >= _count) {
            var removed = this.toList
            clear()
            return removed
        }
        var removed = this.skip(_count - k).toList
        var n = _head
        for (i in 1..._count-k) n = n.next
        _tail = n
        _tail.next_ = null
        _count = _count - k
        return removed
    }

    // Removes all occurrences of the element 'd' from the current instance
    // and returns the number of occurrences.
    remove(d) {
        var ixs = indicesOf_(d, 0)[-1..0]
        if (ixs.count > 0) {
            for (ix in ixs) {
                removeAt_(ix)
            }
        }
        return ixs.count
    }

    // Clears the current instance of all its elements.
    clear() {
        _count = 0
        _head = null
        _tail = null
    }

    // Replaces all occurrences of the element 'd' in the current instance
    // by 'e' and returns the number of occurrences.
    replace(d, e) {
        if (d == e) return 0
        var ixs = indicesOf_(d, 0)
        if (ixs.count > 0) {
            for (ix in ixs) {
                this[ix] = e
            }
        }
        return ixs.count
    }

    // Exchanges the elements at indices 'i' and 'j' of the current instance.
    exchange(i, j) {
        if (i == j) return
        var t = this[i]
        this[i] = this[j]
        this[j] = t
    }

    // Returns the index of the first occurrence of 'd' in the current instance starting
    // from index 'start'.
    indexOf(d, start) {
        checkIndex_(start, 0, "Start")
        return indexOf_(d, start)
    }

    // Private helper method for 'indexOf' which avoids type and bounds checks.
    indexOf_(d, start) {
        if (start < 0) start = _count + start
        var seq = (start == 0) ? this : this.skip(start)
        var i = start
        for (e in seq) {
            if (e == d) return i
            i = i + 1
        }
        return -1
    }

    // Convenience version of 'indexOf' which starts from 0.
    indexOf(d) { indexOf(d, 0) }

    // Returns the index of the first occurrence of any element of the sequence 'ds'
    // in the current instance starting from index 'start'.
    indexOfAny(ds, start) {
        checkIndex_(start, 0, "Start")
        if (start < 0) start = _count + start
        if (!(ds is Sequence)) Fiber.abort("First argument must be a Sequence.")
        var i
        for (d in ds) {
            if ((i = indexOf_(d, start)) >= 0) return i
        }
        return -1
    }

    // Convenience version of 'indexOfAny' which starts from 0.
    indexOfAny(ds) { indexOf(ds, 0) }

    // Returns a list of the indices of all occurrences of 'd' in the current instance
    // starting from index 'start'.
    indicesOf(d, start) {
        checkIndex_(start, 0, "Start")
        return indicesOf_(d, start)
    }

    // Private helper method for 'indicesOf' which avoids type and bounds checks.
    indicesOf_(d, start) {
        if (start < 0) start = _count + start
        var ixs = []
        var seq = (start == 0) ? this : this.skip(start)
        var i = start
        for (e in seq) {
            if (e == d) ixs.add(i)
            i = i + 1
        }
        return ixs
    }

    // Convenience version of 'indicesOf' which starts from 0.
    indicesOf(d) { indicesOf(d, 0) }

    // Returns the element at a specified index or the elements within a specified
    // index range of the current instance. In the latter case, the elements
    // are copied to a new LinkedList instance.
    [index] {
        if (index is Range) {
            if (index.from > index.to) Fiber.abort("Index range cannot be decreasing.")
            var inc = index.isInclusive ? 0 : 1
            if (index.from < 0 || (index.isInclusive && index.to >= _count + inc)) {
                Fiber.abort("Index range is out of bounds.")
            }
            inc = index.isInclusive ? 1 : 0
            var ll = LinkedList.new()
            for (e in this.skip(index.from).take(index.to-index.from + inc)) ll.add(e)
            return ll
        }
        checkIndex_(index, 0, "Index")
        if (index < 0) index = _count + index
        var i = 0
        for (e in this) {
            if (index == i) return e
            i = i + 1
        }
    }

    // Changes the element at the specified index of the current instance to 'd'.
    [index]=(d) {
        checkIndex_(index, 0, "Index")
        var i = 0
        var n = _head
        for (e in this) {
            if (index == i) {
                n.data = d
                return
            }
            i = i + 1
            n = n.next
        }
    }

     // Returns true if this instance contains ALL the values of a sequence, false otherwise.
    containsAll(ds) {
        if (!(ds is Sequence)) Fiber.abort("First argument must be a Sequence.")
        for (d in ds) {
            if (!contains(d)) return false
        }
        return true
    }

    // Returns true if this instance contains ANY of the values, false otherwise.
    containsAny(ds) { indexOfAny(ds, 0) >= 0 }

    // Returns true if this instance contains NONE of the values, false otherwise.
    containsNone(ds) { !containsAny(ds) }

    // Combines the elements of this instance plus those of another LinkedList object
    // into a new LinkedList and returns it.
    +(other) {
        if (other.type != LinkedList) Fiber.abort("Addend must be another LinkedList.")
        var ll = LinkedList.new()
        ll.addAll(this)
        ll.addAll(other)
        return ll
    }

    // Iterator protocol methods.
    iterate(iterator) {
        if (!iterator) {
            return !_head ? false : _head
        }
        return iterator.next
    }

    iteratorValue(iterator) { iterator.data }

    // Iterates through the nodes of this instance and returns for each one
    // a list containing the current and next data members.
    nodes {
        class N is Sequence {
            construct new(head) { 
                _head = head
            }

            iterate(iterator) {
                if (!iterator) {
                    return !_head ? false : _head
                }
                return iterator.next
            }

            iteratorValue(iterator) {
                var n = iterator.next
                var next = (n) ? n.data : null 
                return [iterator.data, next] 
            }
        }
        return N.new(_head)
    }  

    // Prints the consecutive elements of the current instance to stdout
    // separated by a single space and followed by a new line.
    print() {
        for (e in this) System.write("%(e) ")
        System.print()
    }

    // Returns the string representation of the current instance.
    toString { "[" + toList.join(" -> ") +"]" }
}

/* DNode is a building block for a doubly linked list. As such it consists of three fields:
   a data member, which can be of any type, and links to the next and previous Node objects.
*/
class DNode {
    // Constructs a new DNode object.
    construct new(data) {
        _data = data
        _next = null
        _prev = null
    }

    // Public properties.
    data { _data }
    data=(d) { _data = d }

    next { _next }
    next=(n) {
        _next = (n.type == DNode || n == null) ? n : Fiber.abort("Invalid argument.")
    }

    prev { _prev }
    prev=(n) {
        _prev = (n.type == DNode || n == null) ? n : Fiber.abort("Invalid argument.")
    }

    // Private setters, no checks.
    next_=(n) { _next = n }
    prev_=(n) { _prev = n }

    // Returns the string representation of this instance.
    toString { _data.toString }
}

/* DLinkedList represents a doubly linked list of DNode objects.
   The 'elements' of the list generally refer to their data members,
   not the DNodes themselves. Indexing operations support negative
   indices which count backwards from the end of the list.
*/
class DLinkedList is Sequence {

    // Constructs a new, empty DLinkedList object.
    construct new() {
        _count = 0
        _head = null
        _tail = null
    }

    // Constructs a new DLinkedList object and adds the elements of a sequence to it.
    construct new(a) {
        _count = 0
        _head = null
        _tail = null
        addAll(a)
    }

    // Creates a new DLinkedList with 'size' elements, all set to 'd'.
    static filled(size, d) {
        if (size.type != Num || !size.isInteger || size < 0) {
            Fiber.abort("Size cannot be negative.")
        }
        var ll = DLinkedList.new()
        if (size == 0) return ll
        for (i in 1..size) ll.add(d)
        return ll
    }

    // Copies the current instance to a new DLinkedList.
    copy() { DLinkedList.new(this) }

    // Basic properties.
    head { _head ? _head.data : null }  // returns the first element
    tail { _tail ? _tail.data : null }  // returns the last element

    count { _count }                    // returns the number of elements

    // Returns whether or not the current instance is empty.
    isEmpty { _count == 0 }

    // Adds an element at the tail of the current instance and returns it.
    add(d) {
        var node = DNode.new(d)
        if (!_head) {
            _head = node
            _head.next_ = null
            _head.prev_ = null
            _count = 1
        } else {
            var n = _tail
            n.next_ = node
            node.next_ = null
            node.prev_ = n
            _count = _count + 1
        }
        _tail = node
        return d
    }

    // Adds a sequence of elements at the tail of the current instance and returns them.
    addAll(a) {
        if (!(a is Sequence)) Fiber.abort("Argument must be a Sequence.")
        for (e in a) add(e)
        return a
    }

    // Inserts an element at the head of the current instance and returns it.
    prepend(d) { insert_(0, d) }

    // Inserts a sequence of elements at the head of the current instance and returns them.
    prependAll(a) {
        if (!(a is Sequence)) Fiber.abort("Argument must be a Sequence.")
        var i = 0
        for (e in a) {
            insert_(i, e)
            i = i + 1
        }
        return a
    }

    // Private helper method to check whether an index is valid.
    checkIndex_(index, inc, s) {
        if (index.type != Num || !index.isInteger) Fiber.abort("%(s) must be an integer.")
        var c = _count + inc
        if (index >= c || index < -c) Fiber.abort("%(s) is out of bounds.")
    }

    // Inserts an element at a specified index of the current instance
    // and returns the inserted element.
    insert(index, d) {
        checkIndex_(index, 1, "Index")
        return insert_(index, d)
    }

    // Private helper method for 'insert' which avoids type and bounds checks.
    insert_(index, d) {
        if (index <  0) index = _count + index + 1
        if (index == _count) {
            add(d)
            return d
        }
        var node = DNode.new(d)
        if (index == 0) {
            node.next_ = _head
            node.prev_ = null
            _head = node
        } else {
            var mid = (_count/2).floor
            var n
            if (index < mid) {
                n = _head
                for (i in 1...index) n = n.next           
            } else {
                n = _tail
                for (i in _count...index) n = n.prev
            }
            node.next_ = n.next
            n.next.prev_ = node
            node.prev_ = n
            n.next_ = node
        }
        _count = _count + 1
        return d
    }

    // Inserts an element 'e' immediately after the first occurrence of an element 'd'
    // in the current instance and returns the inserted element. Returns null if 'd'
    // not found.
    insertAfter(d, e) {
        var ix = indexOf_(d, 0)
        return (ix >= 0) ? insert_(ix+1, e) : null
    }

    // Inserts an element 'e' immediately before the first occurrence of an element 'd'
    // in the current instance and returns the inserted element. Returns null if 'd'
    // not found.
    insertBefore(d, e) {
        var ix = indexOf_(d, 0)
        return (ix >= 0) ? insert_(ix, e) : null
    }

    // Removes the element at the specified index of the current instance and returns it.
    removeAt(index) {
        checkIndex_(index, 0, "Index")
        return removeAt_(index) 
    }

    // Private helper method for 'removeAt' which avoids type and bounds checks.
    removeAt_(index) {
        if (index < 0) index = _count + index        
        var removed
        if (index == 0) {
            removed = _head.data
            _head = _head.next
            if (_head) _head.prev_ = null
        } else if (index == _count - 1) {
            removed = _tail.data
            _tail = _tail.prev
            _tail.next_ = null
        } else {
            var mid = (_count/2).floor
            var n
            if (index < mid) {
                n = _head
                for (i in 0...index) n = n.next
            } else {
                n = _tail
                for (i in _count-1...index) n = n.prev
            }
            removed = n.data
            n.prev.next_ = n.next
            n.next.prev_ = n.prev
        }
        _count = _count - 1
        return removed
    }

    // Removes the first 'k' elements of the current instance and returns a list of them.
    removeFirst(k) {
        if (k.type != Num || !k.isInteger || k < 0) {
            Fiber.abort("Argument must be a non-negative integer.")
        }
        if (k == 0) return []
        if (k >= _count) {
            var removed = this.toList
            clear()
            return removed
        }
        var removed = this.take(k).toList
        var n = _head
        for (i in 1..k) n = n.next
        n.prev_ = null
        _head = n
        _count = _count - k
        return removed
    }

    // Removes the last 'k' elements of the current instance and returns a list of them.
    removeLast(k) {
        if (k.type != Num || !k.isInteger || k < 0) {
            Fiber.abort("Argument must be a non-negative integer.")
        }
        if (k == 0) return []
        if (k >= _count) {
            var removed = this.toList
            clear()
            return removed
        }
        var removed = this.skip(_count - k).toList
        var n = _tail
        for (i in 1..k) n = n.prev
        _tail = n
        _tail.next_ = null
        _count = _count - k
        return removed
    }

    // Removes all occurrences of the element 'd' from the current instance
    // and returns the number of occurrences.
    remove(d) {
        var ixs = indicesOf_(d, 0)[-1..0]
        if (ixs.count > 0) {
            for (ix in ixs) {
                removeAt_(ix)
            }
        }
        return ixs.count
    }

    // Clears the current instance of all its elements.
    clear() {
        _count = 0
        _head = null
        _tail = null
    }

    // Replaces all occurrences of the element 'd' in the current instance
    // by 'e' and returns the number of occurrences.
    replace(d, e) {
        if (d == e) return 0
        var ixs = indicesOf_(d, 0)
        if (ixs.count > 0) {
            for (ix in ixs) {
                this[ix] = e
            }
        }
        return ixs.count
    }

    // Exchanges the elements at indices 'i' and 'j' of the current instance.
    exchange(i, j) {
        if (i == j) return
        var t = this[i]
        this[i] = this[j]
        this[j] = t
    }

    // Returns the index of the first occurrence of 'd' in the current instance starting
    // from index 'start'.
    indexOf(d, start) {
        checkIndex_(start, 0, "Start")
        return indexOf_(d, start)
    }

    // Private helper method for 'indexOf' which avoids type and bounds checks.
    indexOf_(d, start) {
        if (start < 0) start = _count + start
        var seq = (start == 0) ? this : this.skip(start)
        var i = start
        for (e in seq) {
             if (e == d) return i
             i = i + 1
        }
        return -1
    }

    // Convenience version of 'indexOf' which starts from 0.
    indexOf(d) { indexOf(d, 0) }

    // Returns the index of the last occurrence of 'd' in the current instance.
    lastIndexOf(d) {
        var i = _count - 1
        for (e in this.reversed) {
             if (e == d) return i
             i = i - 1
        }
        return -1
    }

    // Returns the index of the first occurrence of any element of the sequence 'ds'
    // in the current instance starting from index 'start'.
    indexOfAny(ds, start) {
        checkIndex_(start, 0, "Start")
        if (start < 0) start = _count + start
        if (!(ds is Sequence)) Fiber.abort("First argument must be a Sequence.")
        var i
        for (d in ds) {
            if ((i = indexOf_(d, start)) >= 0) return i
        }
        return -1
    }

    // Convenience version of 'indexOfAny' which starts from 0.
    indexOfAny(ds) { indexOf(ds, 0) }

    // Searches for the indices of all occurrences of 'd' in the current instance
    // starting from index 'start' and returns a list of three items:
    // The first item is a Bool indicating whether the value was found.
    // The second item is the number of times the value was found.
    // The third item is a list of indices at which the value was found.
    indicesOf(d, start) {
        checkIndex_(start, 0, "Start")
        var res = indicesOf_(d, start)
        var c = res.count
        return [c > 0, c, res]
    }

    // Private helper method for 'indicesOf' which avoids type and bounds checks and
    // just returns a list of indices at which the value was found.
    indicesOf_(d, start) {
        if (start < 0) start = _count + start
        var ixs = []
        var seq = (start == 0) ? this : this.skip(start)
        var i = start
        for (e in seq) {
            if (e == d) ixs.add(i)
            i = i + 1
        }
        return ixs
    }

    // Convenience version of 'indicesOf' which starts from 0.
    indicesOf(d) { indicesOf(d, 0) }

    // Returns the element at a specified index or the elements within a specified
    // index range of the current instance. In the latter case, the elements
    // are copied to a new DLinkedList instance.
    [index] {
        if (index is Range) {
            if (index.from > index.to) Fiber.abort("Index range cannot be decreasing.")
            var inc = index.isInclusive ? 0 : 1
            if (index.from < 0 || (index.isInclusive && index.to >= _count + inc)) {
                Fiber.abort("Index range is out of bounds.")
            }
            inc = index.isInclusive ? 1 : 0
            var ll = DLinkedList.new()
            for (e in this.skip(index.from).take(index.to-index.from + inc)) ll.add(e)
            return ll
        }
        checkIndex_(index, 0, "Index")
        if (index < 0) index = _count + index
        var mid = (_count/2).floor
        if (index < mid) {
            var i = 0
            for (e in this) {
                if (index == i) return e
                i = i + 1
            }
        } else {
            var i = _count - 1
            for (e in this.reversed) {
                if (index == i) return e
                i = i - 1
            }
        }
    }

    // Changes the element at the specified index of the current instance to 'd'.
    [index]=(d) {
        checkIndex_(index, 0, "Index")
        var mid = (_count/2).floor
        if (index < mid) {
            var i = 0
            var n = _head
            for (e in this) {
                if (index == i) {
                    n.data = d
                    return
                }
                i = i + 1
                n = n.next
            }
        } else {
            var i = _count - 1
            var n = _tail
            for (e in this.reversed) {
                if (index == i) {
                    n.data = d
                    return
                }
                i = i - 1
                n = n.prev
            }
        }
    }

     // Returns true if this instance contains ALL the values of a sequence, false otherwise.
    containsAll(ds) {
        if (!(ds is Sequence)) Fiber.abort("First argument must be a Sequence.")
        for (d in ds) {
            if (!contains(d)) return false
        }
        return true
    }

    // Returns true if this instance contains ANY of the values, false otherwise.
    containsAny(ds) { indexOfAny(ds, 0) >= 0 }

    // Returns true if this instance contains NONE of the values, false otherwise.
    containsNone(ds) { !containsAny(ds) }
  
    // Combines the elements of this instance plus those of another DLinkedList object
    // into a new DLinkedList and returns it.
    +(other) {
        if (other.type != DLinkedList) Fiber.abort("Addend must be another DLinkedList.")
        var ll = DLinkedList.new()
        ll.addAll(this)
        ll.addAll(other)
        return ll
    }

    // Iterator protocol methods.
    iterate(iterator) {
        if (!iterator) {
            return !_head ? false : _head
        }
        return iterator.next
    }

    iteratorValue(iterator) { iterator.data }

    // Reverses the iteration order.
    reversed {
        class R is Sequence {
            construct new(tail) { 
                _tail = tail
            }

            iterate(iterator) {
                if (!iterator) {
                    return !_tail ? false : _tail
                }
                return iterator.prev
            }

            iteratorValue(iterator) { iterator.data }
        }
        return R.new(_tail)
    }
    
    // Iterates through the nodes of this instance and returns for each one
    // a list containing the previous, current and next data members.
    nodes {
        class N is Sequence {
            construct new(head) { 
                _head = head
            }

            iterate(iterator) {
                if (!iterator) {
                    return !_head ? false : _head
                }
                return iterator.next
            }

            iteratorValue(iterator) {
                var p = iterator.prev
                var prev = (p) ? p.data : null 
                var n = iterator.next
                var next = (n) ? n.data : null 
                return [prev, iterator.data, next] 
            }
        }
        return N.new(_head)
    }  

    // Prints the consecutive elements of the current instance to stdout
    // separated by a single space and followed by a new line.
    print() {
        for (e in this) System.write("%(e) ")
        System.print()
    }

    // As 'print' method but prints the elements in reverse.
    rprint() {
        for (e in this.reversed) System.write("%(e) ")
        System.print()
    }

    // Returns the string representation of the current instance.
    toString { "[" + toList.join(" <-> ") +"]" }
}