[Python] List-like Data Structure to prepend in O(1) AND append in O(n) [faster than deque]

I'm looking for a Deque like data structure, but it's only responsible to prepend to the start in O(1) time. Since it wouldn't need to append to the end, it would simplify the responsibilities that Deque has, ideally being faster than deque.

Are there any data structures which follow this rule?

I also tried using linked lists, but this is slower than Deque. But pointer allocation/reallocation seems slow. For 1 million prepends, linked lists give you ~0.84 seconds while deque is only ~0.1 seconds.

import time
from collections import deque

# Linked List Implementation
class Node:
def __init__(self, value=None):
self.value = value
self.next = None

class LinkedList:
def __init__(self):
self.head = None

def prepend(self, value):
new_node = Node(value)
new_node.next = self.head # Point new node to current head
self.head = new_node # Update head to the new node

def get_list(self):
current = self.head
result = []
while current:
result.append(current.value)
current = current.next
return result

# Deque Implementation
class FrontOnlyDeque:
def __init__(self):
self.deque = deque()

def prepend(self, value):
self.deque.appendleft(value)

def get_list(self):
return list(self.deque)


# Timing function
def time_operations(impl, n):
start_time = time.time()
for i in range(n):
impl.prepend(i)
return time.time() - start_time

# Number of prepends to test
n = 1000000

# Linked List test
linked_list = LinkedList()
linked_list_time = time_operations(linked_list, n)

# Deque test
deque_impl = FrontOnlyDeque()
deque_time = time_operations(deque_impl, n)

print(f"Linked List prepend time: {linked_list_time} seconds")
print(f"Deque prepend time: {deque_time} seconds")

Continue reading...