Swift Algorithm Club: Swift Linked List Data Structure

Accessing Nodes

Even though a linked list works most efficiently when you move through nodes in order via previous and next, sometimes it is handy to access an item by index.

To do this, you will declare a nodeAt(index:) method in your LinkedList class. This will return the Node at the specified index.

Update the implementation of LinkedList to include the following:

public func nodeAt(index: Int) -> Node? {
  // 1
  if index >= 0 {
    var node = head
    var i = index
    // 2
    while node != nil {
      if i == 0 { return node }
      i -= 1
      node = node!.next
    }
  }
  // 3
  return nil
}

Here’s what you’ve done:

1. Added a check that the specified index is not negative. This prevents an infinite loop if the index is a negative value.
2. Loop through the nodes until you reach the node at the specified index and return the node.
3. If the index less than 0 or greater than the number of items in the list, then return nil.

Removing All Nodes

Removing all nodes is simple. We just assign nil to the head and tail:

public func removeAll() {
  head = nil
  tail = nil
}

Removing Individual Nodes

To remove an individual node, you will have to deal with three cases:

1. Removing the first node. The requires the head and previous pointers to be updated:
   
2. Removing a node in the middle of the list. This requires the previous and next pointers to be updated:
   
3. Removing the last node in the list. This requires the next and tail pointers to be updated:
   

Update the implementation of LinkedList to include:

public func remove(node: Node) -> String {
  let prev = node.previous
  let next = node.next

  if let prev = prev {
    prev.next = next // 1
  } else { 
    head = next // 2
  }
  next?.previous = prev // 3

  if next == nil { 
    tail = prev // 4
  }

  // 5
  node.previous = nil 
  node.next = nil

  // 6
  return node.value
}

Here’s what you’ve done:

1. Update the next pointer if you are not removing the first node in the list.
2. Update the head pointer if you are removing the first node in the list.
3. Update the previous pointer to the previous pointer of the deleted node.
4. Update the tail if you are removing the last node in the list.
5. Assign nil to the removed nodes previous and next pointers.
6. Return the value for the removed node.

Generics

So far you’ve implemented a general-purpose linked list that stores String values. You’ve provided functionality to append, remove and access nodes in your LinkedList class. In this section we will use generics to abstract away the type requirement from our linked list.

Update the implementation of your Node class to the following:

// 1
public class Node<T> {
  // 2
  var value: T
  var next: Node<T>?
  weak var previous: Node<T>?

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

Here’s what you’ve done:

1. You’ve changed the declaration of the Node class to take a generic type T.
2. Your goal is to allow the Node class to take in values of any type, so you’ll constrain your value property to be type T rather than a String.
3. You’ve also updated your initializer to take any type.

Generics: Challenge

Try updating the implementation of LinkedList to use generics.

The solution is provided in the spoiler section down below, but try it yourself first!

[spoiler title=”Solution”]

// 1. Change the declaration of the Node class to take a generic type T
public class LinkedList<T> {
  // 2. Change the head and tail variables to be constrained to type T
  fileprivate var head: Node<T>?
  private var tail: Node<T>?

  public var isEmpty: Bool {
    return head == nil
  }
  
  // 3. Change the return type to be a node constrained to type T
  public var first: Node<T>? {
    return head
  }

  // 4. Change the return type to be a node constrained to type T
  public var last: Node<T>? {
    return tail
  }

  // 5. Update the append function to take in a value of type T
  public func append(value: T) {
    let newNode = Node(value: value)
    if let tailNode = tail {
      newNode.previous = tailNode
      tailNode.next = newNode
    } else {
      head = newNode
    }
    tail = newNode
  }

  // 6. Update the nodeAt function to return a node constrained to type T
  public func nodeAt(index: Int) -> Node<T>? {
    if index >= 0 {
      var node = head
      var i = index
      while node != nil {
        if i == 0 { return node }
        i -= 1
        node = node!.next
      }
    }
    return nil
  }

  public func removeAll() {
    head = nil
    tail = nil
  }

  // 7. Update the parameter of the remove function to take a node of type T. Update the return value to type T.
  public func remove(node: Node<T>) -> T {
    let prev = node.previous
    let next = node.next

    if let prev = prev {
      prev.next = next
    } else {
      head = next
    }
    next?.previous = prev

    if next == nil {
      tail = prev
    }

    node.previous = nil
    node.next = nil
    
    return node.value
  }
}

[/spoiler]

Your code should compile now, so let’s test this out! At the bottom of your playground file, add the following code to verify that your generic linked list is working:

let dogBreeds = LinkedList<String>()
dogBreeds.append(value: "Labrador")
dogBreeds.append(value: "Bulldog")
dogBreeds.append(value: "Beagle")
dogBreeds.append(value: "Husky")

let numbers = LinkedList<Int>()
numbers.append(value: 5)
numbers.append(value: 10)
numbers.append(value: 15)

Where To Go From Here?

I hope you enjoyed this tutorial on making a linked list!

Here is a Swift playground with the above code. You can also find alternative implementations and further discussion in the linked list section of the Swift Algorithm Club repository.

This was just one of the many algorithm clubs focused on the Swift Algorithm Club repository. If you’re interested in more, check out the repo.

If you have any questions on linked lists in Swift, please join the forum discussion below!

If you enjoyed what you learned in this tutorial, why not check out our Data Structures and Algorithms in Swift book, available on our store?

In Data Structures and Algorithms in Swift, you’ll learn how to implement the most popular and useful data structures and when and why you should use one particular datastructure or algorithm over another. This set of basic data structures and algorithms will serve as an excellent foundation for building more complex and special-purpose constructs.

As well, the high-level expressiveness of Swift makes it an ideal choice for learning these core concepts without sacrificing performance.

• You’ll start with the fundamental structures of linked lists, queues and stacks, and see how to implement them in a highly Swift-like way.
• Move on to working with various types of trees, including general purpose trees, binary trees, AVL trees, binary search trees and tries.
• Go beyond bubble and insertion sort with better-performing algorithms, including mergesort, radix sort, heap sort and quicksort.
• Learn how to construct directed, non-directed and weighted graphs to represent many real-world models, and traverse graphs and trees efficiently with breadth-first, depth-first, Dijkstra’s and Prim’s algorithms to solve problems such as finding the shortest path or lowest cost in a network.
• And much, much more!

By the end of this book, you’ll have hands-on experience solving common issues with data structures and algorithms — and you’ll be well on your way to developing your own efficient and useful implementations.