Queue With Doubly Linked List in Swift

      4 Comments on Queue With Doubly Linked List in Swift

Queue is a simple and widely used data structure that operates on a FIFO principle. In this article we'll implement a queue with doubly linked list in swift

Queue is a simple and widely used data structure that operates on a first in first out principle. Sometimes you can hear them being referred to as FIFO (first in first out) queues. In this article we’ll implement a queue with doubly linked list in swift. A linked list is a very efficient way of implementing a queue. You can implement a queue using an ordinary linked list, but in this article we’ll explore the concept behind a doubly linked list and see one possible example on how to use it. We’ll be using what we learn today in one of the upcoming articles on graph algorithms.

Doubly Linked List

We covered linked lists in the article on how to implement a stack using a linked list, check it out if you’re interested. In this article we’ll reiterate some of the important concepts already mentioned. So you don’t have to read that article to understand what we’re talking about here.

A doubly linked list data structure is very similar to the linked list. In a linked list every item in the list has a pointer to the next item. In a doubly linked list every item has a pointer to the next item and to the previous item. Think of a doubly linked list as two normal linked lists that point in opposite directions.

Check it out on an diagram:

Our doubly linked list will accept a generic type and store it in the ‘value’ variable. It will also have optional variables to the previous and next nodes. We’ll have pointers to the first and last elements of the list, called ‘head’ and ‘tail’.

Enqueue

We’ll manipulate some pointers when we add, or enqueue, an item into our queue. Let’s imagine we’re adding a new node into the queue:

When we add ‘Node6’, we have to modify ‘Node5’ and set its ‘next’ variable to point to ‘Node6’. The ‘tail’ is actually pointing to ‘Node5’, the ‘tail’ will always point to the last element in the list. So we’re actually accessing ‘Node5’ via the ‘tail’ pointer. We also need to modify ‘Node6’ and have its ‘previous’ variable point back to ‘Node5’. Next thing we need to do is update the ‘tail’ to point to ‘Node6’, which is now the last element in the list.

The thick red arrows are pointers we modified when inserting a new element.

Dequeue

Dequeue is an action of removing an item from the queue. Dequeuing is even simpler than enqueuing. We fetch the current ‘head’ of the list and set the ‘head’ pointer to point to the next element in the list.

Check it out on a diagram:

These are the basic concepts of a queue. Let’s see how to implement them…

Implementation

In order to save the elements into our list, we’ll use an inner class called ‘Node’. It’s a very simple class that only has a couple of properties and it’s private:

We’ll be using generics throughout our example.

Our main class will hold a reference to the current head and the current tail:

Obviously, we’ll be using the ‘head’ and ‘tail’ to enqueue and dequeue items. But we can also use them for other operations. As you can see from the code listing above, we’re using the ‘head’ pointer to check if the list is empty, and to get the number of elements in the list.

Enqueue

In the enqueue function, we check to see if the element is already in the list. If it’s not, we create a new node and swap the pointers around. Just like we explained on the diagram above:

At the end of the method we’re checking to see if the ‘head’ is nil. That would mean that our list is empty and the element we’re just inserting is the first element in the list. In that case we need to set the ‘head’ pointer to point to the same element that the ‘tail’ is pointing to.

Dequeue

Dequeue is even simpler:

We just move the ‘head’ pointer on to the next element in the list. If the new ‘head’ pointer is nil, that means we’ve reached the end of our list, so we nil out the ‘tail’ pointer as well. At the end of the function we return the value stored in the node that we just removed from the list.

Contains

In the ‘enqueue’ function we were checking to see if an element was already in the list. We have a small utility function for this:

We start with the ‘head’ and save it into a ‘current’ variable. In the loop we’re updating the ‘current’ pointer to point to the next element in the list. The loop will end when it reaches the end of the list. If we find the element, in the meantime, we’ll return from the function and exit the loop.

Traversing The Doubly Linked List

You’ve seen some examples on how to traverse the list in the code examples above. You can also find two computed variables that we have created specifically to demonstrate the traversals. The variables ‘elements’ and ‘reversedElements’ will return all the items in the queue in order, or in the reverse order.

To return an array of elements stored in the list, we start with the head pointer and start moving down the chain to the next pointer until we reach the end of the list:

This code should look familiar to you by now.

We can do one interesting thing with a doubly linked list. We can reverse this array of elements really easily. As you’ve probably guessed, we’ll do almost the exact same thing we did in the ‘elements’ variable, only in reverse:

Obviously, instead of saving the ‘next’ pointer, we’re saving the ‘previous’ pointer.

Testing It Out

Let’s start enqueuing ๐Ÿ™‚ We create our queue with an ‘Int’ as a type. You can use any type you want, the queue is generic. After that, we just start enqueueing and dequeueing items:

And the console output of our little test run is:

That’s it, you know how to use doubly linked lists to create queues ๐Ÿ™‚

Conclusion

Linked lists are a very useful and efficient data structure. Doubly linked lists are giving us the added benefit of traversing the list in both directions. Admittedly, we could have implemented our queue using a simple linked list, but we did it with a doubly linked list to demonstrate one of its possible usages.

Because of their nature, they’re perfect for implementing queues. A queue is a very old and a very important data structure. We’re covering it here because it will help you understand some of the algorithms we’ll cover in the future. And it’s always nice to know how things work, right ๐Ÿ™‚

I hope you had some fun and that you’ve learned something new today ๐Ÿ™‚ You can find all the code in the GitLab repo along with all the code snippets.

As always… Have a nice day ๐Ÿ™‚
~D;

More resources

4 thoughts on “Queue With Doubly Linked List in Swift

    1. Dejan Agostini Post author

      Hi millie,

      Thank you very much ๐Ÿ™‚ Sure I can, but it can take some time before I write those. I see a lot of assignments posted on that page. I’ll add it to my list of future articles. Thanks for the suggestion.

      Have a nice day ๐Ÿ™‚
      ~D;

      Reply
  1. Pingback: 2018: Year in Review | agostini.tech

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.