Python: Implementing Efficient Stack

By Xah Lee. Date: .

If you implement a linked list as efficient stack data structure, in python code, would it be faster than the builtin python list, for push (adding) a million items?

It turns out, no. In general it is almost 3 times slower.

But if you use the builtin lib collections.deque (deque stand for double-ended queue, which is a double-ended stack.) for push/pop operations, then yes, it's faster than python builtin list. The reason is that it is written in C.

This page shows the timing comparison of custom stack written in python against builtin python list.

Note: A linked list implementation for the stack data structure is optimal, and should be faster than a smart array that regenerates with items are added to array (which is python's implementation of its builtin list.).

Implementing Efficient Stack

The goal, is to see, if a stack using linked list implemented on top of python is more faster than using the builtin python list, for adding an item a million times.

# Code by Dion Bridger, 2022-12-20
def createLL(pythonList):
    result = []
    for item in pythonList:
        pushLL(result, item)
    return result

def pushLL(linkedList, x):
    if 0 == len(linkedList):
        return linkedList
        head = linkedList[0]
        tail = linkedList[1]
        linkedList.extend([x, [head, tail]])
        return linkedList

def popLL(linkedList):
    if 0 == len(linkedList):
        raise ValueError("Can't pop from empty list.")
    head = linkedList[0]
    tail = linkedList[1]
    return head

# ssss---------------------------------------------------

def createPL(pythonList):
    return list(pythonList)

def pushPL(pythonList, x):
    return pythonList.append(x)

def popPL(pythonList):
    return pythonList.pop()

# ssss---------------------------------------------------

x1 = range(10)

xstack = createLL(x1)
xlist = createPL(x1)

import timeit

print(timeit.timeit(lambda: pushLL(xstack, 1), number=1000000))
print(timeit.timeit(lambda: pushPL(xlist, 1), number=1000000))

# print( xstack)
# print( xlist )

# ssss---------------------------------------------------

# x1 = range(1_000_000)

# xstack = createLL(x1)
# xlist = list(x1)

# import timeit

# print(timeit.timeit(lambda: pushLL(xstack, 1), number=1000))
# print(timeit.timeit(lambda: xlist.append(1), number=1000))

# # print( xstack)
# # print( xlist )


Our stack is not faster than python's builtin list, in general. it is about 2 times as low.

Why is collections.deque fast?

because it is written in C.

python collections deque 2022-12 TjbDt
collections.deque C source code