How I Built My Own List Type in Python With a String
Tags: python, programming, fun
Published: 2022-05-02 12:20:33

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:

```python
element1,element2,element3
```

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.

```python
__list: str = ""
__delimiter: str = ","

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

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

```python
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
```

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:

```md
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
```

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](https://github.com/simeg/SlowList).

## What’s Next? 🌌
If you think this project is interesting and want to contribute to it there’s a few [issues on Github](https://github.com/simeg/SlowList/issues) 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:

* [5 Good Habits of a Software Engineer](https://dev.to/simeg/5-good-habits-of-a-software-engineer-3ocp)
* [What Skills Makes a Great Software Engineer?](https://dev.to/simeg/what-skills-do-you-think-makes-a-great-software-engineer-1b14)

---

_Follow me on Twitter [@prplcode](https://twitter.com/prplcode)_

_Originally published at https://prplcode.dev_