Doubly Linked Lists
Another interesting application of a linked list is that it can be used as the underlying data structure behind a queue. We covered queues in Chapter 8, Crafting Elegant Code with Stacks and Queues, and you’ll recall that they are lists of items in which data can only be inserted at the end and removed from the beginning. Back then, we used an array as the basis for the queue, explaining that the queue is simply an array with special constraints. However, we can also use a linked list as the basis for a queue, assuming that we enforce the same constraints of only inserting data at the end and removing data from the beginning. Does using a linked list instead of an array have any advantages? Let’s analyze this.
Again, the queue inserts data at the end of the list. As we discussed earlier in this chapter, arrays are superior when it comes to inserting data, since we’re able to do so at an efficiency of O(1). Linked lists, on the other hand, insert data at O(N). So when it comes to insertion, the array makes for a better choice than a linked list.
When it comes to deleting data from a queue, though, linked lists are faster, since they are O(1) compared to arrays, which delete data from the beginning at O(N).
Based on this analysis, it would seem that it doesn’t matter whether we use an array or a linked list, as we’d end up with one major operation that is O(1) and another that is O(N). For arrays, insertion is O(1) and deletion is O(N), and for linked lists, insertion is O(N) and deletion is O(1).
However, if we use a special variant of a linked list called the doubly linked list, we’d be able to insert and delete data from a queue at O(1).
A doubly linked list is like a linked list, except that each node has two links—one that points to the next node, and one that points to the preceding node. In addition, the doubly linked list keeps track of both the first and last nodes.
Here’s what a doubly linked list looks like:
In code, the core of a doubly linked list would look like this:
| | class Node |
| | |
| | attr_accessor :data, :next_node, :previous_node |
| | |
| | def initialize(data) |
| | @data = data |
| | end |
| | |
| | end |
| | |
| | class DoublyLinkedList |
| | |
| | attr_accessor :first_node, :last_node |
| | |
| | def initialize(first_node=nil, last_node=nil) |
| | @first_node = first_node |
| | @last_node = last_node |
| | end |
| | |
| | end |
Since a doubly linked list always knows where both its first and last nodes are, we can access each of them in a single step, or O(1). Similarly, we can insert data at the end of a doubly linked list in one step by doing the following:
We create a new node ("Sue") and have its previous_node point to the last_node of the linked list ("Greg"). Then, we change the next_node of the last_node ("Greg") to point to this new node ("Sue"). Finally, we declare the new node ("Sue") to be the last_node of the linked list.
Here’s the implementation of a new insert_at_end method available to doubly linked lists:
| | class DoublyLinkedList |
| | |
| | attr_accessor :first_node, :last_node |
| | |
| | def initialize(first_node=nil, last_node=nil) |
| | @first_node = first_node |
| | @last_node = last_node |
| | end |
| | |
| | def insert_at_end(value) |
| | new_node = Node.new(value) |
| | |
| | # If there are no elements yet in the linked list: |
| | if !first_node |
| | @first_node = new_node |
| | @last_node = new_node |
| | else |
| | new_node.previous_node = @last_node |
| | @last_node.next_node = new_node |
| | @last_node = new_node |
| | end |
| | end |
| | |
| | end |
Because doubly linked lists have immediate access to both the front and end of the list, they can insert data on either side at O(1) as well as delete data on either side at O(1). Since doubly linked lists can insert data at the end in O(1) time and delete data from the front in O(1) time, they make the perfect underlying data structure for a queue.
Here’s a complete example of a queue that is built upon a doubly linked list:
| | class Node |
| | |
| | attr_accessor :data, :next_node, :previous_node |
| | |
| | def initialize(data) |
| | @data = data |
| | end |
| | |
| | end |
| | |
| | class DoublyLinkedList |
| | |
| | attr_accessor :first_node, :last_node |
| | |
| | def initialize(first_node=nil, last_node=nil) |
| | @first_node = first_node |
| | @last_node = last_node |
| | end |
| | |
| | def insert_at_end(value) |
| | new_node = Node.new(value) |
| | |
| | # If there are no elements yet in the linked list: |
| | if !first_node |
| | @first_node = new_node |
| | @last_node = new_node |
| | else |
| | new_node.previous_node = @last_node |
| | @last_node.next_node = new_node |
| | @last_node = new_node |
| | end |
| | end |
| | |
| | def remove_from_front |
| | removed_node = @first_node |
| | @first_node = @first_node.next_node |
| | return removed_node |
| | end |
| | |
| | end |
| | |
| | class Queue |
| | attr_accessor :queue |
| | |
| | def initialize |
| | @queue = DoublyLinkedList.new |
| | end |
| | |
| | def enque(value) |
| | @queue.insert_at_end(value) |
| | end |
| | |
| | def deque |
| | removed_node = @queue.remove_from_front |
| | return removed_node.data |
| | end |
| | |
| | def tail |
| | return @queue.last_node.data |
| | end |
| | end |