Article Preview

FEATURE

A Matrix Tree

Using a matrix instead of a linked list

Issue: 15.6 (November/December 2017)
Author: Marc Zeedar
Author Bio: Marc taught himself programming in high school when he bought his first computer but had no money for software. He's had fun learning ever since. Jens Bendig founded a computer animation company, motionDesign, in 1996 and a small IT business called Void in 1998. In his youth he was fascinated by two things, film and software, and he still is. He now teaches computer animation in Bremen, Germany.
Article Description: ption>No description avai
Article Length (in bytes): 49,558
Starting Page Number: um
Article Number: 15605
Resource File(s):

project15605.zip Updated: 2017-11-01 11:56:48

Related Link(s): None

Excerpt of article text...

In the previous issue of xDev (issue 15.5), Thomas Tempelmann wrote about WeakRefs as a solution for linking linked lists. It's a great idea, but in many situations you can use a matrix to show connections instead.

First, here's a quick recap if you are unfamiliar with linked lists. Linked lists are objects that are connected with each other—they're great for things like tree structures, with each branch linking to their offshoots, and those children linking back to their parents (see Figure 1)

There are issues with linked lists, however. Finding an item can take time if you have to search the entire structure, clearing/erasing links requires extra work, and they can use memory and be slow as per the previous article.

Most significantly, they make it hard to get a visualization of the link-structure—it's topology. Using a connectivity matrix or adjacency matrix instead solves for most of those problems, especially the latter, as the matrix is the topology!

The Matrix Way

The basic idea of a matrix is easy: you just need a two-dimensional array to create a structure like a simple xy graph. The size of both dimensions are the number of objects you have, so ten objects would be a 10x10 grid:

...End of Excerpt. Please purchase the magazine to read the full article.