What is Data Structure?

Article No: 2

Why we need Data Structure?

Data structures helps us to understand the relationship of one element with other. Also data structures implement and organize it in the memory. One may have question that memory organization for any data element is quite simple than why to make it complex. Let us take an example for this, say if we want to store subjects for computer science course. We can store it in simple way using array, a linear way to store data. But if we want to store information about class wise information like book, authors etc than it will be complex to store linearly. So we have to use some hierarchical data structure to store it.

Data Structure

In computer science, several data structures are known depending on area of applications. Of them, few data structures are there which are frequently used almost in all application areas and with the help of which almost all complex data structures can be constructed. These data structures are known as fundamental data structures or classic data structures.

FIGURE 1.1 Classic data structure

We can select data structures depending upon which type of operation is needed with data. Suppose we have a need to handle some processes in queue then we implement this situation with queue data structure. Sometimes a situation can be handled with different data structures then we take efficiency and storage in consideration. We can implement these data structures and their operations in some generalized manner then they can be used in some other modules also.

Primitive Data Structures

Primitive data structure also known as system defined data structure is inbuilt of any programming language. That is primitive data structures are defined by the system not by the user. For example in C programming language we have int, char, float and double data types. So primitive data structures are basic data types of any language that form the basic unit for the data structure define by the user.

It defines the internal representation of data, storage of data and retrieval from the memory. They are called primitive data types. The basic operations that could be performed on primitive data types are creation, destroy, read, update.

Non-Primitive Data Structures

These data structures are defined by the user using primitive data structures. These are the special kind of logical data types also known as derived data types. The Non-primitive data structure is also known as composite data structure.

Linear Data Structure

In linear data structures, the items are arranged in linear sequence. Linear management of data is in terms of sequence of data. For example array, linked list, stack or queue, where all elements will be arranged linearly in memory.

There are two basic ways of representing linear data structures in memory.

One way is to show linear relationship between elements as sequential memory location. Data structures, such as arrays, stacks and queues, are examples of such linear data structures. This method is known as static memory allocation of data.

The other way is to show the linear relationship between elements by using pointers or links. The linear data structure, linked list, is an example of such a data structure. This method is known as dynamic memory allocation.

The choice of a linear data structure depends on type of operations to be performed and frequency with which these operations are to be performed.

Since arrays are usually easy to traverse, sort, and search, they are generally used to store data that are more permanent in nature. If the size of the structure and data in the structure are constantly changing, then linked list is more useful.

1.      Array. The simplest type of data structure is a linear (or one-dimensional) array. By a linear, we mean a list of a finite number n of similar data elements referenced respectively by a set of n consecutive numbers, usually 1, 2, 3, . . . , n. If we choose the name A for the array, then the elements of A are denoted by bracket notation

A[1], A[2], A[3], . . . , A[N]

Regardless of the notation, the number K in A[K] is called a subscript and A[K] is called a subscripted variable.

FIGURE 1.2 Array

2.      Stack. A stack, also called a last-in-first-out (LIFO) system, is a linear list in which insertions and deletions can take place at one end, called the top. This structure is similar in its operation to a stack of dishes on a spring system. Note that new dishes are inserted only at the top of the stack and dishes can be deleted only from the top of the stack.

FIGURE 1.3 Stack

3.      Queue. A queue, also called a first-in-first-out (FIFO) system, is a linear list in which deletions can take place at one end of the list, the “front” of the list, and insertions can take place only at the other end of the list, the “rear” of the list. This structure operates in much the same way as a line of people waiting at a bus stop; the first person in line is the first person to board the bus.

FIGURE 1.4 Queue

4.      Linked list. A linked list, or one-way list, is a linear collection of data elements, called nodes, where the linear order is given by means of pointers. That is, each node is divided into two parts: the first part contains the information of the element, and the second part, called the link field or nextpointer field, contains the address of the next node in the list.

FIGURE 1.5 Linked List

Non-linear data structure

In this data structures, items are not in sequence. It means that data elements will be stored non-linear way, like one data may have more than two adjacent data or more.

1.      Trees. Data frequently contain a hierarchical relationship between various elements. The data structure which reflects this relationship is called a rooted tree graph or, simply, a tree.

FIGURE 1.6 Tree

2.      Graph. Data sometimes contain a relationship between pairs of elements which is not necessarily hierarchical in nature. For example, suppose an airline flies only between the cities connected by lines. The data structure which reflects this type of relationship is called a graph.

FIGURE 1.7 Graph

In addition to these classic data structures, other data structures such as lattice, Petri nets, neural nets, search graphs, semantic nets, etc., are known in various applications. These are known to be very complex data structures.

Resource Used:

1. Classic Data Structure

Compiled By: Chaudhary Amit V.