The current project I am working on is to work my way through Cracking the Code Interview creating a Swift implementation of each algorithm and data structure problem listed.

I decided to tackle the Linked List structure first because it was really annoying me how many people told me this was something I MUST learn how to do.

Fortunately the Swift Algorithm Club had an implementation I could look over. I really didn’t see the point in trying to reinvent the wheel, so I figured I could just drag and drop their implementation into a Playground and create a linked list so I could just focus on completing the questions.

(I strongly recommend reading through the tutorial they published recently explaining how to implement this yourself. It’s a great read!)

One issue I encountered was when I attempted to drag and drop the file into a playground. I recently discovered you can have multiple files in Playgrounds and was super excited about it.

I got a compiler error. I looked up the issue and found I needed to import the sources file. No worries. I added it then I got an additional error:

Playground execution failed: error: RemoveDuplicates.playground:8:12: error: 'LinkedList' initializer is inaccessible due to 'internal' protection level
let list = LinkedList()

Huh. That was weird.

I looked over the class and I didn’t see anything that was private. The class and most of the methods were listed as public.

I reached out to the Algorithm Club and they indicated that it was missing a public initializer.

I forked the repository and added a public initializer:

public init() {}

So cool. I should be able to access things now. Huzzah.

I went to go and figure out how to start working on implementing my code questions. The first one talks about iterating through a linked list to remove duplicate values.

I went to start working on this. I realized that there wasn’t a way to simply pass in an already existing data structure to turn into a linked list. I would have to add each node to the linked list one by one.

This seemed like an inconvenience, so I reached out to them again to ask if there was an easier way to do this. They helpfully suggested that I add an extension to the linked list class to let me do this.

Because they did such a great job setting up the class, creating an extension to do this was pretty easy:

extension LinkedList {
  public convenience init(array: Array) {
    self.init()
        
    for element in array {
      self.append(element)
    }
  }
}

I wanted to make sure this actually worked and would be this easy, so I created a test case in their Playground for the Linked List:

let fibonacci = [1, 1, 2, 3, 5, 8,]
let arrayList = LinkedList(array: fibonacci)
print(arrayList)

I forked the repository and submitted this as a pull request.

Conclusion

I really wanted to do an algorithms post every day. I am glad I was able to do one today. It was frustrating to encounter some road blocks, but it was incredibly awesome that the Algorithm Club was around to answer my questions and that I am able to contribute some enhancements to this to make it more useful.

It’s also nice that I was able to use this in a project and find things that were not considered by the original creators and to be able to make it more useful.

Even though I didn’t get to work on my problem set for the evening, it was nice to have a team to work with to solve a problem with code. That’s what I like about programming and I don’t get to do this as much as I would like.

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.