Implementing a Deque in Python

A deque (pronounced "deck") is a double-ended queue, a versatile data structure that allows efficient insertion and deletion from both ends. This challenge asks you to implement a deque class in Python, providing the core operations expected of a deque. Building your own deque is a great exercise in understanding data structures and their underlying implementations.

Problem Description

You are tasked with creating a Deque class in Python. This class should support the following operations:

• __init__(): Initializes an empty deque.
• append(item): Adds an item to the right end of the deque.
• appendleft(item): Adds an item to the left end of the deque.
• pop(): Removes and returns the rightmost item from the deque. Raises an IndexError if the deque is empty.
• popleft(): Removes and returns the leftmost item from the deque. Raises an IndexError if the deque is empty.
• peek(): Returns the rightmost item without removing it. Raises an IndexError if the deque is empty.
• peekleft(): Returns the leftmost item without removing it. Raises an IndexError if the deque is empty.
• is_empty(): Returns True if the deque is empty, False otherwise.
• size(): Returns the number of items in the deque.

The deque should be implemented using a Python list internally. Ensure that your implementation is efficient, particularly for appendleft and popleft operations. Consider how list operations can be leveraged to achieve this.

Examples

Example 1:

Input:
deque = Deque()
deque.append(1)
deque.append(2)
deque.appendleft(3)
print(deque.popleft())
print(deque.pop())

Output:

3
2

Explanation: The deque starts empty. 1 and 2 are added to the right. 3 is added to the left. popleft() removes and returns 3. pop() removes and returns 2.

Example 2:

Input:
deque = Deque()
print(deque.pop())

Output:

IndexError: pop from an empty deque

Explanation: The deque is empty. Attempting to pop() raises an IndexError.

Example 3:

Input:
deque = Deque()
deque.append(1)
deque.append(2)
print(deque.peek())
print(deque.peekleft())
print(deque.size())
print(deque.is_empty())

Output:

2
1
2
False

Explanation: 1 and 2 are added to the right. peek() returns 2 without removing it. peekleft() returns 1 without removing it. size() returns 2. is_empty() returns False.

Constraints

• The deque can hold any type of Python object.
• The maximum number of elements in the deque is not explicitly limited, but consider memory usage for very large deques.
• append, appendleft, pop, and popleft operations should ideally have an average time complexity of O(1). While using a list might not achieve this perfectly for appendleft and popleft, strive for reasonable performance.
• peek, peekleft, size, and is_empty operations should have a time complexity of O(1).

Notes

• You are free to use Python's built-in list data structure as the underlying implementation for your deque.
• Pay close attention to error handling, particularly when attempting to pop or popleft from an empty deque.
• Consider the implications of using a list for appendleft and popleft operations in terms of performance. While a linked list would offer O(1) for these operations, the goal here is to use a list and optimize within that constraint.
• Thoroughly test your implementation with various scenarios, including edge cases like empty deques and deques with a single element.