outward not upward

Linked lists, sometimes simply called lists, are a fundamental data structure in computer science. Languages such as Java and C# do an admirable job of abstracting away the details behind lists, but understanding them is absolutely crucial when building efficient programs.

The way in which linked lists are structured varies, but we will consider a doubly-linked list with external data. By that, we mean that each link in the list will refer to the previous link and the next link in the list, and that the data type that represents the list itself will not contain the data itself, but instead each link will contain a reference (pointer) to its corresponding data. In C++, a naive implementation might look like this:

struct LinkedList
{


LinkedList *prev;
LinkedList *next;
DataType *data;

};

Read the rest of this entry »

I bill myself out as a “software developer.” This is fair, I think, since I’ve written a lot of software over the past ten years, and this combined with my college education has enabled me to develop solutions to rather large and difficult problems.

Sometimes, though, we all need to reminded of the basics. It’s been a couple of years since my basic data structures and algorithms class, and it’s now gotten to the point where the difference between a red-black tree and a leftist tree is pretty fuzzy. Fuzzy to the point that I’m not sure I ever really grokked the difference.

So, it’s time for a refresher. I don’t have a copy of Leiserson/Rivest/Cormen handy, so I’m just going to use what’s on the shelf. Here’s the rubric for each topic: Read the rest of this entry »