1.5 Type of Data Structures

There are two aspects of managing data structures, namely, logical and physical.

A. Logical Data Structures

- Linear Structures

The most common organization for data is a linear structure. A structure is linear if it has these two properties :

Property 1: Each element of the structure is followed by at most one other element

Property 2: No two elements are followed by the same element

An array is an example of a linearly structured data type. We generally write a linearly structured data type like this A®B®C®D.

Non-Linear Structures

Physical Data Structures

The physical aspects concerns with data storage and organization in computer hard wares and devices. These hardware media are capable of storing and holding data that can be addressed. RAM (Random-access-memory) of a computer, the read-write memory on a floppy disk, and Rom on a CD-ROM, hard disk and magnetic tapes are different kind of addressable storage media.

RAM: It is the primary, volatile and addressable memory that hold data and instructions for processing. The units of addressable storage might be words or bytes, which in depth themselves are based on binary system (0/1). In RAM, data can be accessed in an easy and speedy manner.

Magnetic Disks:

Magnetic Disk of the various types are used for Auxiliary Storage. The types used most often involve some type of magnetic disk. This method uses magnetism to store data on a magnetic surface. Advangages are high storage capacity, reliability and gives direct access to data. A drive spins the disk (in case of floppy disk) or a pack of platters (in case of hard disks) very rapidly underneath read/write head (s).

Before a disk is used, it must be prepared by means of a process called Formatting. Formatting is one of the basic tasks handled by the computer’s operating system. The formatting process sets up a method of assigning addresses to the different areas of disk, by dividing disk (s) into tracks, sectors, clusters, and cylinders. The number of tracks and sectors on a given medium
(floppy or hard disk) is determined by the operating system of the computer. During the formatting operation the operation system labels each sector of each track with an address. It also sets up an area for keeping the list of addresses, called Master Boot record and File Allocation Table (FAT) on the disk. During formatting, the disk’s drive’, read/write head lays down a magnetic pattern on the disk’s surface, which enables data storage into organization of tracks, sectors etc.

The computer keep track of what it has put where on a disk by remembering the addresses of all sectors used, which would mean remembering some combination of the cylinder, track, and sector (c, t, s).

Computer maintains on the disk a special area called Master Boot Area and a table called File Allocation Table FAT. Master Boot Record and FAT are stored at the beginning of disk that is, outer most, first few track-sectors (clusters) of the disk. These track-sectors are called hard track-sectors. All other interior track-sectors are called soft tracks, and are used for data storage.

When a disk is formatted, all previous data is erased, surfaces are checked for physical and magnetic defects. A root directory is created in the hard track-sector area to tell where things are on the disk.

Master Boot Record (MBR) and FAT

The MBR is the information in the first few track-sectors of hard disk or floppy that identifies how and where an operating system is located so that it can be booted into computer’s main memory (RAM). The MBR is also called partition sector or table because it includes a table that locates each partition of hard disk.

A file which we want to store is defined as a finite sequence of bytes. We can break this sequence of bytes into successive blocks or clusters of 512 bytes each and we can store each 512-byte block in an empty sector of the disk. We link the successive sectors together by storing in each sector the address of another sector that contains the next 512-byte block of the file. Thus each sector contains not only a 512-byte block of data, but also a pointer to the next block in sequence in the file.

It is also usual to save some of the empty sectors on the disk to contain a file directory. You can imagine this as a table that contains one record for each file on the disk. Each record in the directory contains the characters spelling the file name, such as MyProgram.c, some file attributes, such as the length of the file in bytes, its date of creation, a code designating the type of the file, and finally a pointer to the first 512-byte block in the series of linked blocks containing the contents of the file. If the directory containing these individual file records fills more than one 512-byte sector, additional sectors can be allocated and “linked on” to the end of the directory in order to extend it.

The processing of accessing data has 4 steps, Seek, Rotate, Settle and Data transfer. The combination of times taken by these processes is known as the access time to locate data. Head moves laterally to proper track called Seek. The rotation of the disk under the head to the correct sector is called rotational delay. The lowering of head to disk and wait for vibrations to stop takes settling time. Finally, some time is consumed in data transfer from disk to main memory (RAM), and this time is called data transfer rate in kbs. All these add to give access time.

Optical Disk: CD-ROM etc

Based on Laser technology, optical disks offer a medium capable of storing extremely large amounts of data. The three main types of optical disks are CD-ROM, WORM CD, and CD-RW. CD-ROM stands for Compact-Disk-Read only Memory.