Data Structures

Good afternoon everyone,

Today, we're going to discuss a few generic data structures sometimes used in the underpinnings of classic data types.  They include these major collections:

• Arrays
• Bitfields
• Linked Lists

Arrays have a simple setup in most languages and would be defined similar to one of these:

• NumberArray[ Type: NUMBER; Count: 10 ]
• NUMBER NumberArray[ Count: 10 ]
• NUMBER NumberArray[ ]

Arrays must contain (by design of the program, language, compiler, or library) several methods or functional blocks to perform these steps:

• Insertion (At an end or specified position)
• Deletion (At a specified position)
• Retrieval by Position (And you need to confirm if positions start at 0, 1, or use named positions)
• Update by Position (Sometimes implemented by Retreival, Deletion, and then Insertion)
• Length or Count (Used to determine validity of the request, not always available to user)

Array elements can also be arrays making table and matrix operations methods that can be implemented with an understanding of the math behind these systems.  Some early forms of images on computers were implemented with faked tables using long arrays only to be replaced by tabular style arrays in the long run.  The storage of these arrays can be complicated for either the programmer or technician researching memory issues making it a necessity for the conscientious designer to start off with error detection and built in testing.

Bitfields are specialized arrays that access or mimic the binary data of the storage and are often used for flags or systems of simple BOOLEAN equations.  Some implementations will turn an INTEGER between 0 and 2^X-1 into an array of X length.

Linked Lists utilizes a feature called a pointer.  Insertion and deletion is accomplished by holding two copies of the list. Depending on the language you may be able to specify the pointer in a variety of ways, but the general system setup is one of three styles:

• Forward links that require you to have a link to the first element and travel the list to the end to append items.
• Reverse links that start with the last element.
• Multiple links.  This special category in many cases can travel the list very fast, but the storage demands, as implied by the name, multiple quickly.

Regardless of style, Linked Lists generally have the following features:

• Insertion
• Deletion
• Length
• Update
• Retrieval
• Search

In the future, I may select sample implementations from well known tutorial sites for deeper discussions on these structures.