Category: Programming

The linked list exercises continue! In case you missed them, be sure to check out part 1 and part 2 of this linked list series before moving forward…

Adding an item to the start of a linked list

In this article, the first new feature we’ll implement is the ability to add new items to the start of the list. It’s similar to adding an item to the end of a list, which is why I reviewed it above.

The diagram below shows the first two nodes of a linked list. Recall that a linked list’s head points to its first node and that every node points to the next one:

Here’s how you add a new node to the start of the list. The new node becomes the first node, and the former first node becomes the second node:

Here are the steps:

• Create a new node. In our implementation, newly-created nodes have a next property that points to null, nil, or None by default.
• If the list is empty (i.e. head points to null, nil, or None), adding it to the list is the same thing as adding it to the start of the list. Point head to the new node and you’re done.
• If the list is not empty, you need to do just a little more work.
  • Point the new node’s next property to head. This makes the current first node the one that comes after the new node.
  • Point head at the new node. This makes the new node the first one in the list.

Here’s how I implemented this in Python…

# Python

def add_first(self, value):
    new_node = Node(value)

    # 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,
    # make the current first node the second node
    # and make the new node the first node.
    new_node.next = self.head
    self.head = new_node

…and here’s my JavaScript implementation:

# JavaScript

addFirst(value) {
    let newNode = new Node(value)
    
    // If the list is empty,
    // point `head` to the newly-added node
    // and exit.
    if (this.head === null) {
        this.head = newNode
        return
    }
    
    // If the list isn’t empty,
    // make the current first node the second node
    // and make the new node the first node.
    newNode = this.head
    this.head = newNode
}

Inserting a new item at a specified position in the list

So far, we’ve implemented methods to:

• Add a new item to the start of the list, and
• Add a new item to the end of the list.

Let’s do something a little more complicated: adding a new item at a specified position in the list. The position is specified using a number, where 0 denotes the first position in the list.

Here’s how you add a new node at a specified position in the list.

Here are the steps:

• The function has two parameters:
  1. index: The index where a new node should be inserted into the list, with 0 denoting the first item.
  2. value: The value that should be stored in the new node.
• Create a new node, new_node, and put value into it.
• Use a variable, current_index, to keep track of the index of the node we’re currently looking at as we traverse the list. It should initially be set to 0.
• Use another variable, current_node, which will hold a reference to the node we’re currently looking at. It should initially be set to head, which means that we’ll start at the first item in the list.
• Repeat the following as long as current_node is not referencing null, nil, or None:
  • We’re looking for the node in the position immediately before the position where we want to insert the new node. If current_index is one less than index:
    • Point the new node at the current node’s next node.
    • Point the current node at the new node.
    • Return true, meaning that we successfully inserted a new item into the list
  • If we’re here, it means that we haven’t yet reached the node immediately before the insertion point. Move to the next node and increment current_index.
• If we’re here, it means that we’ve gone past the last item in the list. Return false, meaning we didn’t insert a new item into the list.

Here’s how I implemented this in Python…

# Python

def insert_element_at(self, index, value):
    new_node = Node(value)
    current_index = 0
    current_node = self.head

    # Traverse the list, keeping count of 
    # the nodes that you visit,
    # until you’ve reached the specified node.  
    while current_node:
        if current_index == index - 1:
            # We’re at the node before the insertion point!
            # Make the new node point to the next node
            # and the current node point to the new node.
            new_node.next = current_node.next
            current_node.next = new_node
            return True
        
        # We’re not there yet...
        current_node = current_node.next
        current_index += 1
        
    # If you’re here, the given index is larger
    # than the number of elements in the list.
    return False

…and here’s my JavaScript implementation:

// JavaScript

insertElementAt(index, value) {
    let newNode = new Node(value)
    let currentIndex = 0
    let currentNode = this.head
    
    // Traverse the list, keeping count of 
    // the nodes that you visit,
    // until you’ve reached the specified node.     
    while (currentNode) {
        if (currentIndex === index - 1) {
            // We’re at the node before the insertion point!
            // Make the new node point to the next node
            // and the current node point to the new node.
            newNode.next = currentNode.next
            currentNode.next = newNode
            return true
        }
        
        // We’re not there yet...
        currentNode = currentNode.next
        currentIndex++
    }
    
    // If you’re here, the given index is larger
    // than the number of elements in the list.
    return false        
}

Deleting an item from a specified position in the list

Now that we can add a new item at a specified position in the list, let’s implement its opposite: deleting an item from a specified position in the list. Once again, the position is specified using a number, where 0 denotes the first position in the list.

Here’s how you delete a new node from a specified position in the list:

Here are the steps:

• The function has a single parameter, index: the index of the node to be deleted, with 0 denoting the first item in the list.
• Use a variable, current_index, to keep track of the index of the node we’re currently looking at as we traverse the list. It should initially be set to 0.
• Use another variable, current_node, which will hold a reference to the node we’re currently looking at. It should initially be set to head, which means that we’ll start at the first item in the list.
• Repeat the following as long as current_node is not referencing null, nil, or None:
  • We’re looking for the node in the position immediately before the position of the node we want to delete. If current_index is one less than index:
    • Point the current node to the next node’s next node, which removes the next node from the list.
    • Set both the next node’s data and next properties to null, nil, or None. At this point, this node is no longer in the list and is an “island” — no object points to it, and it doesn’t point to any objects. It will eventually be garbage collected.
    • Return true, meaning that we successfully deleted the item from the list
  • If we’re here, it means that we haven’t yet reached the node immediately before the deletion point. Move to the next node and increment current_index.
• If we’re here, it means that we’ve gone past the last item in the list. Return false, meaning we didn’t delete the item from the list.

Here’s how I implemented this in Python…

# Python

def delete_element_at(self, index):
    current_index = 0
    current_node = self.head

    # Traverse the list, keeping count of 
    # the nodes that you visit,
    # until you’ve reached the specified node.  
    while current_node:
        if current_index == index - 1:
            # We’re at the node before the node to be deleted!
            # Make the current node point to the next node’s next node
            # and set the next node’s `data` and `next` properties
            # to `None`.
            delete_node = current_node.next
            current_node.next = delete_node.next
            delete_node.data = None
            delete_node.next = None
            return True
        
        # We’re not there yet...
        current_node = current_node.next
        current_index += 1
        
    # If you’re here, the given index is larger
    # than the number of elements in the list.
    return False

…and here’s my JavaScript implementation:

// JavaScript

deleteElementAt(index) {
    let currentIndex = 0
    let currentNode = this.head
    
    // Traverse the list, keeping count of 
    // the nodes that you visit,
    // until you’ve reached the specified node.  
    while (currentNode) {
        if (currentIndex === index - 1) {
            // We’re at the node before the node to be deleted!
            // Make the current node point to the next node’s next node
            // and set the next node’s `data` and `next` properties
            // to `null`.
            const deleteNode = currentNode.next
            currentNode.next = deleteNode.next
            deleteNode.data = null
            deleteNode.next = null
            return true
        }
        
        // We’re not there yet...
        currentNode = currentNode.next
        currentIndex++
    }
    
    // If you’re here, the given index is larger
    // than the number of elements in the list.
    return false  
}

The classes so far

Let’s take a look at the complete Node and LinkedList classes so far, in both Python and JavaScript.

Python

# Python

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


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:
            result += f'{current_node}\n'
            current_node = current_node.next
            
        return result.strip()
    
    def add_last(self, value):
        new_node = Node(value)

        # 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
        
    def __len__(self):
        count = 0
        current_node = self.head
        
        # Traverse the list, keeping count of 
        # the nodes that you visit,
        # until you’ve gone past the last node.
        while current_node:
            current_node = current_node.next
            count += 1
            
        return count        
        
    def get_element_at(self, index):
        current_index = 0
        current_node = self.head
        
        # Traverse the list, keeping count of 
        # the nodes that you visit,
        # until you’ve reached the specified node.        
        while current_node:
            if current_index == index:
                # We’re at the node at the given index!
                return current_node.data
            
            # We’re not there yet...
            current_node = current_node.next
            current_index += 1
    
        # If you’re here, the given index is larger
        # than the number of elements in the list.
        return None
    
    def set_element_at(self, index, value):
        current_index = 0
        current_node = self.head
        
        # Traverse the list, keeping count of 
        # the nodes that you visit,
        # until you’ve reached the specified node.  
        while current_node:
            if current_index == index:
                # We’re at the node at the given index!
                current_node.data = value
                return True
            
            # We’re not there yet...
            current_node = current_node.next
            current_index += 1
            
        # If you’re here, the given index is larger
        # than the number of elements in the list.
        return False
        
    def add_first(self, value):
        new_node = Node(value)

        # 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,
        # make the current first node the second node
        # and make the new node the first node.
        new_node.next = self.head
        self.head = new_node
        
    def insert_element_at(self, index, value):
        new_node = Node(value)
        current_index = 0
        current_node = self.head
        
        # Traverse the list, keeping count of 
        # the nodes that you visit,
        # until you’ve reached the specified node.  
        while current_node:
            if current_index == index - 1:
                # We’re at the node before the insertion point!
                # Make the new node point to the next node
                # and the current node point to the new node.
                new_node.next = current_node.next
                current_node.next = new_node
                return True
            
            # We’re not there yet...
            current_node = current_node.next
            current_index += 1
            
        # If you’re here, the given index is larger
        # than the number of elements in the list.
        return False
        
    def delete_element_at(self, index):
        current_index = 0
        current_node = self.head
        
        # Traverse the list, keeping count of 
        # the nodes that you visit,
        # until you’ve reached the specified node.  
        while current_node:
            if current_index == index - 1:
                # We’re at the node before the node to be deleted!
                # Make the current node point to the next node’s next node
                # and set the next node’s `data` and `next` properties
                # to `None`.
                delete_node = current_node.next
                current_node.next = delete_node.next
                delete_node.data = None
                delete_node.next = None
                return True
            
            # We’re not there yet...
            current_node = current_node.next
            current_index += 1
            
        # If you’re here, the given index is larger
        # than the number of elements in the list.
        return False

JavaScript

// JavaScript

class Node {
    
    constructor(data) {
        this.data = data
        this.next = null
    }
    
    toString() {
        return this.data.toString()
    }
    
}


class LinkedList {
    
    constructor() {
        this.head = null
    }
    
    toString() {
        if (!this.head) {
            return('Empty list.')
        }
        
        let output = ""
        let currentNode = this.head

        while (currentNode) {
            output += `${currentNode.data.toString()}\n`
            currentNode = currentNode.next
        }
        
        return output.trim()
    }
    
    addLast(value) {
        let newNode = new Node(value)
        
        // If the list is empty,
        // point `head` to the newly-added node
        // and exit.
        if (this.head === null) {
            this.head = newNode
            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...
        let currentNode = this.head
        while (currentNode.next) {
            currentNode = currentNode.next
        }
        
        // If you’re here, `currentNode` is
        // the last node in the list.
        // Point `currentNode` at
        // the newly-added node.
        currentNode.next = newNode
    }
    
    getCount() {
        let count = 0
        let currentNode = this.head
        
        // Traverse the list, keeping count of 
        // the nodes that you visit,
        // until you’ve gone past the last node.
        while (currentNode) {
            currentNode = currentNode.next
            count++
        }
        
        return count
    }
    
    getElementAt(index) {
        let currentIndex = 0
        let currentNode = this.head
        
        // Traverse the list, keeping count of 
        // the nodes that you visit,
        // until you’ve reached the specified node.     
        while (currentNode) {
            if (currentIndex === index) {
                // We’re at the node at the given index!
                return currentNode.data
            }
            
            // We’re not there yet...
            currentNode = currentNode.next
            currentIndex++
        }
        
        // If you’re here, the given index is larger
        // than the number of elements in the list.
        return null
    }
    
    setElementAt(index, value) {
        let currentIndex = 0
        let currentNode = this.head
        
        // Traverse the list, keeping count of 
        // the nodes that you visit,
        // until you’ve reached the specified node.     
        while (currentNode) {
            if (currentIndex === index) {
                // We’re at the node at the given index!
                currentNode.data = value
                return true
            }
            
            // We’re not there yet...
            currentNode = currentNode.next
            currentIndex++
        }
        
        // If you’re here, the given index is larger
        // than the number of elements in the list.
        return false
    }
    
    addFirst(value) {
        let newNode = new Node(value)
        
        // If the list is empty,
        // point `head` to the newly-added node
        // and exit.
        if (this.head === null) {
            this.head = newNode
            return
        }
        
        // If the list isn’t empty,
        // make the current first node the second node
        // and make the new node the first node.
        newNode = this.head
        this.head = newNode
    }
    
    insertElementAt(index, value) {
        let newNode = new Node(value)
        let currentIndex = 0
        let currentNode = this.head
        
        // Traverse the list, keeping count of 
        // the nodes that you visit,
        // until you’ve reached the specified node.     
        while (currentNode) {
            if (currentIndex === index - 1) {
                // We’re at the node before the insertion point!
                // Make the new node point to the next node
                // and the current node point to the new node.
                newNode.next = currentNode.next
                currentNode.next = newNode
                return true
            }
            
            // We’re not there yet...
            currentNode = currentNode.next
            currentIndex++
        }
        
        // If you’re here, the given index is larger
        // than the number of elements in the list.
        return false        
    }
    
    deleteElementAt(index) {
        let currentIndex = 0
        let currentNode = this.head
        
        // Traverse the list, keeping count of 
        // the nodes that you visit,
        // until you’ve reached the specified node.  
        while (currentNode) {
            if (currentIndex === index - 1) {
                // We’re at the node before the node to be deleted!
                // Make the current node point to the next node’s next node
                // and set the next node’s `data` and `next` properties
                // to `null`.
                const deleteNode = currentNode.next
                currentNode.next = deleteNode.next
                deleteNode.data = null
                deleteNode.next = null
                return true
            }
            
            // We’re not there yet...
            currentNode = currentNode.next
            currentIndex++
        }
        
        // If you’re here, the given index is larger
        // than the number of elements in the list.
        return false  
    }
    
}

Coming up next

It’s time to reverse that list!

Previously in this series

• How to solve coding interview questions: Linked lists, part 2
• How to solve coding interview questions: Linked lists, part 1
• 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 case you missed part 1…

Before you continue reading, be sure to check out part 1! It’s where I explain what a linked list is, and provide a couple of basic classes that we’ll build on in this article.

A quick recap

A linked list is a data structure that holds data as a list of items in a specific order. Each item in the list is represented by a node, which “knows” two things:

• Its data
• Where the next node is

Here’s a picture of a node’s structure:

Linked lists are created by connecting nodes together, as shown in the diagram below for a list containing the characters 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.

The JavaScript version of the previous article’s code

In the previous article, I provided code for the Node and LinkedList classes in Python. As promised, here are those classes implemented in JavaScript.

// JavaScript

class Node {
    
    constructor(data) {
        this.data = data
        this.next = null
    }
    
    toString() {
        return this.data.toString()
    }
    
}


class LinkedList {
    
    constructor() {
        this.head = null
    }
    
    toString() {
        let output = ""
        let currentNode = this.head

        while (currentNode) {
            output += `${currentNode.data.toString()}\n`
            currentNode = currentNode.next
        }
        
    toString() {
        if (!this.head) {
            return('Empty list.')
        }
        
        let output = ""
        let currentNode = this.head

        while (currentNode) {
            output += `${currentNode.data.toString()}\n`
            currentNode = currentNode.next
        }
        
        return output.trim()
    }
    
    addLast(data) {
        let newNode = new Node(data)
        
        // If the list is empty,
        // point `head` to the newly-added node
        // and exit.
        if (this.head === null) {
            this.head = newNode
            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...
        let currentNode = this.head
        while (currentNode.next) {
            currentNode = currentNode.next
        }
        
        // If you’re here, `currentNode` is
        // the last node in the list.
        // Point `currentNode` at
        // the newly-added node.
        currentNode.next = newNode
    }

}

…where each item in a list is represented by the node. A node knows only about the data it contains and where the next node in the list is.

The JavaScript version of Node and LinkedList uses the same algorithms as the Python version. The Python version follows the snake_case naming convention, while the JavaScript version follows the camelCase convention.

The JavaScript LinkedList class has the following members:

• head: A property containing a pointer or reference to the first item in the list, or null if the list is empty. This property has the same name in the Python version.
• constructor(): The class constructor, which initializes head to null, meaning that any newly created LinkedList instance is an empty list. In the Python version, the __init__() method has this role.
• toString(): 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. In the Python version, the __str__() method has this role.
• addLast(): Given a value, it creates a new Node containing that value and adds that Node to the end of the list. In the Python version, the add_last() method has this role.

Adding more functionality to the list

In this article, we’re going to add some much-needed additional functionality to the LinkedList class, namely:

• Reporting how many elements are in the list
• Getting the value of the nth item in the list
• Setting the value of the nth item in the list

I’ll provide both Python and JavaScript implementations.

How many elements are in the list?

To find out how many elements are in a linked list, you have to start at its head and “step through” every item in the list by following each node’s next property, keeping a count of each node you visit. When you reach the last node — the one whose next property is set to None in Python or null in JavaScript — report the number of nodes you counted.

The Python version uses one of its built-in “dunder” (Pythonese for double-underscore) methods, __len__(), to report the number of items in the list. Defining __len__() for LinkedList means that any LinkedList instance will report the number of items it contains when passed as an argument to the built-in len() function. For example, if a LinkedList instance named my_list contains 5 items, len(my_list) returns the value 5.

Here’s the Python version, which you should add to the Python version of LinkedList:

# Python

def __len__(self):
    count = 0
    current_node = self.head
    
    # Traverse the list, keeping count of 
    # the nodes that you visit,
    # until you’ve gone past the last node.
    while current_node:
        current_node = current_node.next
        count += 1
        
    return count    

The JavaScript version is getCount(). If a LinkedList instance named myList contains 5 items, len(myList) returns the value 5.

Here’s the JavaScript version, which you should add to the JavaScript version of LinkedList:

// JavaScript

getCount() {
    let count = 0
    let currentNode = this.head
    
    // Traverse the list, keeping count of 
    // the nodes that you visit,
    // until you’ve gone past the last node.
    while (currentNode) {
        currentNode = currentNode.next
        count++
    }
    
    return count
}

How do I get the data at the nth node in the list?

To get the data at the nth node of the list, you can use an approach that’s similar to the one for counting the list’s elements. You have to start at the head and “step through” every item in the list by following each node’s next property, keeping a count of each node you visit and comparing it against n, where n is the index of the node whose data you want. When the count of nodes you’ve visited is equal to n, report the data contained within the current node.

Here’s the Python version, get_element_at(), which you should add to the Python version of LinkedList:

# Python

def get_element_at(self, index):
    current_index = 0
    current_node = self.head

    # Traverse the list, keeping count of 
    # the nodes that you visit,
    # until you’ve reached the specified node.        
    while current_node:
        if current_index == index:
            # We’re at the node at the given index!
            return current_node.data
        
        # We’re not there yet...
        current_node = current_node.next
        current_index += 1

    # If you’re here, the given index is larger
    # than the number of elements in the list.
    return None

Here’s the JavaScript version, getElementAt(), which you should add to the JavaScript version of LinkedList:

// JavaScript

getElementAt(index) {
    let currentIndex = 0
    let currentNode = this.head
    
    // Traverse the list, keeping count of 
    // the nodes that you visit,
    // until you’ve reached the specified node.     
    while (currentNode) {
        if (currentIndex === index) {
            // We’re at the node at the given index!
            return currentNode.data
        }
        
        // We’re not there yet...
        currentNode = currentNode.next
        currentIndex++
    }
    
    // If you’re here, the given index is larger
    // than the number of elements in the list.
    return null
}

How do I set the value of the nth node in the list?

To set the data at the nth node of the list, you can use an approach that’s similar to the one for getting the data at the nth node. You have to start at the head and “step through” every item in the list by following each node’s next property, keeping a count of each node you visit and comparing it against n, where n is the index of the node whose data you want. When the count of nodes you’ve visited is equal to n, set the current node’s data property to the new value.

Here’s the Python version, set_element_at(), which you should add to the Python version of LinkedList:

# Python

def set_element_at(self, index, value):
    current_index = 0
    current_node = self.head

    # Traverse the list, keeping count of 
    # the nodes that you visit,
    # until you’ve reached the specified node.  
    while current_node:
        if current_index == index:
            # We’re at the node at the given index!
            current_node.data = value
            return True
        
        # We’re not there yet...
        current_node = current_node.next
        current_index += 1
        
    # If you’re here, the given index is larger
    # than the number of elements in the list.
    return False

Here’s the JavaScript version, setElementAt(), which you should add to the JavaScript version of LinkedList:

// JavaScript

setElementAt(index, value) {
    let currentIndex = 0
    let currentNode = this.head
    
    // Traverse the list, keeping count of 
    // the nodes that you visit,
    // until you’ve reached the specified node.     
    while (currentNode) {
        if (currentIndex === index) {
            // We’re at the node at the given index!
            currentNode.data = value
            return true
        }
        
        // We’re not there yet...
        currentNode = currentNode.next
        currentIndex++
    }
    
    // If you’re here, the given index is larger
    // than the number of elements in the list.
    return false
}

The classes so far

Let’s take a look at the complete Node and LinkedList classes so far, in both Python and JavaScript.

Python

# Python

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


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:
            result += f'{current_node}\n'
            current_node = current_node.next
            
        return result.strip()
    
    def add_last(self, value):
        new_node = Node(value)

        # 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
        
    def __len__(self):
        count = 0
        current_node = self.head
        
        # Traverse the list, keeping count of 
        # the nodes that you visit,
        # until you’ve gone past the last node.
        while current_node:
            current_node = current_node.next
            count += 1
            
        return count        
        
    def get_element_at(self, index):
        current_index = 0
        current_node = self.head
        
        # Traverse the list, keeping count of 
        # the nodes that you visit,
        # until you’ve reached the specified node.        
        while current_node:
            if current_index == index:
                # We’re at the node at the given index!
                return current_node.data
            
            # We’re not there yet...
            current_node = current_node.next
            current_index += 1
    
        # If you’re here, the given index is larger
        # than the number of elements in the list.
        return None
    
    def set_element_at(self, index, value):
        current_index = 0
        current_node = self.head
        
        # Traverse the list, keeping count of 
        # the nodes that you visit,
        # until you’ve reached the specified node.  
        while current_node:
            if current_index == index:
                # We’re at the node at the given index!
                current_node.data = value
                return True
            
            # We’re not there yet...
            current_node = current_node.next
            current_index += 1
            
        # If you’re here, the given index is larger
        # than the number of elements in the list.
        return False

JavaScript

// JavaScript

class Node {
    
    constructor(data) {
        this.data = data
        this.next = null
    }
    
    toString() {
        return this.data.toString()
    }
    
}


class LinkedList {
    
    constructor() {
        this.head = null
    }
    
    toString() {
        if (!this.head) {
            return('Empty list.')
        }
        
        let output = ""
        let currentNode = this.head

        while (currentNode) {
            output += `${currentNode.data.toString()}\n`
            currentNode = currentNode.next
        }
        
        return output.trim()
    }
    
    addLast(value) {
        let newNode = new Node(value)
        
        // If the list is empty,
        // point `head` to the newly-added node
        // and exit.
        if (this.head === null) {
            this.head = newNode
            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...
        let currentNode = this.head
        while (currentNode.next) {
            currentNode = currentNode.next
        }
        
        // If you’re here, `currentNode` is
        // the last node in the list.
        // Point `currentNode` at
        // the newly-added node.
        currentNode.next = newNode
    }
    
    getCount() {
        let count = 0
        let currentNode = this.head
        
        // Traverse the list, keeping count of 
        // the nodes that you visit,
        // until you’ve gone past the last node.
        while (currentNode) {
            currentNode = currentNode.next
            count++
        }
        
        return count
    }
    
    getElementAt(index) {
        let currentIndex = 0
        let currentNode = this.head
        
        // Traverse the list, keeping count of 
        // the nodes that you visit,
        // until you’ve reached the specified node.     
        while (currentNode) {
            if (currentIndex === index) {
                // We’re at the node at the given index!
                return currentNode.data
            }
            
            // We’re not there yet...
            currentNode = currentNode.next
            currentIndex++
        }
        
        // If you’re here, the given index is larger
        // than the number of elements in the list.
        return null
    }
    
    setElementAt(index, value) {
        let currentIndex = 0
        let currentNode = this.head
        
        // Traverse the list, keeping count of 
        // the nodes that you visit,
        // until you’ve reached the specified node.     
        while (currentNode) {
            if (currentIndex === index) {
                // We’re at the node at the given index!
                currentNode.data = value
                return true
            }
            
            // We’re not there yet...
            currentNode = currentNode.next
            currentIndex++
        }
        
        // If you’re here, the given index is larger
        // than the number of elements in the list.
        return false
    }

}

Wait…this “linked list” thing is beginning to look like a Python or JavaScript array, but not as fully-featured. What’s going on here?

The truth about linked lists

Here’s the truth: there’s a better-than-even chance that you’ll never use them…directly.

If you program in most languages from the 1990s or later (for example, Python was first released in 1991, PHP’s from 1994, Java and JavaScript came out in 1995), you’re working with arrays — or in Python’s case, lists, which are almost the same thing — that you can you can add elements to, remove elements from, perform searches on, and do all sorts of things with.

When you use one of these data types in a modern language…

• Python lists or a JavaScript arrays
• Dictionaries, also known as objects in JavaScript, hashes in Ruby, or associative arrays
• Stacks and queues
• React components

…there’s a linked list behind the scenes, moving data around by traversing, adding, and deleting nodes. There’s a pretty good chance that you’re indirectly using linked lists in your day-to-day programming; you’re just insulated from the details by layers of abstractions.

So why do they still pose linked list challenges in coding interviews?

History plays a major factor.

In older languages like FORTRAN (1957), Pascal (1970), and C (1972), arrays weren’t dynamic, but fixed in size. If you declared an array with 20 elements, it remained a 20-element array. You couldn’t add or remove elements at run-time.

But Pascal and C supported pointers from the beginning, and pointers make it possible to create dynamic data structures — the kind where you can add or delete elements at run-time. In those early pre-web days, when programming languages’ standard libraries weren’t as rich and complete as today’s, and you often had to “roll your own” dynamic data structures, such as trees, queues, stacks, and…linked lists.

If you majored in computer science in the ’70s, ’80s, and even the ’90s, you were expected to know how to build your own dynamic data structures from scratch, and they most definitely appeared on the exam. These computer science majors ended up in charge at tech companies, and they expected the people they hired to know this stuff as well. Over time, it became tradition, and to this day, you’ll still get the occasional linked list question in a coding interview.

What’s the point in learning about linked lists when we’re mostly insulated from having to work with them directly?

For starters, there’s just plain old pragmatism. As long as they’re still asking linked list questions in coding interviews, it’s a good idea to get comfortable with them and be prepared to answer all manner of questions about algorithms and data structures.

Secondly, it’s a good way to get better at the kind of problem solving that we need in day-to-day programming. Working with linked lists requires us to think about pointers/references, space and time efficiency, tradeoffs, and even writing readable, maintainable code. And of course, there’s always a chance that you might have to implement a linked list yourself, whether because you’re working on an IoT or embedded programming project with a low-level language like C or implementing something lower-level such as the reconciler in React.

Coming up next

• Adding a new element to the head of a linked list
• Adding a new element at a specific place in the middle of a linked list
• Deleting a specified element of a linked list

Previously in this series

• How to solve coding interview questions: Linked lists, part 1
• 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

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

In the previous installment in the How to solve coding interview questions series, I showed you my Python solution for the challenge “Find the first NON-recurring character in a string,” which is a follow-up to the challenge “Find the first recurring character in a string.”

A couple of readers posted their solution in the comments, and I decided to take a closer look at them. I also decided to write my own JavaScript solution, which led me to refine my Python solution.

“CK”’s JavaScript solution

The first reader-submitted solution comes from “CK,” who submitted a JavaScript solution that uses sets:

// JavaScript

function findFirstNonRepeatingChar(chars) {
    let uniqs = new Set();
    let repeats = new Set();
    
    for (let ch of chars) {
        if (! uniqs.has(ch)) {
            uniqs.add(ch);
        } else {
            repeats.add(ch);
        }
    }
    
    for (let ch of uniqs) {
        if (! repeats.has(ch)) {
            return ch;
        }
    }
    
    return null;
}

The one thing that all programming languages that implement a set data structure is that every element in a set must be unique — you can’t put more than one of a specific element inside a set. If you try to add an element to a set that already contains that element, the set will simply ignore the addition.

In mathematics, the order of elements inside a set doesn’t matter. When it comes to programming languages, it varies — JavaScript preserves insertion order (that is, the order of items in a set is the same as the order in which they were added to the set) while Python doesn’t.

CK’s solution uses two sets: uniqs and repeats. It steps through the input string character by character and does the following:

• If uniqs does not contain the current character, it means that we haven’t seen it before. Add the current character to uniqs, the set of characters that might be unique.
• If uniqs contains the current character, it means that we’ve seen it before. Add the current character to repeats, the set of repeated characters.

Once the function has completed the above, it steps through uniqs character by character, looking for the first character in uniqs that isn’t in repeats.

For a string of length n, the function performs the first for loop n times, and the second for loop some fraction of n times. So its computational complexity is O(n).

Thanks for the submission, CK!

Dan Budiac’s TypeScript solution

Dan Budiac provided the second submission, which he implemented in TypeScript:

// TypeScript

function firstNonRecurringCharacter(val: string): string | null {

    // First, we split up the string into an
    // array of individual characters.
    const all = val.split('');

    // Next, we de-dup the array so we’re not
    // doing redundant work.
    const unique = [...new Set(all)];

    // Lastly, we return the first character in
    // the array which occurs only once.
    return unique.find((a) => {
        const occurrences = all.filter((b) => a === b);
        return occurrences.length === 1;
    }) ?? null;

}

I really need to take up TypeScript, by the way.

Anyhow, Dan’s approach is similar to CK’s, except that it uses one set instead of two:

1. It creates an array, all, by splitting the input string into an array made up of its individual characters.
2. It then creates a set, unique, using the contents of all. Remember that sets ignore the addition of elements that they already contain, meaning that unique will contain only individual instances of the characters from all.
3. It then goes character by character through unique, checking the number of times each character appears in all.

For a string of length n:

• Splitting the input string into the array all is O(n).
• Creating the set unique from all is O(n).
• The last part of the function features a find() method — O(n) — containing a filter() method — also O(n). That makes this operation O(n²). So the whole function is O(n²).

Thanks for writing in, Dan!

My JavaScript solution that doesn’t use sets

In the meantime, I’d been working on a JavaScript solution. I decided to play it safe and use JavaScript’s Map object, which holds key-value pairs and remembers the order in which they were inserted — in short, it’s like Python’s dictionaries, but with get() and set() syntax.

// JavaScript

function firstNonRecurringCharacter(text) {
    // Maps preserve insertion order.
    let characterRecord = new Map()

    // This is pretty much the same as the first
    // for loop in the Python version.
    for (const character of text) {
        if (characterRecord.has(character)) {
            newCount = characterRecord.get(character) + 1
            characterRecord.set(character, newCount)
        } else {
            characterRecord.set(character, 1)
        }
    }

    // Just go through characterRecord item by item
    // and return the first key-value pair
    // for which the value of count is 1.
    for (const [character, count] of characterRecord.entries()) {
        if (count == 1) {
            return character
        }
    }

    return null
}

The final part of this function takes an approach that’s slightly different from the one in my original Python solution. It simply goes through characterRecord one key-value pair at a time and returns the key for the first pair it encounters whose value is 1.

It remains an O(n) solution.

My revised Python solution

If I revise my original Python solution to use the algorithm from my JavaScript solution, it becomes this:

# Python

def first_non_recurring_character(text):
    character_record = {}
    
    # Go through the text one character at a time
    # keeping track of the number of times
    # each character appears.
    # In Python 3.7 and later, the order of items
    # in a dictionary is the order in which they were added.
    for character in text:
        if character in character_record:
            character_record[character] += 1
        else:
            character_record[character] = 1
    
    # The first non-recurring character, if there is one,
    # is the first item in the list of non-recurring characters.
    for character in character_record:
        if character_record[character] == 1:
            return character

    return None

This is also an O(n) solution.

Previously in this series

• 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