Chapter 8 - Can't find DoublyLinkedList class in the Sources folder

đź“š Official Books Data Structures & Algorithms in Swift
1

Hi in the example of the Doubly linked list implementation it mentions there is a DoublyLinkedList class in the Sources folder but I cannot see it, only the Array one.

2

I also cannot find this file in source

3

@jomoka Can you please help with this when you get a chance? Thank you - much appreciated! :]

4

@mkashiwagi
Sorry for the late reply! I double checked and the doubly linked list class is there. Did you check chapter 8 (Queue) queue project?

5

@jomoka
Any specific reason of using “DoublyLinkedList” for “Queue” implementation, instead of “Singular LinkedList”?

1 Like
6

@pulkitap

Depends on your use case. If you think about a normal list or array.

A doubly linked list would be useful if you wanted to remove an element at the start or end of the queue. (Since you have the reference to the tail node)

If you used a singly linked-list, to insert or remove elements, you would have to traverse the list till you reach the index to add/remove the node (since a node only has reference to the next node in a singly linked list)

Another example if you used a singly linked list, you can only traverse the list from the start.
Where as if you used a doubly linked list, you will be able to traverse the list from the start or backwards from the end.

Picking the right data structure, you can consider complexity (big O Notation), order of elements(how to traverse the data structure), usage (How will your queue, or data structure will be used), performance (how fast is it to perform a particular function), memory (storage of data)

Hope this is helpful!

7

@jomoka

For Queue implementation, we “enqueue” from tail and “dequeue” from head. And in singly linked list also, we have both, i.e. head as well as tail.
Although, we can also implement it with doubly list, but doubly list requires much more space as compare to singly list.

2 Likes
8

@pulkitap yes I agree doubly linked list requires more space due to the additional node references. If you just want a normal queue with standard fifo ordering. Then a single linked list works for this standard use case.

If all you care about is removing from the head then a single linked list is all you need.

It just depends on your use case.