Fundamental Data Structures

Since the vast majority of algorithms of interest operate on data, particular ways of organizing data play a critical role in the design and analysis of algorithms. A data structure can be defined as a particular scheme of organizing related data item. The nature of the data items is dictated by a problem at hand; they can range from elementary data types (e.g., integers or characters) to data structure. There are a few data structure that have proved to be particular important for computer algorithms. Since you are undoubtedly familiar with most if not all of them, just a quick review is provided here:

Linear Data Structures

The two most important elementary data structures are the array and the linked list. A (one-dimensional) array is a sequence of n items of the same data type that are stored contiguously in computer memory and made accessible by specifying value of the array’s index.

In the majority of cases, the index is an integer either between 0 and n-1 or between 1 and n. Some computer languages allow an array index to range between any two integer bounds low and high and some even permit non-numerical indicates to specify, for example, data items corresponding to the 12 months of the year by the month names. Each and every element of an array can be accessed in the same constant amount of time regardless of where in the array the element in question is located. This feature positively distinguishes array from linked list. It is also assumed that every element of an array occupies the same amount of computer storage.

                                                Array are used for implementing a variety of other data structure. Prominent among them is the string, a sequence of characters from an alphabet terminated by a special character indicating the string’s end. String composed of zero’s and ones are called binary string or bit strings. Strings are indispensable for processing textual data. Defining computer languages and compiling programs written in them, and studying abstract computational models. Operations we usually perform on strings differ from those we typically perform on other arrays. They include computing the string length, comparing two strings to determine which one precedes the other according to the so-called lexicographic order, i.e. in a dictionary and concatenating two strings (forming one string from two given strings by appending the second to the end of the first).

A linked list is a sequence of zero or more elements called nodes each containing two kinds of information: some data and one or more links called pointers to other nodes of the linked list. (A special pointer called “NULL” is used to indicate the absence of a node’s successor.) In a singly linked list, each node except the last one contains a single pointer to the next element.

To access a particular node of a linked list, we start with the list’s first node and traverse the pointer chain until the particular node is reached. Thus, the time needed to access an element of a singly linked list, unlike that of an array, depends on where in the list element is located. On the positive side, linked lists do not require any preliminary reservation of the computer memory, and insertions and deletions can be made quite efficiently in a linked list by reconnecting a few appropriate pointer.

                                We can exploit of the linked list structure in a variety of ways. For example, it is often convenient to start a linked list with a special node called the header. This node often contains information about the linked list such as its current length; it may also contain in addition to a pointer to the first element, a pointer to the linked list’s last element.

                                Another extension is the structure called the doubly linked list, in which every node, except the first and the last, contains pointers to both its successor and its predecessor.

                The array and linked list are two principal choice in representing a more abstract data structure called a linear list or simply a list. A list is a finite sequence of data item i.e. a collection of data items arranged in a certain linear order. The basic operation performed on this data structure are searching, insertion and deletion of an element.

                                                                Two special types of lists, stacks and queues, are particularly important stack is a list in which insertions and deletions can be done only at the end. This end is called the top because a stack is usually visualized not horizontally but vertically. As a result when elements are added to (pushed onto) a stack and deleted from (popped off) it, the structure operates in the “last-in-first-out” (LIFO) fashion exactly as the stack of plates does if we can remove only the top plate or add another plate top of the stack. Stack have a multitude of applications; in particular they are indispensable for implementing recursive algorithms.

                                                                A Queue, on the other hand is list from which elements are deleted from one end of the structure, called the front (this operation is called de-queue), and new elements are added to the other end, called rear (this operation is called en-queue). Consequently, a queue operation in the “first-in-first-out”(FIFO) fashion. Queue also have many important applications, including several algorithms for graph problems.