Introduction to Data Structures

Data structures and models have an important place in software development. When developing software, we first use the data structures and models provided by the programming language. If those structures are unsuitable, we can define and use a data structure appropriate to the problem.

Software and Program

Software is the collection of programs and code, excluding hardware, created by a programmer to perform a desired task or function.

A program is an algorithmic expression that forms a complete unit and performs a specific task. A program can be implemented in software or designed in hardware.

Code is a part of a program obtained by expressing an algorithmic operation through the statements, functions and features of a programming language.

Hardware and Memory

Hardware is the general name for the units that form a computer system, the integrated circuits on those units and the connections between them, composed of passive or active electronic components.

Hardware is physical, while software is virtual. Software programs and code are stored in memory or storage devices. Memory is the hardware unit in which program code and parameters are held. Storage devices include disks, diskettes, CDs and tape-backup units.

The hierarchy of memory and storage by access speed is described as registers, processor-internal memory, cache memory, main memory and storage devices.

Operating System

An operating system is the collection of software that runs on a computer, manages hardware resources and provides common services for application software. Examples include DOS, Windows, UNIX, Linux and NetWare.

Operating systems can be classified as single-user or multi-user according to the number of users; general-purpose or special-purpose according to intended use; single-process or multiprocess according to process handling; and real-time or non-real-time according to timing sensitivity.

Data Structure and Data Model

A data structure describes how data or information is arranged and stored in memory. Programming languages generally provide basic structures for integers, fractional numbers, characters and strings. If a program requires structures beyond these basic types, they must be defined using the facilities of the selected language. In C, for example, new data structures can be defined with `struct` and `union`.

A data model describes relational or sequential conditions among data and can be regarded as a conceptual approach to solving a problem. Mathematical and engineering problems implemented on computers can be solved by mapping them to an existing data model or defining a new model. Trees and graphs are two widely used examples.

Algorithm

An algorithm expresses, step by step, a specific task based on an existing or newly defined data model and then enables the task to be implemented in a programming language. Even a difficult-looking program becomes easier to implement when the necessary data model, data structure and algorithmic expression have been established.

The appropriate data structure and algorithm depend directly on the application. Existing language models are sufficient for some applications, while others require the programmer to define new models by combining existing ones.

An algorithm precisely specifies the steps and conditions required to obtain the result of a problem. Following those steps under the stated conditions leads to a result. Software development may require many types of algorithms, including:

• search algorithms
• sorting algorithms
• matrix or vector-processing algorithms
• graph algorithms
• algorithms for solving mathematical models

One or more of these types are commonly used in application development.

Program Execution Speed and Memory Requirements

Program execution cost is expressed through complexity. Complexity is not stated directly in units of time; it is expressed in terms of operation count or loop count because elapsed time depends heavily on the hardware on which the program runs. Comparing algorithms only by wall-clock time can therefore be misleading. Instead, the required operations or iterations are estimated independently of a particular computer.

Algorithmic complexity is examined from two perspectives: time complexity and space complexity. Time complexity describes the work required to reach a result; space complexity describes the required memory.

Complexity can be expressed either as an exact mathematical function of parameters or by an order showing how those parameters affect growth. Asymptotic notations such as O and Ω are used, with Big O being common. For example, a matrix-multiplication algorithm with time complexity O(n^2.81) is better in asymptotic order than O(n^3).

A program needs memory for two purposes: storing the code and storing the data processed while that code runs.

Processor, Machine Code and Assembly Language

A processor is a programmable digital unit that performs arithmetic, logic and comparison operations and combines them in meaningful sequences to execute more complex tasks. Examples include Intel Pentium processors used in standard PCs, Motorola 68040, Zilog Z80 and Z8000, IBM RISC 6000 and Texas Instruments digital-signal processors. Processors can be classified by architecture, production technology, characteristics and methods of accessing units.

Machine code is a program fragment written with instructions from a processor’s instruction set. A processor can execute machine-code programs directly without a compiler or translator.

Assembly language assigns symbolic names to machine-level instructions and uses those symbols when writing programs. It replaces difficult numeric machine-code representations with words that are more meaningful to humans.

Each processor family, and often each member of that family, has its own machine code and assembly language. Developing software at this level is difficult and time-consuming because the code and language must be learned for each processor.

Programming Languages

Programming languages make it possible to develop software without knowing every hardware detail. Many languages, such as BASIC, FORTRAN, Pascal, C and Python, have been designed either for specific fields or for general use. They are commonly described as high-level or mid-level languages.

An executable program ultimately has to be represented as machine code because the processor can decode and execute only machine instructions. Since machine-code development is difficult, assembly and high-level languages were created.

Assembly is a low-level language and requires knowledge of the processor’s internal structure, registers, addressing modes and data flow. C is generally described as a mid-level language because it combines capabilities associated with both low- and high-level programming. A compiler produces machine code from programs written in high- or mid-level languages, and each language has its own compiler toolchain.

Visual programming languages provide facilities for creating graphical interfaces in addition to the main program logic on graphical operating systems. Examples include Visual Basic, Visual C and Visual C++ on Windows and GTK+/GNOME libraries on Linux.

Database and SQL

A database is a storage and query system designed to keep information under a defined discipline and retrieve it quickly when needed. SQL, the Structured Query Language, enables interaction with a database, definition of its structures and insertion, retrieval and modification of data.

SQL is a standard query language supported by systems such as Access, Microsoft SQL Server, Oracle, Sybase and Ingres. MySQL can be regarded as an implementation commonly used under Linux-based environments. Oracle, Sybase and Ingres are professional database-management systems that provide both design facilities and execution environments.

For Internet applications, the MySQL and PHP combination has historically been used widely to build dynamic, database-driven web pages.

SQL performs substantial work while remaining comparatively easy to learn, particularly for developers familiar with English. Its syntax often resembles an English sentence. Commands such as SELECT, INSERT, UPDATE and DELETE operate on fields, tables and database files.

Divide-and-Conquer Approach

Divide and conquer has an important place in computer science. A large problem is divided into smaller problems while preserving the relevant properties, and the smaller problems are solved more easily. For example, a randomly ordered array can be repeatedly divided until each section contains only a small number of elements and can then be sorted and merged.

Many problems are naturally suitable for division. Sorting and searching, tree models and some matrix operations are examples for which divide-and-conquer algorithms make the solution easier to formulate.

Network Software and Programming

Network software enables different computers on a network, or different applications on the same computer, to interact and exchange data. A virtual connection is first established between the communicating programs, creating a logical channel. After that, the programs can exchange data as though they were accessing a local resource.

Network software depends strongly on the protocol suite. Software developed for one protocol suite does not necessarily work under another. TCP/IP, NetBEUI, NetWare and AppleTalk are examples; TCP/IP, which is also the protocol suite of the Internet, is the most widely used.

Network programming is the development of application software whose components communicate over a network. The central requirement is reliable communication between program components running on different systems. Network programming depends on the network architecture and protocol suite. Software developed for TCP/IP requires TCP/IP to be installed on the participating systems.

Benchmarking

Benchmarking compares the performance of two programs or systems that perform the same task by running them on commonly defined sample data. The same approach can be used for hardware. For example, two computers can perform a predefined task a fixed number of times, producing performance scores that can then be compared.

A benchmark dataset should be widely known and readily obtainable so that others can evaluate their own systems. Unless it targets a special case, the dataset should exercise a sufficiently broad set of possible conditions. When a special case is intended, that property must be stated explicitly.

Reference

• Rıfat Çölkesen, Data Structures and Algorithms