DEV Community

Cover image for How I Built My Own List Type in Python With a String
Simon Egersand 🎈
Simon Egersand 🎈

Posted on • Updated on • Originally published at prplcode.dev

How I Built My Own List Type in Python With a String

I had this idea of building a list type in Python just using the string type. Sounds stupid, right? “Crazy idea; bad pitch” as one of my old colleagues used to say. I knew it was stupid, and that was the point! The idea came to me a few years ago when I was implementing a linked list. “In what other ways can I represent a list?” I thought. “Let me build a list type using a string!”

Choosing Python 🐍

Python is fun! It’s quick to get started with, there’s a big community and there are mature tools to help you. I could have chosen JavaScript but I’m less experienced with Python and I wanted to learn more about it.

List Type Design

This is the part where most brain power is used — usually. For me it was quick. I decided to design my list type in a string list this:

element1,element2,element3
Enter fullscreen mode Exit fullscreen mode

I chose "," as the delimiter between elements, mostly for readability.

Just like in (untyped) Python, my list was gonna be heterogeneous, which means I can store elements of different types in the same list. I took this decision to align with the native list type and to simplify the implementation.

List API Design 📄

Next step was to decide the API for my new list type. I looked at the API for Python’s list and decided to implement most of them. Some of them, like copy() and reverse() I chose to exclude.

Implementation 😌

This was the fun part! Initialising a new list was easy, just create an empty string. Same for add(), just append it to the end with the delimiter in between.

__list: str = ""
__delimiter: str = ","

def add(self, element: object) -> None:
    if self.is_empty():
        self.__list = element
    else:
        self.__list += "{}{}".format(self.__delimiter, element)
Enter fullscreen mode Exit fullscreen mode

I also added support for remove() which was slightly more complicated.

def remove(self, element: object) -> bool:
    for i in range(self.size()):
       if self.get(i) == element:
           self.remove_at(i)
           return True

   return False
Enter fullscreen mode Exit fullscreen mode

I ended up implementing 12 methods but I don’t want to clutter this post with any more code. See below for a link to the repo.

Performance 🚀

Once I had implemented my list type I was super curious how it performed in comparison to the native list type. I decided to benchmark all my new methods, and here are the results:

List        Function            Description                                     N       Result
----------------------------------------------------------------------------------------------------------
Native      constructor         new instance with 100 strings                   10000   7.07ms
SlowList    constructor         new instance with 100 strings                   10000   1926.76ms
----------------------------------------------------------------------------------------------------------
Native      constructor         new instance with 100 ints                      10000   5.95ms
SlowList    constructor         new instance with 100 ints                      10000   1499.77ms
----------------------------------------------------------------------------------------------------------
Native      constructor         new instance using of() with 100 strings        10000   6.40ms
SlowList    constructor         new instance using of() with 100 strings        10000   1868.80ms
----------------------------------------------------------------------------------------------------------
Native      constructor         new instance using of() with 100 ints           10000   5.77ms
SlowList    constructor         new instance using of() with 100 ints           10000   1447.82ms
----------------------------------------------------------------------------------------------------------
Native      add                 add strings to list                             10000   1.00ms
SlowList    add                 add strings to list                             10000   28.26ms
----------------------------------------------------------------------------------------------------------
Native      add                 add ints to list                                10000   3.25ms
SlowList    add                 add ints to list                                10000   41.65ms
----------------------------------------------------------------------------------------------------------
Native      add_at              add_at fixed position with string               10000   21.93ms
SlowList    add_at              add_at fixed position with string               10000   684.87ms
----------------------------------------------------------------------------------------------------------
Native      add_at              add_at fixed position with int                  10000   21.45ms
SlowList    add_at              add_at fixed position with int                  10000   183.11ms
----------------------------------------------------------------------------------------------------------
Native      contains            contains with string                            10000   1.19ms
SlowList    contains            contains with string                            10000   106.24ms
----------------------------------------------------------------------------------------------------------
Native      contains            contains with int                               10000   0.96ms
SlowList    contains            contains with int                               10000   94.71ms
----------------------------------------------------------------------------------------------------------
Native      get                 get last element of list of size 100            10000   0.46ms
SlowList    get                 get last element of list of size 100            10000   104.16ms
----------------------------------------------------------------------------------------------------------
Native      index_of            index_of last string in list of size 100        10000   15.42ms
SlowList    index_of            index_of last string in list of size 100        10000   10365.40ms
----------------------------------------------------------------------------------------------------------
Native      index_of            index_of last int in list of size 100           10000   16.63ms
SlowList    index_of            index_of last int in list of size 100           10000   7364.60ms
----------------------------------------------------------------------------------------------------------
Native      last_index_of       last_index_of las string in list of size 100    10000   9.85ms
SlowList    last_index_of       last_index_of las string in list of size 100    10000   295.06ms
----------------------------------------------------------------------------------------------------------
Native      last_index_of       last_index_of last int in list of size 100      10000   9.08ms
SlowList    last_index_of       last_index_of last int in list of size 100      10000   225.17ms
----------------------------------------------------------------------------------------------------------
Native      remove              remove last string in list of size 100          10000   21.70ms
SlowList    remove              remove last string in list of size 100          10000   12636.32ms
----------------------------------------------------------------------------------------------------------
Native      remove              remove last string in list of size 100          10000   21.24ms
SlowList    remove              remove last string in list of size 100          10000   9124.89ms
----------------------------------------------------------------------------------------------------------
Native      remove_at           remove_at last int in list of size 100          10000   6.34ms
SlowList    remove_at           remove_at last int in list of size 100          10000   2270.03ms
----------------------------------------------------------------------------------------------------------
Native      size                size with string list of size 100               10000   0.80ms
SlowList    size                size with string list of size 100               10000   9.06ms
----------------------------------------------------------------------------------------------------------
Native      size                size with int list of size 100                  10000   0.94ms
SlowList    size                size with int list of size 100                  10000   7.40ms
----------------------------------------------------------------------------------------------------------
Native      set                 set last string in list of size 100             10000   0.48ms
SlowList    set                 set last string in list of size 100             10000   427.26ms
----------------------------------------------------------------------------------------------------------
Native      set                 set last int in list of size 100                10000   0.55ms
SlowList    set                 set last int in list of size 100                10000   430.91ms
----------------------------------------------------------------------------------------------------------
Native      to_string           to_string string list of size 100               10000   9.19ms
SlowList    to_string           to_string string list of size 100               10000   43.74ms
----------------------------------------------------------------------------------------------------------
Native      to_string           to_string int list of size 100                  10000   269.77ms
SlowList    to_string           to_string int list of size 100                  10000   38.11ms
Enter fullscreen mode Exit fullscreen mode

No surprises really. The native list is faster in all the methods except for to_string() where my list is. faster. This is not entirely accurate though because Python’s list doesn’t have a to_string() so I created one by using ''.join(list).

Conclusion

After seeing the results of the benchmarks, the name of the list type became obvious -- SlowList. I’m sure it could be faster and more optimised by someone more knowledgeable on Python than me, but of course it will never be as fast as the native list.

I really enjoyed this project. I knew from the beginning no one would ever use it, or even star it on Github, and that was the root of the enjoyment. I’m so used to thinking I need to deliver value that it was a relief to build something completely useless.

You can find the project on Github.

What’s Next? 🌌

If you think this project is interesting and want to contribute to it there’s a few issues on Github you can look at. I always welcome help 😊

Learn More 👩‍🏫

For more serious topics on how to grow yourself as a software engineer, check out these posts:


Follow me on Twitter @prplcode

Originally published at https://prplcode.dev

Top comments (0)