Recently I have started my journey of solving interview problems on Leetcode. To help me further build my knowledge on these practice problems I will be writing blog posts to explain my solution. This post describes what a Singly Linked List is and how I designed one in C#. I choose C# for this interview because Microsoft Visual Studio’s debugger is easy to use and makes visualizing the data as I modify it easier. You can take these concepts and apply them to any programming language. This post is language agnostic however it uses C# for the code examples.

What is a Linked List?

A Linked List is a data structure where you have a collection of objects called nodes, each node links to the next object. Unlike an array, elements are not indexed and do not require a contiguous block of memory. Each object stores a pointer to the next object meaning you can allocate memory anywhere when adding a new object. This makes inserting and deleting elements efficient.

Why should you use a Linked List?

This means to modify an array a lot of copying can occur when inserting into an existing array or when increasing the size if other elements are next to it. If you find yourself frequently inserting into an array, modifying it (or its objects), a Linked List will save time by not copying memory to new locations.

What are the disadvantages of using a Linked List?

Unlike an array, a Linked List is not indexed, and memory is allocated dynamically, as it does not use a contiguous block of memory you cannot use the initial memory location, do simple math to find the location of a specific index, and quickly add it. Rather you have to traverse the Linked List. This means accessing the elements in order until you find the one you need. You also cannot traverse reversely (from end to start) unless you implement a doubly linked list which involves each node having two pointers increasing memory utilization. In constrained environments this may be a problem as it can use more memory than an array would.

When should you use a Linked List vs an Array?

In general if you plan on frequently inserting and deleting elements into a collection you should use a Linked List whereas if you mostly read the collection and modifying is rare or if you are in a memory constrained environment an array is a better choice. In general arrays are faster for reading and random access whereas Linked Lists are faster for insertion and deletion of elements in a collection.

Differences between a LinkedList on a Managed Language vs an Unmanaged Language

When using a language such as C#, Java, or Rust memory is managed for you either by the runtime or at compile time. This means once there are no more references to an object it is automatically deleted. In an unmanaged language such as C or C++ you will have to free memory after deleting an object or risk a memory leak over time. Additionally, consider using smart pointers where possible to reduce the risks of use-after-free, etc. In general free-ing and allocating memory this way is much more efficient than copying an array with your changes to a new contiguous block of memory.

Design Patterns

It’s worth noting a design pattern I use. I use a technique called fail-fast. This means I add guard clauses which check if an index or other input is invalid and immediately return an error before an exception can occur due to undefined or buggy behavior.

Defining the Linked List

To make a few operations easier I first defined a class called MyLinkedClass. This includes access to the list head, list tail, and a size integer. It is possible to traverse the list and count that way however storing the size saves time and assists with guard clauses. For example, I cannot attempt to access an index larger than the list. Is it worth noting that the list is empty by default and that the head/tail are both a null reference until the first object is added. In the methods of this list I check if the head is null, however if you want you could instead check the size of this list. I end up with an object like this which stores this metadata and I can add each method to it.

public class MyLinkedList
    {
        public MyLinkedListNode head;
        public MyLinkedListNode tail;
        public int size = 0;

        public MyLinkedList(){}
    }

Defining the Node of a Linked List

As alluded to above, I have a class defining the nodes MyLinkedListNode. Your node will have two fields. A data field with data of whatever your list is of. In my example it will be a list of integers. Although in practice this could be a list of any type of object. I end up with a class like this which defines each node.

public class MyLinkedListNode
    {
        public int data;
        public MyLinkedListNode next;

        public MyLinkedListNode(int val)
        {
            data = val;
        }
    }

Get node of an index from a Linked List

The first method I will add will let us get the node of a given index from a Linked List. For the purpose of this project I will assume nodes are 0-index and an invalid index will return -1. Once checked, define a variable currentNode and set to the head node. On each iteration first check if I (the iterator) is equal to the requested index, if so break out of the loop, otherwise set current node to the next node. Once you reach the requested index, break out of the loop and return the node to the calling function.

public int Get(int index)
        {
            if (index > (size - 1) || index < 0)
            {
                return -1;
            }
            else
            {
                MyLinkedListNode currentNode = head;

                for (int i = 0; i < index; i++)
                {
                    if (i == index)
                    {
                        break;
                    }
                    else
                    {
                        currentNode = currentNode.next;
                    }
                }

                return currentNode.data;
            }
        }

Add node to the head of a Linked List

Adding a node to the head of a Linked List is simple. First check if this is the first node in the linked list. If so set this newNode as the head and the tail. Otherwise get the first node, set new node’s next property to this current head, and update the head field of the linked list. Next increment the size check.

public void AddAtHead(int val)
        {
            MyLinkedListNode newNode = new MyLinkedListNode(val);

            if (head == null)
            {
                head = newNode;
                tail = newNode;
            }
            else
            {
                newNode.next = head;
                head = newNode;
            }

            size++;
        }

Add node to the tail of a Linked List

Adding a node to the head of a Linked List is simple. First check if this is the first node in the linked list. If so, set this newNode as the head and the tail. Otherwise get the last node, set it’s next property to this node, and update the tail field of the linked list. Next increment the size check.

 public void AddAtTail(int val)
        {
            MyLinkedListNode newNode = new MyLinkedListNode(val);
            if (head == null)
            {
                head = newNode;
                tail = newNode;
            }
            else
            {
                tail.next = newNode;
                tail = newNode;
            }

            size++;
        }

Add a node before the Nth index

Here things get a little more complicated. First do the usual index safety check. If adding to the head or tail of the list call the AddToHead or AddToTail methods as they have additional position specific logic and it avoids rewriting code. After calling AddToHead or AddToTAil Return to break out of the function. Otherwise treat it as if adding a middle node. Get to node before the index (index minus one) and update it’s next pointer to the new node. Then set the new node’s index to the index node. Afterwards, increment the size count.

public void AddAtIndex(int index, int val)
        {
            if (index > size || index < 0)
            {
                return;
            }

            // Add to head
            if (index == 0)
            {
                AddAtHead(val);
                return;
            }

            if (index == size)
            {
                AddAtTail(val);
                return;
            }

            MyLinkedListNode currentNode = head;
            int i = 0;
            while (i < (index - 1))
            {
                currentNode = currentNode.next;
                i++;
            }

            MyLinkedListNode newNode = new MyLinkedListNode(val);
            MyLinkedListNode nextNode = currentNode.next;

            newNode.next = nextNode;

            currentNode.next = newNode;

            size++;
        }

Delete a node at the Nth index

This is also relatively challenging as there are special cases to consider. First add our standard index safety check. Set the current node to head and define a shared incrementer. In this case while loops are more succinct and the the incrementer is only used once then the function breaks with a return. If deleting the headway just set the current head to head.next, and decrement the size count. When deleting the tail, get the index before the tail (size-2), set it’s next pointer to null, and update the tail pointer in the MyLinkedList object. If deleting a middle node, get the node before it (index-1) and set it’s next pointer to next node’s next pointer. This clears all references to the object in a managed language like Java or C# this deletes the object once the garbage collector runs, in C++ or other unmanaged languages if you choose to not use smart pointers be sure to free the memory before deleting the references. Once the node is deleted decrement the size counter and you’re all done.

public void DeleteAtIndex(int index)
        {
            if (index >= size || index < 0)
            {
                return;
            }

            MyLinkedListNode currentNode = head;
            int i = 0;

            // Delete Head
            if (index == 0)
            {
                head = head.next;
                size--;
                return;
            }

            // Delete Tail
            if (index == (size - 1))
            {
                while (i < (index - 1))
                {
                    currentNode = currentNode.next;
                    i++;
                }
                tail = currentNode;
                currentNode.next = null;
                size--;
                return;
            }

            // Delete middle node
            while (i < (index - 1))
            {
                currentNode = currentNode.next;
                i++;
            }
            currentNode.next = currentNode.next.next;
            size--;
        }
    }

Current flaws in my solution

My solution still has some final bugs to work out. For example, deleting the head or tail when there is not an additional node in the list may cause a runtime exception. Leetcode does not yet test for every possible regression but I look forward to them updating this challenge in the future.

Challenge Problem

Looking for a challenge to expand upon my solution and test your knowledge? Define a method to modify the node as a given index.

TheLinked List is now complete

Now I’ve finalized the solution to the Linked List. I hope you were able to learn a bit from this blog post and this challenge, while difficult, was a great learning experience and I hope to write about future challenges soon.

Final Solution

Below is my final solution written in C#

using System;
using System.Collections.Generic;
using System.Text;

namespace MyLinkedList
{
	public class MyLinkedListNode
    {
        public int data;
        public MyLinkedListNode next;

        public MyLinkedListNode(int val)
        {
            data = val;
        }
    }
	
    public class MyLinkedList
    {
        public MyLinkedListNode head;
        public MyLinkedListNode tail;
        public int size = 0;

        public MyLinkedList()
        {

        }

        public int Get(int index)
        {
            if (index > (size - 1) || index < 0)
            {
                return -1;
            }
            else
            {
                MyLinkedListNode currentNode = head;

                for (int i = 0; i < index; i++)
                {
                    if (i == index)
                    {
                        break;
                    }
                    else
                    {
                        currentNode = currentNode.next;
                    }
                }

                return currentNode.data;
            }
        }

        public void AddAtHead(int val)
        {
            MyLinkedListNode newNode = new MyLinkedListNode(val);

            if (head == null)
            {
                head = newNode;
                tail = newNode;
            }
            else
            {
                newNode.next = head;
                head = newNode;
            }

            size++;
        }

        public void AddAtTail(int val)
        {
            MyLinkedListNode newNode = new MyLinkedListNode(val);
            if (head == null)
            {
                head = newNode;
                tail = newNode;
            }
            else
            {
                tail.next = newNode;
                tail = newNode;
            }

            size++;
        }

        public void AddAtIndex(int index, int val)
        {
            if (index > size || index < 0)
            {
                return;
            }

            // Add to head
            if (index == 0)
            {
                AddAtHead(val);
                return;
            }

            if (index == size)
            {
                AddAtTail(val);
                return;
            }

            MyLinkedListNode currentNode = head;
            int i = 0;
            while (i < (index - 1))
            {
                currentNode = currentNode.next;
                i++;
            }

            MyLinkedListNode newNode = new MyLinkedListNode(val);
            MyLinkedListNode nextNode = currentNode.next;

            newNode.next = nextNode;

            currentNode.next = newNode;

            size++;
        }

        public void DeleteAtIndex(int index)
        {
            if (index >= size || index < 0)
            {
                return;
            }

            MyLinkedListNode currentNode = head;
            int i = 0;

            // Delete Head
            if (index == 0)
            {
                head = head.next;
                size--;
                return;
            }

            // Delete Tail
            if (index == (size - 1))
            {
                while (i < (index - 1))
                {
                    currentNode = currentNode.next;
                    i++;
                }
                tail = currentNode;
                currentNode.next = null;
                size--;
                return;
            }

            // Delete middle node
            while (i < (index - 1))
            {
                currentNode = currentNode.next;
                i++;
            }
            currentNode.next = currentNode.next.next;
            size--;
        }
    }
}