Avoiding misuse of optional unwrapping: LinkedList

Question

Below is my implementation of a generic linked list in swift. Unfortunately, Swift playgrounds won't run until the compiler is totally happy - often, that involves clang making me explicitly unwrap some optionals. I just want a general idea of how to restructure my code to avoid unwrapping optionals and to make more use of "guard". To reduce the code, I'll only include source code for a few operations.

import Foundation

class Node<T:Equatable> {
    var value: T? = nil
    var next: Node<T>? = nil
    var prev: Node<T>? = nil

    init() {

    }

    init(value: T) {
        self.value = value
    }
}

class LinkedList<T:Equatable> {
    var count: Int = 0
    var head: Node<T> = Node<T>()
    var tail: Node<T> = Node<T>()

    init () {

    }

    func isEmpty() -> Bool {
        return self.count == 0
    }


    func addItemToTail (value: T) {
        let node = Node<T>(value: value) // create node with value of passed argument
        if self.self.isEmpty() { // if list is empty, set the head and tail to be our single node
            self.head = node
            self.tail = node
        }
        else { // if the list isnt empty, make node previous point to curent tail, make original tail now point to node, and set node to be tail of list
            node.prev = self.tail
            self.tail.next = node
            self.tail = node
        }
        self.count++ // always change our counter
    }


    func removeItemAtIndex(position: Int) {
        if self.count > position {   //make sure position exists
            if self.count != 1 { //this means there are at least 2 elements in the linked list. Int (position) can be 0 at the lowest. Count is greater than 0, and if it's not 1, it
                //must be 2 or greater.                /
                if position == 0 { //item to remove is the head so we must remove connections to the next one, and make the next one the head.
                    //let newHead = self.head.next!
                    self.head = self.head.next! //pointers to further nodes are maintained, we simply dropped out the current head and reassigned the next one
                }
                if position == self.count-1 { //item to remove is the tail so we must get the previous node and make that the new tail.
                    self.tail.prev!.next = nil //tail points to nothing, so have tail->previous have the next node be nil
                    self.tail = self.tail.prev!
                }
                if (position > 0 && position < count-1) {
                    var currentNode = self.head
                    for _ in 0...position-1 {
                        currentNode = currentNode.next!
                    }
                    //the node being stored in currentNode is now the node at the index to be deleted. Link the next and prev nodes and remove from list
                    currentNode.next!.prev = currentNode.prev //make the next node->prev to previous node
                    currentNode.prev!.next = currentNode.next //make previous node->next point to next node
                    }
                }
            if self.count == 1 { //we have a single element and we're now removing it. We won't set linked list to nil, but rather give it an initialized head that has no
                //data for next, prev or value properties
                self.head = Node<T>()
                self.tail = Node<T>()        //if we were making this circular, then we would also have a blank node for the tail, as one node can be both a head and tail
            }
            self.count-- //always maintain the element count as our operations rely on it for figuring out computations.
        }
    }


    func printList() {
        var output: String = "["
        var currentNode: Node? = self.head
        while (currentNode != nil) {
            output += String(currentNode!.value)
            currentNode = currentNode!.next
            if (currentNode != nil) {
                output += " "
            }
        }
        output += "]"
        Swift.print(output)
    }
}



var list = LinkedList<String>()

list.addItemToTail("this")
list.addItemToTail("is a")
list.addItemToTail("linked list")
list.addItemToTail("in swift")

\$\begingroup\$ Welcome to Code Review! Nice first question! \$\endgroup\$

syb0rg
– syb0rg

2016-05-20 15:58:34 +00:00
Commented May 20, 2016 at 15:58 — syb0rg
– syb0rg, Commented May 20, 2016 at 15:58

Martin R · Accepted Answer · 2016-05-20 22:07:48Z

Daniel has already covered the most important points, here are some additional remarks:

The Node class does not need T to be Equatable, you can remove that restriction.
Within the scope of class Node<T> { ... }, you can shorten Node<T> to Node without repeating the placeholder type.
Optionals are implicitly initialized to nil.
The prev and next property should be private because these are not meant to be accessed (or modified) from outside the module. The same applies to head and tail in LinkedList.

Together with Daniel's suggestion to make the value property non-optional, the class definition would then look like this:

class Node<T> {
    var value: T
    private var next: Node?
    private var prev: Node?

    init(value: T) {
        self.value = value
    }
}

I would make isEmpty a computed property instead of an instance method (similar to the isEmpty property of CollectionType etc):

var isEmpty: Bool {
    return self.count == 0
}

Instead of a printList() method it is more Swifty to make the type conform to CustomStringConvertible:

extension LinkedList : CustomStringConvertible {

    var description: String {
        var output = "["
        // ... append all list elements ...
        output += "]"
        return output
    }
}

Now you can just print(list) to get its description.

The ++ and -- operators are deprecated in Swift 2.2 and will be removed in Swift 3. You should replace them by

 self.count += 1
 self.count -= 1

It would also make sense to make LinkedList conform to SequenceType which is not too difficult:

extension LinkedList : SequenceType {
    func generate() -> AnyGenerator<Node<T>> {
        var currentNode = self.head
        return AnyGenerator {
            if let node = currentNode {
                defer { currentNode = node.next }
                return node
            } else {
                return nil
            }
        }
    }
}

Then you can traverse a list with

for item in list {
    print(item.value)
}

As a bonus, the description property simplifies to

var description: String {
    return "[" + self.map { String($0.value) }.joinWithSeparator(" ") + "]"
}

Wish I could mark both as correct but the "more switfy" way was really beneficial to learn. — karan satia
– karan satia, Commented May 23, 2016 at 11:43
Running into tons of issues trying to follow the advice given on here. After encapsulating my node properties and making head&tail optionals (and value required), in my addItemToTail function, I keep getting the error "cannot call value of non-function type 'Node<T>'?". I'm trying to assign currentNode = currentNode.next so I can traverse the list. I tried making it conform to sequencetype but kept getting the error "Argument passed to call that takes no arguments" after the "return AnyGenerator" code... — karan satia
– karan satia, Commented May 23, 2016 at 18:35
@karansatia: Yes, the above code uses Swift 2.2 (Xcode 7.3). With Swift 2.1 (Xcode 7.2) it would be return anyGenerator { ... }, but there may be more differences. — Martin R
– Martin R, Commented May 24, 2016 at 4:52

Daniel T. · Accepted Answer · 2016-05-20 21:42:42Z

You avoid force-unwrapping optionals by using the if let construct. An obvious example in your code is in your addItemToTail method. Instead of calling isEmpty, you could check to see if tail's value was a valid node... Something like:

// NOTE: this code assumes you follow my advice below and make tail optional and value required.
if let tail = tail {
    // at this point, we know the list isn't empty because it has a valid tail in it.
    node.prev = tail
    tail.next = node
    self.tail = node // have to use self.tail here to avoid trying to assign to the local tail which is a let constant.
}
else {
    // the list must be empty, otherwise it would have a valid tail.
    head = node
    tail = node
}

There is also a while let construct that you can use in your printList() function...

    while let node = currentNode, let value = node.value {
        output += String(value)
        currentNode = node.next
        if currentNode != nil {
            output += " "
        }
    }

Since this a code review site, here are some other notes about your code...

Your linked list class should actually be a struct like the rest of the Swift containers. Of course this would mean you have to ensure correct copy semantics...
Instead of Node holding an optional value, it should be a required value. There's no point in having a node that isn't holding a value.
If you change the above, you will have to make head and tail in the LinkedList optional. This makes sense though because and empty list wouldn't have either a head or tail. Doing this will also make your if lets (like in addItemToTail simpler because you won't have to also check that value != nil.
Your removeItemAtIndex method is more complex than it needs to be. You should be able to implement it with one loop and two if statements. (walk up the chain until you find the correct node to remove. Assign its next node to its prev node's next. Assign its prev node to its next node's prev. Then correct head and tail if necessary.)

Stack Exchange Network

Avoiding misuse of optional unwrapping: LinkedList

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Avoiding misuse of optional unwrapping: LinkedList

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions