Global Nerdy

If you’re interviewing for a position that requires you to code, the odds are pretty good that you’ll have to face a coding interview. This series of articles is here to help you gain the necessary knowledge and skills to tackle them!

Over the next couple of articles in this series, I’ll walk you through a classic computer science staple: linked lists. And by the end of these articles, you’ll be able to handle this most clichéd of coding interview problems, satirized in the meme below:

You’ve probably seen the ads for AlgoExpert with the woman pictured above, where she asks you if you want a job at Google and if you know how to reverse a linked list.

But before you learn about reversing linked lists — or doing anything else with them — let’s first answer an important question: what are they?

What are linked lists?

A linked list is a data structure that holds data as a list of items in a specific order. Linked lists are simple and flexible, which is why they’re the basis of many of the data structures that you’ll probably use in your day-to-day programming.

Linked list basics

Nodes

The basic component of a linked list is a node, which is diagrammed below:

In its simplest form, a node is a data structure that holds two pieces of information:

• data: This holds the actual data of the list item. For example, if the linked list is a to-do list, the data could be a string representing a task, such as “clean the bathroom.”
• next: A linked list is simply a set of nodes that are linked together. In addition to the data it holds, a node should also know where the next node is, and that’s what its next property is for: it points to the next item in the list. In languages like C and Go, this would be a pointer, while in languages like C#, Java, JavaScript, Kotlin, Python, and Swift, this would be a reference.

Here’s a Python implementation of a node. We’ll use it to implement a linked list:

# Python

class Node:
    
    def __init__(self, data):
        self.data = data
        self.next = None
        
    def __str__(self):
        return f"{self.data}"

With Node defined, you can create a new node containing the data “Hello, world!” with this line of code:

new_node = Node("Hello, world!")

To print the data contained inside a node, call Node’s print() method, which in turn uses the value returned by its __str__() method:

print(new_node)
# Outputs “Hello, world!”

Assembling nodes into a linked list

You create a linked list by connecting nodes together using their next properties. For example, the linked list in the diagram below represents a list of the first four letters of the alphabet: a, b, c, and d, in that order:

The diagram above features the following:

• Four nodes, each one for a letter in the list.
• A variable called head, which is a pointer or reference to the first item in the list. It’s the entry point to the list, and it’s a necessary part of the list — you can’t access a linked list if you can’t access its head.
• An optional variable called tail, which is a pointer or reference to the last item in the list. It’s not absolutely necessary, but it’s convenient if you use the list like a queue, where the last element in the list is also the last item that was added to the list.

Let’s build the linked list pictured above by putting some nodes together:

# Python

# Let’s build this linked list:
# a -> b -> c -> d

head = Node("a")
head.next = Node("b")
head.next.next = Node("c")
head.next.next.next = Node("d")

That’s a lot of nexts. Don’t worry; we’ll come up with a better way of adding items to a linked list soon.

Here’s an implementation that creates the same list but doesn’t rely on chaining nexts:

# Python

# Another way to build this linked list:
# a -> b -> c -> d

head = Node("a")

node_b = Node("b")
head.next = node_b

node_c = Node("c")
node_b.next = node_c

node_d = Node("d")
node_c.next = node_d

To see the contents of the list, you traverse it by visiting each node. This is possible because each node points to the next one in the list:

# Python

print(head)
print(head.next)
print(head.next.next)
print(head.next.next.next)
print(head.next.next.next.next)

Here’s the output for the code above:

a
b
c
d
None

Of course, the code above becomes impractical if you don’t know how many items are in the list or as the list grows in size.

Fortunately, the repetition in the code — all those prints and nexts — suggests that we can use a loop to get the same result:

# Python

current = head

while current is not None:
    print(current)
    current = current.next

Here’s the output for the code above:

a
b
c
d

A linked list class

Working only with nodes is a little cumbersome. Let’s put together a linked list class that makes use of the Node class:

# Python

class LinkedList:
    
    def __init__(self):
        self.head = None
        
    def __str__(self):
        if self.head is None:
            return('Empty list.')
        
        result = ""
        current_node = self.head
        while current_node is not None:
            result += f'{current_node}\n'
            current_node = current_node.next
        return result.strip()
    
    def add_last(self, data):
        new_node = Node(data)

        # If the list is empty,
        # point `head` to the newly-added node
        # and exit.
        if self.head is None:
            self.head = new_node
            return
        
        # If the list isn’t empty,
        # traverse the list by going to each node’s
        # `next` node until there isn’t a `next` node...
        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        
        # If you’re here, `current_node` is
        # the last node in the list.
        # Point `current_node` at
        # the newly-added node.
        current_node.next = new_node

This LinkedList class has the following members:

• head: A property containing a pointer or reference to the first item in the list, or None if the list is empty.
• __init__(): The class initializer, which initializes head to None, meaning that any newly created LinkedList instance is an empty list.
• __str__(): Returns a string representation of the contents of the linked list for debugging purposes. If the list contains at least one item, it returns the contents of the list. If the list is empty, it returns the string Empty list.
• add_last(): Given a value, it creates a new Node containing that value and adds that Node to the end of the list.

With this class defined, building a new list requires considerably less typing…

# Python

list = LinkedList()
list.add_last("a")
list.add_last("b")
list.add_last("c")
list.add_last("d")

…and displaying its contents is reduced to a single function call, print(list), which produces this output:

a
b
c
d

Coming up next:

• JavaScript implementations
• Adding an item to the start of a linked list
• Finding an item in a linked list
• Will you ever use a linked list, and why do they ask linked list questions in coding interviews?

Previously in this series

• How to solve coding interview questions: Finding the first NON-recurring character in a string in Swift
• How to solve coding interview questions: Looking deeper into finding the first NON-recurring character in a string
• How to solve coding interview questions: The first NON-recurring character in a string
• Coding interview questions: “First recurring character” in Swift
• How to solve coding interview questions: The first recurring character in a string
• I Has the Dumb (or: How I Embarrassed Myself in My Interview with Google) — from way back in 2013

In previous posts, I’ve presented Python, JavaScript, and TypeScript solutions for the coding interview challenge: “Write a function that returns the first NON-recurring character in a given string.” In this post, I’ll show you my solution in Swift.

Here’s a table that provides some sample input and corresponding expected output for this function:

If you give the function this input…	…it should produce this output:
aabbbXccdd	X
a🤣abbbXcc3dd	🤣
aabbccdd	null / None / nil

The algorithm

I’ve been using an algorithm that takes on the problem in two stages:

In the first stage, the function steps through the input string one character at a time, counting the number of times each character in the string appears in a “character record”. Because we’re looking for the first non-recurring character in the input string, the order in which data is stored in the character record is important. It needs to maintain insertion order — that is, the order of the character record must be the same order in which each unique character in the input string first appears.

For example, given the input string aabbbXccdd, the function should build a character record that looks like this:

Character	Count
a	2
b	3
X	1
c	2
d	2

Given the input string a🤣abbbXcc3dd, it should build a character record that looks like this:

Character	Count
a	2
🤣	1
b	3
X	1
c	2
3	1
d	2

Given the input string aabbccdd, it should build a character record that looks like this:

Character	Count
a	2
b	2
c	2
d	2

Once the function has built the character record, it’s time to move to the second stage, where it iterates through the character record in search of a character with a count of 1, and:

• If the function finds such a character, it exits the function at the first such occurrence, returning that character. For the input string aabbbXccdd, it returns X, and for the input string a🤣abbbXcc3dd, it returns 🤣.
• If the function doesn’t find any characters with a count of 1, it exits the function, having gone through every character in the character record, returning a null value (which in the case of Swift is nil).

Using a Swift OrderedDictionary

The character record is the key to making the algorithm work, and the key to the character record is that must be an ordered collection. If I add a, b, and c to the character record, it must maintain the order a, b, c.

This isn’t a problem in Python. While Python dictionaries have traditionally been unordered, as of Python 3.7, dictionaries maintain insertion order. In the previous articles covering this coding interview question, my Python solutions used a regular Python dictionary.

Because JavaScript runs in so many places in so many versions, I decided not to trust that everyone would be running a later version, which preserves insertion order. In the previous article, I wrote a JavaScript solution that implemented the character record using Map, a key-value data structure that keeps the items stored in the order in which they were inserted.

Swift’s built-in Dictionary does not keep the items in any defined order. Luckily, the Swift Collections package provides OrderedDictionary, which gives us both key-value storage and insertion order.

You’ll need to add Swift Collections to your project in order to use it. To do this, select File → Add Packages…

The dialog box for adding packages will appear:

Do the following:

• Enter swift-collections into the search field.
• Select swift-collections from the package list.
• Click Add Package.

You’ll be presented with a list of products within the Swift Collections package:

For this exercise, you’ll need only OrderedCollections, so check its box and click Add Package, which will add the package to your project.

Implementing the solution

Now we can implement the solution!

// We need this for `OrderedDictionary` 
import OrderedCollections

func firstNonRecurringCharacter(text: String) -> String? {
  var characterRecord = OrderedDictionary<Character, Int>()
   
  for character in text {
    if characterRecord.keys.contains(character) {
      characterRecord[character]! += 1
    } else {
      characterRecord[character] = 1
    }
  }
  
  for character in characterRecord.keys {
    if characterRecord[character] == 1 {
      return String(character)
    }
  }
 
  return nil
}

characterRecord, which keeps track of the characters encountered as we go character by character through the input string, is an OrderedDictionary. Note that with Swift, which is both statically and strongly typed, we need to specify that characterRecord’s keys are of type Character and its values are Ints.

After that, the implementation’s similar to my Python and JavaScript versions.

Previously in this series

• How to solve coding interview questions: Looking deeper into finding the first NON-recurring character in a string
• How to solve coding interview questions: The first NON-recurring character in a string
• Coding interview questions: “First recurring character” in Swift
• How to solve coding interview questions: The first recurring character in a string
• I Has the Dumb (or: How I Embarrassed Myself in My Interview with Google) — from way back in 2013