Skip to content

Implementing Doubly Linked List Using Swift 2.0

A linked list is a data structure for keeping data with an order. In this article, we will see how it actually works and how we can implement this structure in Swift 2.0. It will give us a similar functionality as an array. Later on we will try to create another data structure. Let’s start without wasting our time.

Note: I wrote this for beginner level, so if you are experienced enough and just need the code, you can find it at GitHub. I wrote the link at the end of this post.

 

HOW LINKED LIST WORKS

linked-list-types-small

We will be working with “nodes” for our linked list. A node is simply an object with a value and an indicator which shows where the next node is.

Actually we have two types of linked lists. First one is “singly linked list” which every node is aware of its next node. But it doesn’t know its previous node so we can’t iterate backwards, we can only go forward.

Second one is “doubly linked list” which we are considering in this article. Every node in a doubly linked list should be aware of its both next and previous nodes. So we can iterate forward and backwards without any problems. So let’s see how it works practically.

We will start with our Node class. Let’s create a Swift file named Node.swift in Xcode for this class, and write these lines.

Here we have our Node class. I will not go so deep with that but if you don’t know, “<T:NSObject>” will allow you to choose whatever type you want, for your “value” when you are creating your node object.

Our “value” variable will keep our data, “next” will point to its next node and “prev” will point to its previous node. So let’s move to the next part.

Second class we need is our linked list class. So let’s create a new file in Xcode and name it as MyLinkedList.swift.

So, let’s see what we have. We have our variable “count” to keep number of items we have in our list. We also have “head” and “tail” so we can see our starting and ending points for our list. We should always know these in order to access our list. You will see it better when we get into our methods. Now let’s see our methods.

  • isEmpty() is a basic boolean returning function to see if our list is empty or not.
  • addItem(value: T) will add a new item to our list.
  • insertItem(value: T, position: Int) will add a new item to a specific place.
  • removeItem(position: Int) will remove the item at the desired index.
  • replaceItem(itemToReplace: T, position: Int) will replace an item from desired index, with a new one.
  • getItemAt(position: Int) -> T? will return an item from the desired index.
  • printList() will print a list of our items.
  • printInverse() will print a list of our items, but backwards.

Important: You should always check your code with “printInverse()” because if you are working with a linked lists, it doesn’t always mean your code is correct when your head to tail printing is correct. When you are iterating forwards, you will get a correct result if your “next” indicators are correct, but your “prev” indicators might be wrong.

Let’s move on, we still have a lot to do. Now we want to be able to add items to our list. So we should implement our addItem(value: T) method.

What are we doing is quite important, and basics of working with a linked list.

  1. We are creating a new node with our desired value. (2nd line)
  2. If our list is empty, since our new node is the only node in our list, we assign our new node as head and tail. (3rd-5th lines)
  3. If our list is not empty, then we should make some different operations here. Our new node will be the last node, so previous node of it will be current tail. Now current tail is not the last node so we should also make some changes on it. Its next will point to our new node, and finally our tail will point to our recently added new node.(6th-9th lines)
  4. We successfully added our new item, so we should also increase our count.(11th line)

Now we are able to add new items to our list, but before trying, we should have our print methods, so we can see if it’s working or not.

  1. We should have our output string so we are creating that.
  2. For iterating, we need a node to keep where are we at that time. That node will be currentNode. For start it will keep our head node.
  3. We are using a while loop to see if we are at the end(If we have nil), if we are not, we will keep going.
  4. We are adding our values to our output text.
  5. currentNode = currentNode!.next, here we are moving to the next node.

I hope you can see what’s going on here. It is not very complicated, but it could be a little bit confusing at first time.

Now you can run some tests with your code, and see how it works.

Next, we should implement our printInverse() method.

It is very similar to what we recently did. Only difference is we are starting from tail and we are iterating through previous nodes.

Now you can try two different printing methods and compare them.

Let’s move on and implement our removeItem(position: Int)

I will not explain this part so deeply because it contains a lot of logic but basically we have some different cases here. Is our node, head? Or is it tail? Is it at the somewhere middle? Or it is the only one node at the list? Different operations for different cases. You should read carefully and try to understand what’s going on.

How can we insert an item to desired index? Here is our insertItem(value: T, position: Int) method.

Again, we have some different cases, if our desired index is head or not. We don’t cover the possibility of adding to tail because let’s that our list is like this: [3, 5, 7, 9] if we add “10” to index 3, our new list will be like this [3, 5, 7, 10, 9] so we didn’t add it to the end actually, and if we want to add it to index 4 we can’t, because there isn’t such an index at that time. So if we want to add an item to the tail we can use addItem() for that.

Replacing an item, it’s our replaceItem(itemToReplace: T, position: Int) method.

It is just basic iteration and changing desired nodes value. Nothing more.

Do we need to get an item from specific index. Our getitemAt(position: Int) method.

Again, basic iteration, and returning the value of the currentNode.

Finally we managed to implement everything we need. Our final code should look like this:

So, we finished. Now you can go and play with your code. You can test it, try different cases. Maybe you can improve it. If you have any questions, you can ask on comments, or you can find me from social media, links are at the right top corner. And please let me know if you find any improvements or bugs in the code.

Here you can also find this project on GitHub. It also includes a queue implementation which I will cover later on.

https://github.com/erginbilgin/Swift-Doubly-Linked-List-Implementation

3 Comments

  1. in the removeItem function, this line

    if position == 0 {
    self.head.next!.prev = self.head.prev

    applies only to a circular linked list, correct? If this is a double linked list, non circular, then the previous node of the head-> should not point to anything, since the head node->prev should be nil. Here, you have the new head pointing to previousHead->prev. This would make sense in a circular list…right? Or am I totally off.

    • Ergin Bilgin Ergin Bilgin

      Yes, you are right. Instead of that line you can use “self.head.next!.prev = nil”. Same thing applies when removing the tail.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.