2
\$\begingroup\$

I made this implementation of a stack in Swift that stores its elements as a linked list. It seems to work perfectly well, but I’m wondering how I can improve it to follow the best practices of the language.

struct StackList<T> : CustomStringConvertible {
    private var first: StackNode? = nil // The topmost node in the stack

    /// Add a new element to the top of the stack
    /// - parameter newElement: the new element to be added
    mutating func push(_ newElement: T) {
        let newElement = StackNode(newElement);
        newElement.next = first;
        first = newElement;
    }

    /// Remove and return the topmost element from the stack
    /// - returns: Optional containing the removed element, or nil if the stack was empty
    mutating func pop() -> T? {
        guard let first = first else { return nil }

        let poppedElement = first.element
        self.first = first.next
        return poppedElement
    }

    /// The number of elements in the stack
    var size: Int {
        var count = 0
        var current = first

        // Traverse the list
        while current != nil {
            count += 1
            current = current!.next
        }
        return count
    }

    /// Textual representation of the stack
    var description: String {
        var output = ""

        // Traverse the list
        var currentNode = first;
        while let thisNode = currentNode {
            if output != "" { output += ", " }  // Add commas between elements
            output += String(describing: thisNode.element)

            currentNode = thisNode.next
        }

        return "[\(output)]"
    }

    private class StackNode {
        var next: StackNode? = nil
        var element: T

        init(_ element: T) {
            self.element = element
        }
    }
}
\$\endgroup\$
5
\$\begingroup\$

That looks already quite good and clean. Here are my remarks:

private var first: StackNode? = nil // The topmost node in the stack

An optional value is initalized to nil by default, so

private var first: StackNode? // The topmost node in the stack

is sufficient. And with a different variable name it becomes self-explaining:

private var top: StackNode?

There are trailing semi-colons at some places, these are not needed in Swift.

Here

    let newElement = StackNode(newElement)
    newElement.next = first
    first = newElement

you pass one property of the new node as parameter of the init method, and set the other via accessor, which looks asymmetric to me. With

private class StackNode {
    var next: StackNode?
    let element: T

    init(_ element: T, next: StackNode?) {
        self.element = element
        self.next = next
    }
}

this simplifies to

    let newElement = StackNode(newElement, next: first)
    first = newElement

or even

    first = StackNode(newElement, next: first)

Note also that the element property in StackNode can be a constant.

A better property name for

/// The number of elements in the stack
var size: Int 

might be count – that is what all Swift collection types use. The forced unwrap in

    // Traverse the list
    while current != nil {
        count += 1
        current = current!.next
    }

is safe, but can even be avoided with

    // Traverse the list
    while let node = current {
        count += 1
        current = node.next
    }

A common practice is to put the implementation of protocols into separate extensions:

extension StackList: CustomStringConvertible {
    var description: String { ... }
}

Naming: class StackNode is defined within the StackList “namespace,” so you can simply name it Node. And I would name StackList just Stack – it is an implementation detail that it uses a linked list.

Further suggestions

Make StackList conform to Sequence. A simple implementation would be

extension StackList: Sequence {
    func makeIterator() -> AnyIterator<T> {
        var current = first
        return AnyIterator {
            guard let node = current else { return nil }
            defer { current = node.next }
            return node.element
        }
    }
}

That allows to enumerate all elements easily:

for item in stack { print(item) }

In addition, you can use it in the description method which then simplifies to

extension StackList: CustomStringConvertible {
    var description: String {
        return "[" + self.map { "\($0)" }.joined(separator: ", ") + "]"
    }
}

Implement a peek() method to get the top element without removing it, and an isEmpty property.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.