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")

• syb0rg: Welcome to Code Review! Nice first question!

Answer 1

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(" ") + "]"
}

• karan satia: Wish I could mark both as correct but the "more switfy" way was really beneficial to learn.
• karan satia: 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...
• Martin R: @karansatia: Which Xcode version are you using?
• karan satia: 7.2.1. Need to update to 7.3.1
• Martin R: @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.

Answer 2

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

1. 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...
2. 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.
3. 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.
4. 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.)