# Doubly Linked Lists

{% hint style="info" %}
Doubly linked lists are particularly useful when paired with other data structures like hash tables since it allows for $$O(1)$$ retrieval and deletions
{% endhint %}

It is easiest to use a dummy head and tail pointer for the doubly linked list to avoid weird edge cases

```python
class DoublyLinkedList:
    def __init__(self):
        self.head = Node(0, 'HEAD')
        self.tail = Node(-1, 'TAIL')
	# Setup the dummy pointers
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def insert_end(self, node):
        last = self.tail.prev
	# Fix the last element pointers
        last.next = node
        node.prev = last
	# Set the current element pointers
        node.next = self.tail
        self.tail.prev = node
        self.size += 1

        return node

    def delete(self, node):
        node_prev, node_next = node.prev, node.next
	# All we need to do is re-point the next and prev
	# Don't need to care too much about head/tail 
	# because we're using dummy pointers
        node.prev.next = node_next
        node.next.prev = node_prev
        node.next = None
        node.prev = None
        self.size -= 1

    def front(self):
        if self.head.next == self.tail: return None
        return self.head.next

    def length(self):
        return self.size

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://interviews.woojiahao.com/data-structures/linked-lists/doubly-linked-lists.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.