2: Introduction to Data Structures

Introduction to Data Structures

Data Structure is an arrangement of data in a computer’s memory (or sometimes on a disk). Data structures include arrays, linked lists, stacks, binary trees, and hash tables, among others. Algorithms manipulate the data in these structures in various ways, such as searching for a particular data item and sorting the data.

Overview of Data Structures
Another way to look at data structures is to focus on their strengths and weaknesses. Table 1.1 shows the advantages and disadvantages of the various data structures.

TABLE 1.1 Characteristics of Data Structures

Data Structure Advantages Disadvantages
Array
Quick insertion, very
fast access if index
known. Slow search,
slow deletion,
fixed size.
Ordered array
Quicker search than
unsorted array Slow insertion and
deletion, fixed size.
Stack Provides last-in, first-out access. Slow access to other items.
Queue
Provides first-in, first-out access. Slow access to other items.
Linked list
Quick insertion, quick deletion. Slow search.
Binary tree
Quick search, insertion, deletion (if tree remains balanced). Deletion algorithm is complex.
Red-black tree Quick search, insertion, deletion. Tree always balanced. Complex.
2-3-4 tree Quick search, insertion, deletion. Tree always balanced. Similar trees good for disk storage. Complex.
Hash
Very fast access table if key known. Fast insertion Slow deletion, access slow if key not known, inefficient
memory usage.
Heap
Fast insertion, deletion, access to largest item. Slow access to other items.

Graph
Models real-world situations. Some algorithms are slow and complex.
The data structures shown in Table 1.1, except the arrays, can be thought of as Abstract Data Types, or ADTs.

A data type consists of
• a domain (= a set of values)
• A set of operations.
Example 1: Boolean or logical data type provided by most programming languages.
• Two values: true, false.
• Many operations, including: AND, OR, NOT, etc.

Abstract Data Type (ADT):
The basic idea behind an abstract data type is the separation of the use of the data type from its implementation (i.e., what an abstract data type does can be specified separately from how it is done through its implementation)

The advantages of using the ADT approach are:
1. The implementation of ADT can change without affecting those method that use the ADT
2. The complexity of the implementation are hidden

For example, an abstract stack data structure could be defined by two operations: push, that inserts some data item into the structure, and pop, that extracts an item from it.