I’m reading Data Structures and Algorithms in Python, by Goodrich, Tamassia, and Goldwasser, and I think that it is very, very good. I particularly like the explanation of why binary search over a sorted list is 
.
Monthly Archives: May 2016
Sorting Algorithms in Python
Tonight I’m looking at some sorting algorithms in Python. First up are Bubble Sort and Selection sort, both with 
average and worst case runtime, and 
memory. Then I’ll look at an iterative and recursive implementation of Merge Sort, Quick Sort, and Heap Sort with 
.
Simple Directed Graph in Python
This is a work in progress, there’s a lot of complex questions you can ask about graphs, but I though it was neat that you could produce an actual graphy looking thing in so few lines of code. This is a directed graph, and you use the graph object to first create nodes, and then define (unweighted) edges between them or to themselves. The __repr__() method just lists the node data, whatever that is, with an ASCII arrow pointing to another node’s data.
Doubly Linked List in Python
Here is round two for linked lists, the doubly linked list. It’s not very much more complex than a singly linked list. Breaking things into cases using the self.count attribute makes the code easier to read and reason about.
Another Simple Tree in Python
I’ve posted before about creating a tree in Python, but I like this implementation better. It uses a nested class to represent the nodes of the tree, and an interesting construction (line 11) that is a result of that nested class. Also, I do a simple pre-order traversal. I’ll flesh this guy out in later posts.
Singly Linked List in Python
I was reading about data structures this evening and I worked out simple singly linked list. The neat thing about this implementation is that a I made it iterable, also. I’d originally wanted to provide a minimal working singly linked list, and then add features and testing with explanations, but it’s been a long day. This example assumes that you’re using Python2.7; version 3 provides a __next__ class method.