Doubly Linked Lists — Swift 4

GetAtIndex, insertAtIndex, append, prepend

Doubly Linked List Diagram

This diagram represents our linked list we will be working with! Each rectangle represents a node which has 3 slots in it. The middle slot represents value of the node, the left slot represents the previous pointer, and the right slot represents the next pointer. In addition to that, our linked list will keep count of a head and a tail.

Make sure to check out my singly linked list article here for previous references!😃 There, I go in depth of how to create a singly linked list class as well as a node class to start implementing the different methods within it.

How are doubly linked lists different from singly linked lists? Doubly has a previous pointer which points to its previous node! This can be favorable based upon what type of actions we want to do on our data structure which we will go into furthermore in this article.⏬✔️

Table of Contents

1. Pros and Cons of a Doubly LinkedList
2. Creating the Node Class Using Generics
3. Creating the LinkedList Class Using Generics
4. Methods in Doubly LinkedList class:
   • Append
   • Prepend
   • Items
   • Get node at index
   • Insert at index
5. Examples of Using Doubly Linked List in Real Life
6. Stretch Challenges!
   • Delete all nodes in the linked list
   • Inserting a node after a specific node
   • Print out the linked list in order
   • Print out the linked list in reverse order

Pros and Cons of a Doubly Linked List

Node class

As you can see in this Node class above, each node holds exactly 3 variables; a value(data), a next which will hold the node after it, and a prev which will hold the node before it.

Generics

Generic code enables you to write flexible, reusable functions and types that can work with any type, subject to requirements that you define. — Swift Docs

Swift Array and Dictionary types are generic collections.
In our case, we would also want to create our linked list class using generics so we can create nodes with whichever type we want such as Integers, Floats, Doubles, Strings, Tuples, or even our own Models!

Linked List class

This linked list class will contain properties of the head, tail, and size. This size value will be helpful when we want to find the length of the entire linked list.

Now that we have our foundation written down, we can start implementing different methods to our LinkedList class👇🏼👇🏼👇🏼

Methods in DoublyLinkedList class

I highly recommend to try coding these functions or writing down pseudocode before looking at the solutions!! 📝 ✍🏼
Don’t forget to keep account for both next pointers and previous pointers while implementing the following methods.

• Append

Adding a new item to the end of the linked list.

This is where self.size will be used and updated!

1. Create a new node from the value passed in the parameter
2. Create a guard statement to make sure the head value is not nil in order to continue lines after 12.
3. If the head is nil, meaning our linked list is empty, we initialize the head and tail to be the new node created on line 3.
4. Now that we are sure our linked list isn’t empty, we know there is a tail value. So we set the tail’s next pointer to be newNode. We also give newNode a previous pointer to our tail. Lastly, is to update the tail to become the newNode.
5. Incrementing our size by 1 since we just added a new member to our list family. 😲😄

• Prepend

Adding a new item to the beginning of the linked list.

1. Create a new node from the value parameter
2. Using a guard statement to make sure there is a head value or else lines 8–11 will get executed.
3. Initializing our head and tail to be newNode without having to change or add any pointers.
4. Now that the case of the linked list isn’t empty, we go ahead and do the following:
   Setting the head’s previous pointer to be newNode
   Giving newNode a next pointer to our head
   And finally updating the head to our first node(newNode)
5. Incrementing our size by 1 since we just added a new member to our list family. 😲😄

• Items

Returning all items in the linked list as an array of values sorted from the head to tail.

1. If the linked list is empty, we return an empty array
2. Create an empty array where we will be appending all the node values
3. Loop through the linked list starting from self.head.
   In the while loop we first append the current node’s value, and then update curr to become the next node.
4. Once we hit the end of the linked list, we can return the array which is now filled with all the values of nodes in the linked list!

• Insert at index:

Inserting a node at the given position we would want to insert it at.

Don’t be alarmed by this huge chunk of code! We’ll get through this together step by step and see how this magic all happens.🔗🔗

1. We first need to check the input index must be in range of our items in the linked list. Let’s say we have 3 nodes in our linked list, the indexes we can only go up to is 3. If given index is larger than 3, we’ll return out of the function with a print statement saying the index is out of bounds.

⚠️Before going into steps 2, 3, and 4, we must know there are 3 possibilities of where we want to insert the node.
— Inserting at the front: changing self.head
— Inserting at the end: changing self.tail
— Inserting between 2 nodes: changing next and previous reference pointers.
We would want to check for these cases separately so our code is more efficient!

2. index == 0 means we’re inserting in front of our list.
Here’s what’s going on in the prepend method. (Order matters!☝🏼)
- Set the current head’s previous pointer to our newNode
- Set our newNode’s next pointer to the self.head. We do not need to set newNode’s previous pointer since it’s set by default to nil
- Change the head to be our newNode!!

3. index == self.size means we‘re inserting to the end of our list.
Here’s what’s going on in the append method. (Order matters!☝🏼)
- Set the current tail’s next pointer to our newNode
- Set our newNode’s previous pointer to the current tail
- then we change the tail!

4. index is somewhere between 2 nodes which means we’ll have to traverse the linked list until we get to the desired index.
- 1: Create a new node with the desired value
- 2: Loop through the linked list, updating our curr node to become the node right at the index we would want to insert newNode
- 3: Attaching our current’s previous’s next pointer to newNode.
And also attaching our newNode’s previous pointer to our current’s previous node.
Now we can reassign current’s previous pointer to newNode.
And our newNode’s next pointer to the current node.
- 4: Incrementing self.size by 1. And we’re only doing this step in the else clause because both append and prepend methods already cover the incrementation.

• Get node at index

This method simply returns the value of the node at the given index.

1. Checks that the input index is in the range from 0 to self.size. Or else, we will return nil since there are no values at that invalid index.
2. start from self.head and traverse through the linked list. If say the index was 1, then we update ‘curr’ to the next node 1 time. Likewise, if the index was 0, the code won’t execute the for loop at all (0 times).
3. Lastly, we return the value of that current node because it is correctly at the index we are looking for.

Examples of Using Doubly Linked Lists in Real Life

• Creating a music playlist 🎶🎵🎶. This article even gives you a coding example on how to implement your own class!
• Drawing from a deck of cards. The nodes can represent the rank, and color of one card.
• And finally, the undo and redo functionality on a browser!! This is where you can reverse the node to get to the previous page.

Stretch Challenge Methods

1. deleteAll(): Deletes all the nodes in the linked list
2. insertAfter(_ value: T, after: T): Takes in the value you want to insert and, a value of the node you want to insert right after
3. listForward(): prints out the linked list node’s values from front to back
4. listBackward(): prints out the linked list node’s values from back to front

I hope you found value in this blog post and I highly encourage you to try implementing all these methods in a Swift playground

Thank you for checking out this blog post!

If you have any questions or comments, please feel free to reach out to me. And don’t forget to give this article some claps! 👏🏼*up to 50x*👏🏼 if you found it helpful.