Python: Implementing Efficient Stack

By Xah Lee. Date: 2022-12-20.

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.).

2022-12-19

Implementing Efficient Stack

implement a stack in python, using linked list. The core of the linked list, must be either python 2-tuple, or list of 2 items.
you must write 3 function: createLL(pythonList), pushLL(linkedList,x), and popLL(linkedList).
No lib call. (obviously, else you can write a wrapped to the lib deque)
the code must have the expected efficiency of stack. that is, push and pop are contant time, regardless of stack length.

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):
        linkedList.append(x)
        linkedList.append([])
        return linkedList
    else:
        head = linkedList[0]
        tail = linkedList[1]
        linkedList.clear()
        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]
    linkedList.clear()
    linkedList.extend(tail)
    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 )

2022-12-21

Conclusion

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

2022-12-21

Why is collections.deque fast?

because it is written in C.

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