Deque Doubly Linked list

A Deque is a data structure that allows insertion and deletion of elements from both ends. It can be implemented using a Doubly Linked List, where each node contains a value and pointers to the previous and next nodes.

Here's an implementation of a Deque using a Doubly Linked List in Python:

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


class Deque:
    def __init__(self):
        self.head = None
        self.tail = None

    def is_empty(self):
        return self.head is None

    def add_front(self, value):
        new_node = Node(value)

        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def add_rear(self, value):
        new_node = Node(value)

        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def remove_front(self):
        if self.is_empty():
            return None

        front_value = self.head.value
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None

        return front_value

    def remove_rear(self):
        if self.is_empty():
            return None

        rear_value = self.tail.value
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.tail = self.tail.prev
            self.tail.next = None

        return rear_value

In this implementation, we define a Node class that represents a node in the Doubly Linked List. Each node has a value, a prev pointer to the previous node, and a next pointer to the next node.

The Deque class represents the Deque data structure. It has a head and tail pointer to the first and last nodes of the Doubly Linked List, respectively.

The is_empty method checks if the Deque is empty by checking if the head pointer is None.

The add_front method adds an element to the front of the Deque. It creates a new node with the given value and updates the pointers accordingly.

The add_rear method adds an element to the rear of the Deque. It creates a new node with the given value and updates the pointers accordingly.

The remove_front method removes and returns the element from the front of the Deque. It handles the case where the Deque becomes empty after the removal.

The remove_rear method removes and returns the element from the rear of the Deque. It handles the case where the Deque becomes empty after the removal.

Now let's solve a question from LeetCode using the Deque data structure. Consider the problem "Palindrome Linked List" (LeetCode #234).

Problem statement: Given a singly linked list, determine if it is a palindrome.

Example: Input: 1 -> 2 -> 2 -> 1 Output: True

To solve this problem, we can use a Deque to store the elements of the linked list in the order they appear. We then compare the elements from both ends of the Deque to check if they form a palindrome.

def is_palindrome(head):
    if not head or not head.next:
        return True

    deque = Deque()

    # Store the elements of the linked list in the deque
    node = head
    while node:
        deque.add_rear(node.val)
        node = node.next

    # Compare elements from both ends of the deque
    while not deque.is_empty():
        front = deque.remove_front()
        rear = deque.remove_rear()
        if front != rear:
            return False

    return True

In this example, we create a linked list with four nodes: 1 -> 2 -> 2 -> 1. We then call the is_palindrome function with the head of the linked list and print the result, which is True indicating that the linked list is a palindrome.

In this example, we check if the linked list is empty or contains only one element, in which case it is considered a palindrome. Otherwise, we create a Deque and store the elements of the linked list in the deque using the add_rear method.

Then, we continuously remove elements from both ends of the deque using the remove_front and remove_rear methods and compare them. If any pair of elements doesn't match, we return False, indicating that the linked list is not a palindrome.

The time complexity of the is_palindrome function is O(n), where n is the number of nodes in the linked list. The space complexity is also O(n) because we need to store all the elements of the linked list in the deque.