Data Structures and Algorithms

Iterative Sorting

Apr 162018

Before writing an algorithm, it’s always worth thinking about how you would solve the same problem “by hand”. After all, you can’t write instructions for how to do something if you don’t know how to do it yourself.

The problem we’re currently interested in is sorting — given a list, put its values in order. There are hundreds of algorithms which solve this problem, but ultimately every sorting algorithm does one of two things:

The ‘Linked List’ Data Structure

Feb 192018

When designing a data structure, there are always choices to make. In the previous post we described the array-list data structure implementing the list data type; in that post, we made the choice to store the list values in an “underlying array” so the list values would all be together in memory. In this post we’ll show that this really was a choice, by developing a list data structure which stores the list values in separate objects, rather than a single array object.

The ‘Array-List’ Data Structure

Feb 192018

In earlier posts we described lists and arrays. We described lists as an abstract data type, meaning we said what a list is and what we should be able to do with one. However, we didn’t say how a list is implemented — we didn’t describe a data structure for a list — so we don’t yet have a scheme for representing lists in memory.(1) On the other hand, when we described arrays, we did also describe how to represent them in memory.


hosted on werp.site