This is a new series of posts of me going out and learning common data structures and algorithms that you are asked to implement in code interviews. I am not writing this series of posts because I have gone to the Dark Side. I still think this is stupid, but I care about trying to help self-taught people navigate the waters of finding employment and sadly this is a hoop people have to jump through.

I want to give people resources and to also try to give them hope that if they learn this one last thing they can break through the bureaucratic walls keeping them out. I don’t want them to give up or feel like there is an endless number of things they are required to do. We all know this sucks and it’s bullshit. If you bomb one interview, remember what you were asked, study hard, and keep trying.

Figured since I complained so much about this stupid thing, I may as well start with it.

Honestly, if you want the best explanation of this data structure, check out the explanation in the Swift Algorithm Club repository. I have had a lot of people helpfully suggest I read Wayne Bishop’s book, but I honestly think that Ray’s Algorithm Club is a better resource and it has the additional benefit of being free.

The value in a set of posts like this will be seen later. There are lists of sample questions asked during code interviews that use data structures and algorithms to solve problems. I am going to generate posts going over these common problems and try to show how they can be done in Swift.

I am not writing up this series of posts as a resource for other people, but it could still be of some use for someone. I am writing this up because the best way that I have to be engaged with learning something is to attempt to explain it to someone else in a coherent manner.

Overview

A linked list is simply a series of items that connect to one another. A singly linked list goes only one way. A doubly linked list points both backwards and forwards.

If you look at the image of the NeoPixel strip, this kind of illustrates the idea of how a linked list might work. Each pixel is wired in and connected to the ones around it. The data flows in one direction. You can’t skip one pixel to get to the next one. The color starts with the head of the strip and is passed through to each of the pixels in series. Every pixel has a pixel it receives data from and one that it passes data to. It’s like the game Telephone from when you were a kid.

Linked List vs Array

Arrays are faster than linked lists, but they are less flexible than linked lists. Linked lists are not indexed like arrays, so in order to navigate to a node in a linked list, you have to iterate all the way through the list to get where you want to. This means if you want to add things to a linked list, you should add it towards the beginning of the list to make sure you can get to it faster.

Pointers

Linked lists use pointers to elements rather than indexing. This is one reason that this data structure makes me crazy.

One of the big reasons I am grudgingly doing this series of posts is because I know we got to the point a while ago where basically all languages were based on concepts from C. One reason we are asked about linked lists is to prove that we understand the concept of pointers.

Except Swift is a hybrid functional language.

Swift has to work with C and Objective-C and has unsafe mutable pointers, but you’re not really supposed to implement them directly in production Swift. Yes, you can force the issue and use things like pointers when you don’t have to, but that’s really bad programming.

Another reason I am grudgingly doing this is because I want to gain a better understanding of which these fundamental data structures honestly don’t work well with things like Swift. I would argue that creating a data structure based on pointers in Swift is a bad implementation decision. There are probably ways around using pointers, but why bother implementing something like this then?

Should You Implement This in Production Code?

No. There are a lot of other better ways to do this stuff. This is a really simple thing to implement, which is one reason this stupid question gets asked a lot.

Swift 3 Linked List

Here is a brief overview of the code put out by the Swift Algorithm Club:

public class LinkedListNode {
  var value: T
  var next: LinkedListNode?
  weak var previous: LinkedListNode?
  
  public init(value: T) {
    self.value = value
  }
}

public class LinkedList {
  public typealias Node = LinkedListNode
  
  fileprivate var head: Node?
  
  public var isEmpty: Bool {
    return head == nil
  }
  
  public var first: Node? {
    return head
  }
  
  public var last: Node? {
    if var node = head {
      while case let next? = node.next {
        node = next
      }
      return node
    } else {
      return nil
    }
  }
  
  public var count: Int {
    if var node = head {
      var c = 1
      while case let next? = node.next {
        node = next
        c += 1
      }
      return c
    } else {
      return 0
    }
  }

I am impressed that The Algorithm Club created an implementation of a linked list without throwing around mutable unsafe pointers. Their implementation can be found here. I will be using this as the basis for the answers I will be implementing from Cracking the Code Interview in future posts.

There is a lot more code in their implementation and I highly recommend looking it over if you need to use this in a code interview.

Conclusion

I don’t really know what else to say about this. Someone else created a really good implementation of this and I don’t see the point in reinventing the wheel. I think the value in this will be in the future posts when I explore some of the common problems people ask you to do in order to show your understanding of this data structure.

Again, I am trying to make information available rather than trying to show how clever I am for coming up with things. If I can find a good solution someone else has implemented I am happy to use it.