Data Structure in Swift (Linked List) — Part 2

Nitin Aggarwal

5 min readJan 30, 2020

In the first part of this series, we learned about Array and Dictionary. Now let’s move on Linked List.

What is Linked List?

A linked list is a linear data structure in which the elements are linked by holding the reference of the next node (and of the previous node for Doubly Linked List).
In a linked list, elements are not stored at contiguous memory locations it means we cannot access any element directly using the subscript operator i.e. [].
In a linked list, each element contains the data (or value) field and reference of the next element in the list.

Types of Linked List:

Singly Linked List
Doubly Linked List
Circular Linked List

So let’s move to understand the Singly Linked List in this story.

As each node contains some fields to hold the information in a linked list, so let’s see first how we can create a node in Swift.

Full Code

Let’s understand the above code first before going further.

Created a class named ‘Node’ with some variables like value and reference of Node type to keep the reference of the next node.
Here ‘T’ (Generic) basically used to store any kind of information like String, Int, Double, etc.
Created custom initializer with value and reference of the next node.
Computed the default variable ‘description’ to get the result in our way while displaying the node. Don’t worry about it, we will see the example of it later.
In last, overloaded the Equal operator to compares two nodes.

So we have just created a class Node to hold the information in the list. Next, we will create a struct to keep all the nodes.

Let’s understand the above code first before going to perform the operations on the list.

In the above code, we created a head and tail. The head will point the starting point or node of the list and tail will point the last point or node of the list.

Why we are using head and tail in Linked List -> Actually, all the nodes basically are linked by references. To traverse the list or perform any operation, we have to hold the starting and ending point.

1. How to add a node at the front to the list?

Remember that: Structures and enumerations are value types. By default, the properties of a value type cannot be modified from within its instance methods. However, if you need to modify the properties of your structure or enumeration within a particular method, you can opt in to mutating behavior for that method.

2. How to append a node at the last to the list?

3. How to fetch a node from a specific position from the list?

4. How to get the number of nodes in the list?

5. How to insert a new node at a specific position in the list?

6. How to pop a node from the list?

6. How to remove a last node from the list?

6. How to remove a node from a specific position in the list?

Wow…so we learned all the insertion and deletion operations which we can perform on the Linked List and we covered also that how we can traverse the Linked List.

Now let’s see about the time complexity for all the insertion operations.

Push: Adding a new node at the first in the list. So the time complexity will be O(1)
Append: Adding a new node at the last in the list. So the time complexity will be O(1)
Insert: Adding a new node at the specific position in the list. So the traversing will be performed to find out the node just before the given index, so the time complexity will be O(n); n = insertion index

The time complexity for all the deletion operations.

Pop: Removing the node from the first in the list. So the time complexity will be O(1)
deleteLast: Removing the node from the last in the list. But to remove the last, we have to traverse in the list till tail, so the time complexity will be O(n)
removeAt: Removing the node from a specific position in the list. So the traversing will be performed to find out the node just before the given index, so the time complexity will be O(n); n = deletion index

When to use Linked List?

When the size of the data is not known beforehand in Linked List.

When not to use Linked List?

When you are dealing with search operations with a large number of data, then Linked List is not a good choice. Also, it’s using the old way (loop) for traversal i.e. very slow.

Let’s see the examples which are run on Swift Playground with the above code.

Note: In both the examples, we are just printing the variable name like ‘numberLinkedList’ or ‘stringLinkedList’, so it’s giving me all the values linked with the next node and so on. To do this, Node class has conforms the ‘CustomStringConvertible’ protocol by overriding the ‘description’ property.

GitHub Source Code

So, I hope you really enjoyed this story and learned something about Linked List. If YES, don’t forget to Clap on it 👏🏻