Inspired by an article discussing immutable implementations of recursive data structures I put an alternate solution together using Swift.
The leading answer documents solution by highlighting the following topics:
I have called these out where applicable in the solution below.
/**
Node is a class that stores an arbitrary value of generic type T
and a pointer to another Node of the same time. This is a recursive
data structure representative of a member of a unidirectional linked
list.
*/
public class Node<T> {
public let value: T
public let next: Node<T>?
public init(value: T, next: Node<T>?) {
self.value = value
self.next = next
}
public func reversedList() -> Node<T> {
if let next = self.next {
// 3. The reverse of the second element on followed by the first element.
return next.reversedList() + value
} else {
// 2. Reverse of a one element list is itself
return self
}
}
}
/**
@return Returns a newly created Node consisting of the lhs list appended with rhs value.
*/
public func +<T>(lhs: Node<T>, rhs: T) -> Node<T> {
let tail: Node<T>?
if let next = lhs.next {
// The new tail is created recursively, as long as there is a next node.
tail = next + rhs
} else {
// If there is not a next node, create a new tail node to append
tail = Node<T>(value: rhs, next: nil)
}
// Return a newly created Node consisting of the lhs list appended with rhs value.
return Node<T>(value: lhs.value, next: tail)
}