Linked Lists in Swift: A Deep Dive into the Fundamentals and Best Practices

A linked list is a linear data structure that consists of a sequence of nodes, where each node stores a reference to an object and a reference to the next node in the sequence. Linked lists are a dynamic data structure, meaning that the number of nodes in the list can grow or shrink as needed during the execution of a program.

In Swift, we can implement a linked list by creating a Node class that stores a value and a reference to the next node. Here's an example of a basic Node class implementation in Swift:

The value property is used to store the value of the node, and the next property is used to store a reference to the next node in the list. The next property is optional because the last node in the list may not have a reference to a next node.

We can then create a LinkedList class that will hold a reference to the first node in the list (called the head) and provide methods for adding, removing, and inserting nodes into the list.

Here's an example of a LinkedList class implementation in Swift:

• The addFront(_ value: T) method adds a new node at the beginning of the list.
• The getFirst() -> T? method returns the first value or nil if the list is empty.
• The addBack(_ value: T) method adds a new node at the end of the list.
• The getLast() -> T? method returns the last value or nil if the list is empty.
• The insert(position: Int, value: T) method insert a new node at the specific position index.
• The deleteFirst() method simply removes the first node.
• The func delete(at position: Int) method deletes the node at the specific position index.
• The deleteLast() method deletes the last node object.
• The delete(value: T) method deletes a value if it exists.
• The isEmpty: Bool calculated property return a boolean whether the LinkedList in empty or not.
• The clear() method clears the LinkedList.
• The printLinkedList() prints the values within the LinkedList.

Here are a few implementation examples of the Linked List:

Linked lists have several advantages over other data structures, such as arrays. For example, inserting or deleting an element from a linked list is a constant-time operation, whereas inserting or deleting an element from an array requires shifting all of the elements after the insertion or deletion point, which can be a time-consuming operation.

Linked lists also have a few drawbacks compared to other data structures. For example, accessing an element in a linked list requires following a chain of references, which can be slower than accessing an element in an array using an index. Additionally, linked lists require more memory than arrays, because each node in a linked list requires a reference to the next node in addition to the value stored in the node.

Despite these drawbacks, linked lists are a useful data structure to have in your toolkit, and can be used effectively in a variety of situations where dynamic data structures are needed.

Learning from a Failed Technical Interview: Reflections on LinkedLists

​Now that you have a solid grasp of the fundamental workings of the LinkedList, let's explore the technical interview that didn't go as expected.

The interview question required me to create a method to determine whether a Linked List is cyclic or not.

The isCyclic method is an extension of the ListNode class, providing a static method for checking whether a linked list contains a cycle. It takes a head node as a parameter and returns a boolean value indicating whether a cycle is present or not. The method uses two pointers, slow and fast, initially pointing to the head node. It then iteratively moves the slow pointer one step at a time and the fast pointer two steps at a time through the linked list. If the two pointers ever meet, it signifies the presence of a cycle, and the method returns true. Otherwise, it continues until the fast pointer reaches the end of the list or reaches a nil next reference, indicating the absence of a cycle.