Stack using Linked List in Swift

Question

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
        }
    }
}

Martin R · Accepted Answer · 2018-10-12 19:04:56Z

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.

Stack Exchange Network

Stack using Linked List in Swift

1 Answer 1

Further suggestions

You must log in to answer this question.

Hot Network Questions

Stack using Linked List in Swift

1 Answer 1

Further suggestions

You must log in to answer this question.

Related

Hot Network Questions