How, When, and Why to Use Custom Data Structures in Python

data structurespython

Python's lack of pointers makes data-structure construction intuitively more challenging, and has so much built in functionality that, as an amateur, I can't see when, why, or how you would create something beyond what's already there.

When have you built your own, and why did you do it? E.g. special types of trees, etc.

Best Answer

Well, that kind of depends on what you are willing to call a "data structure." According to Wikipdia, a data structure is simply a "particular way of storing and organizing data in a computer so that it can be used efficiently." So, therefore, classes would be a form of data structure, and classes are very widely used in Python. But, for the sake of this answer, I will assume you are more interested in what you might learn about in a data structures and algorithms class (e.g. trees, linked lists, queues, hashes, etc...).

Now, because of Python's pseudo-code-like syntax it can be a very useful language for implementing data structures in. If for no other purpose than just to aid in understanding these basic concepts. For example, when I first learned about linked list I decided to implement them in Python:

class node:
    def __init__(self, data = None, is_header = False):
        self.data = data
        self.next = None
    def __str__(self):
        return "|{0}| --> {1}".format(str(self.data), str(self.next))


class linked_list:
    def __init__(self):
        self.header = node("!Header!", True)

    def add_node(self, add_me):
        current_node = self.header
        while 1:
            if current_node.next == None:
            current_node.next = add_me
            break
            else:
            current_node = current_node.next    

    def print(self):
        print (str(self.header))

Now, this isn't a perfect example, nor is it even a totally proper implementation of a linked list, but it goes to illustrate something:

Python's simple syntax can be helpful in understanding data structures

Another example would be a priority queue that I built back in the day:

class priority_queue:
    def __init__(self):
        self.element = []
        self.priority = []

    def enqueue_with_priority(self, me, priority):
        where = 0
        for i in range(len(self.element)):
            if not priority < self.priority[i]:
            where = i
            break

        self.element.insert(where, me)
        self.priority.insert(where, priority)

    def dequeue_highest(self):
        return self.element.pop(0)

    def print(self):
        for i in self.element:
            print i

Again, not a perfect implementation but it illustrates another benefit of coding a data structure in Python:

Python is useful in prototyping data structures to optimize them for lower-level programming languages

Looking back on this code I see flaws in my implementation. The Python code, however, tends to be short and sweet. So if I wanted to implement a data structures in a lower-level language (such as a c-style language) I could first generate a quick Python prototype and then optimize later.

Finally, I think Python can help in the development of data structures, because:

In Python, development is quick, mistakes are allowed and you can try things out.

Imagine you are building a hash-table-like data structure, in a strongly-typed, compiled language you would usually try things out in an IDE, then have to compile and run it. In Python, you can just pull up IDLE, iPython or the Python interpreter and just try things out! No need to recompile for each little change to the hash function you want to try -- just plug it into the interpreter.

So, in conclusion, I guess what I'm saying is that I agree with you: there's not a lot of practicality in building your own data structures (since most anything you may want has already been implemented and optimized). However, for me, there is a lot of educational benefit (because of Python's ease of syntax), as well as a lot of creative and developmental freedom (due to Python's low-constraint, EAFP design).

It is important to note that although python (through its wide-reaching library) provides many standard data structures, a "data structure" (by definition) can be almost anything. So, in Python as well as any other language we may use to solve non-trivial problems, we are going to need to define new data structures. Therefore, it is quite arguable that serious Python developers create custom data structures just as much as serious developers in other languages do.

Related Topic