Introduction to Data Structures – Definition, Uses and Examples

Bhupendra Parihar,

Introduction to Data Structures – Ever since human life began on this earth, humans have been continuously inventing various methods to represent data in the form of text or pictures, depending on their needs. This leads to the topic of data structure.

Basic terminology and concepts will be explained in this chapter with suitable examples; we will also consider the operations related to and applied to data structures. We will also try to understand the term algorithm, its complexity and how algorithms and data structure are selected for a given problem. 

Elementary Data Organization

Data may be expressed as facts or figures or probabilities for physical phenomena or business transactions.

 This simply means that data is a single value or set of values. A data item refers to a single unit of values. There are two main types of data Items.

  1. Group items are data items that can be divided into different subitems. 
  2. Elementary items are data items that cannot be divided into different subitems.

For example, in this abstract world, the data items for a product might be product Description, Purchase Cost, Selling Price, Items on Hand, and Order Quantity, but the product identification number is treated as a single item. Therefore, we have five group items and one element item.

Similarly, the data items for an employee might be subitems like First Name, Middle Name, and Last Name, but the employee’s security number would be treated as a single item. So, we have three group items and one elementary item.

This collection of data is often organized and considered similar to a hierarchy of records, fields, and files. In simple terms, an entity is nothing but a semi-essential data element that holds certain attributes or properties. This entity can also contain some values. These values can be of any type, numeric or non-numeric. 

“An entity is an article, a unit, or something about which information can be stored.”

Data Structure

As we have already read that data can be stored in many ways. A logical or mathematical model of a specific organization of data is known as a data structure. The selection of a specific data model is based on two characteristics:

  1. The data model should be structured well enough to reflect the actual relationships of the data in the real world.
  2. The structure should be simple to use so that anyone can use them for effective data processing whenever required.

Types of Data Structures

Array

An array is an ordered set of data items. It is the simplest type of data structure, known as a linear array.

Meaning of Linear Array If we name an array X, then the elements of array X are represented by subscript notation – 

x1, x2, x3, x4………… xn

or by parenthesis notation – 

x(1), x(2), x(3), x(4)…………x(N) 

or by bracket notation 

x(1), (2), (3), (4)…………x(N)

You can choose any type of notation based on the guidelines for your programming language. The number in the array list x(M) is called the subscript, and x(M) is called the subscripted variable. The occurrence of this element in the array list x(N) is at position N№.

Pointers

Now we will study pointers. Two different arrays that represent a sequence are connected through entries called pointers. Let DATA be an array. A variable is called a pointer if P points to an element in DATA, that is, if P contains the address of an element in DATA. An array PTR is called a pointer array if each element of PTR is a pointer. Pointers and pointer arrays are used to facilitate the processing of information in DATA.

Linked List

A linked list is a linear collection of data elements called nodes, where the linear order is given by the mean of the pointers. Each node is divided into two parts:

  1. The first part contains the element information.
  2. This is the Link Field or Next Pointer Field which contains the address of the next node in the list.

It is known as a null pointer because of its special value which is null but not 0. In actual practice, we can use a null pointer or a negative number for the null pointer, A null pointer is given by NULL. Linked lists also use a list pointer variable, START, which holds the address of the first node to be inserted into the list.

Tree

Sometimes a hierarchical relationship is established between different structures in data structures. The data strings that reflect this hierarchical relationship are called a rooted tree graph or a tree.

As we know, a file can contain one or more array records. The performance of the former is satisfactory, but when representing single items and elements items, a better performance is shown by using the given structure.

Stack

A Stack is a linear list in which insertion and deletion can take place only at one end, called the top. In other words, it strictly follows the Last-in-First-Out (LIFO) principle. Consider a stack of dishes that is open at one end and closed at the other. When you start arranging these in the stack, you find that you can add dishes one after the other. This means that insertion of dishes takes place only at one end. Repeating this process again and again gives the same result, which clearly shows that it follows the LIFO principle.

Queue

A queue differs slightly from a stack. It uses the First-In-First-Out (FIFO) principle. It is a linear list in which deletions can occupy only one end of the list (the front of the list) and insertions can occupy the other end of the list (the rear of the list).

Graph

Sometimes a paper contains a relationship between data elements that is not necessarily hierarchical in nature. For example, flights between cities are already connected. This type of data structure that reflects a particular relationship is called a graph.

Data Structures Operations

The data contained in our data structures can be processed by specific operations. However, the specific data structure chosen for a given situation depends on the number of operations to be performed. There are five common operations used when working with data structures.

  1. Traversing – Once the data structure is created, sometimes you need to access each element. This is the process of accessing each record to determine the appropriate terms within the record to be processed.
  2. Searching – Occasions when you need to find the location of a record with a given key value or find the location of all records that match one or more records. satisfies more conditions, known as searching.
  3. Insertion – When you add a new record to the structure, it is called insertion process.
  4. Deletion – When you delete a record from the structure, it is called deletion process.
  5. Updation – When you need to update the existing records of the structure then it is called the updation process.

There are also some cases where you need to use more than one operation type, such as sorting and merging.

(i) Sorting – This technique involves arranging records in a logical order based on one or more logical conditions.

(ii) Merging – When you need to combine two records from two different files into one main file.

Algorithms

As we know, the field of computer science focuses heavily on programs written to solve various problems in different domains. A program is a combination of both data structures and algorithms.

An algorithm is a series of steps required to solve a specific problem.

The concept of using an algorithm is to study a problem and provide a solution. It not only explains the sequence of steps to be performed but also performs these steps in the sequence already described by giving a suitable example to solve the problem.

When working with this type of algorithm, two terms, complexity and time-space trade-off, arise. The function of time and space trade-off is to measure the efficiency of the algorithm relative to its key while processing the data. 

On the other hand, the complexity of an algorithm is a function that provides the running time and/or space in terms of the input size.

engineering subjects