data structures

A data structure is a way of organizing data for use in a computer program. There are three basic components to a data structure: a set of suitable basic data types, a way to organize or relate these data items to one another, and a set of operations, or ways to manipulate the data.

For example, the array is a data structure that can consist of just about any of the basic data types, although all data must be of the same type. The way the data is orga-nized is by storing it in sequentially addressable locations. The operations include storing a data item (element) in the array and retrieving a data item from the array.

Types of Data Structures

The data structures commonly used in computer science include arrays (as discussed above) and various types of lists. The primary difference between an array and a list is that an array has no internal links between its elements, while a list has one or more pointers that link the elements. There are several types of specialized list. A tree is a list that has a root (an element with no predecessor), and each other element has a unique predecessor. The guarantee of a unique path to each tree node can make the operations of inserting or deleting an item faster. A stack is a list that is accessible only at the top (or front). Any new item is inserted (“pushed”) on top of the last item, and remov-ing (“popping”) an item always removes the item that was last inserted. This order of access is called LIFO (last in, first out). A list can also be organized in a first in, first out (FIFO) order. This type of list is called a queue, and is useful in a situation where tasks must “wait their turn” for attention.

Implementation Issues

The implementation of any data structure depends on the syntax of the programming language to be used, the data types and features available in the language, and the algo-rithms chosen for the data operations that manipulate the structure. In traditional procedural languages such as C, the data storage part of a data structure is often specified in one part of the program, and the functions that operate on that structure are defined separately. (There is no mechanism in the language to link them.) In object-oriented languages such as C++, however, both the data storage declarations and the function declarations are part of the same entity, a class. This means that the designer of the data structure has complete control over its implementation and use.

Together with algorithms, data structures make up the heart of computer science. While there can be numerous variations on the fundamental data structures, understand-ing the basic forms and being able to decide which one to use to implement a given algorithm is the best way to assure effective program design.