# Role Of Data Structures Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Computer science is a field of study that deals with solving variety of problems by using computers. The problem to be solved could be as simple as performing the addition of two numbers, or as complex as designing a robot capable of making decisions in a real-time environment. To solve a given problem by using a computer, we need to design an algorithm for it. The nature of an algorithm often depends closely on the nature of the data on which the algorithm works. Therefore, the study of algorithms also involves the study of data structure that algorithms work on.

The word algorithm is derived from the name of the Persian mathematician Al Khwarizmi.

An algorithm can be defined as a step-by-step procedure for solving a problem. It helps the user arrive at the correct result in a finite number of steps.

Multiple algorithm can be designed to solve a particular problem. However, the algorithms may differ in how efficiently they can solve the problems. In such a situation , an algorithm that provides the maximum efficiency should be used for solving the problem. Efficiency here means that the algorithm should work in a minimal time amd use minimal memory.

One of the basic techniques for improving the efficiency of algorithms is to structure the data that they operate in such a way that the resulting operations can be efficiently performed.

The way in which the various data elements are organized in memory with respect to each other is called data structure. We can also say that data structure is a particular way of sorting and organizing data in a computer, so that it can be used efficiently.

Data can be organized in many different ways ; therefore, we can create as many data structure as we want. However, there are some standard data structures that have proved useful over the years. These includes arrays, linked lists, stacks, queues, trees, and graphs. All these data structures are designed to hold a collection of data items. However, the difference lies in the way the data items are arranged with respect to each other and the operations that they allow. Because of the different ways in which the data items are arranged with respect to each other, some data structures prove to be more efficient than others to solve a given problems.

Suppose we want to write am algorithm that enables a printer to service the requests of multiple users on a first-come-first-served basis. In this case, using a data structure that stores and retrieves the requests in order of their arrival would be much more efficient than a data structure that stores and retrieves the requests in a random order.

## TYPES OF DATA STRUCTURE

â-ª Static : These are data structures whose size is fixed at compile time, and does not grow or shrink at run time. Eg. Array. Suppose we declare an array of size 50, but store only 5 elements in it; the memory space allocated for the remaining 45 element will be wasted. Similarly, if we declared an array of size 50 but later we want to store 20 more elements, we will not be able to store these extra required elements because of the fixed size of an array.

â-ª Dynamic : These are data structures whose size is not fixed at compile time and that can grow and shrink at run time to make more efficient use of memory. An example of a dynamic data structure would be a list of items for which memory is not allocated in advance. As and when items are added to the list, memory is allocated for those elements. Similarly, when items are removed from the list, memory allocated to those elements is deallocated. Such a list is called a linked list.

Array and linked lists are the basic data structures that are used to implement other data structures such as stacks,queues,trees, and graphs.

An array is always a static data structure, and a linked list is always a dynamic data structure. However, the other data structure can be static or dynamic depending on whether they are implemented using an array or a linked list.

## WHAT IS DATABASE ?

A database is collection of data or information in an organized way for one or more uses typically in digital form. One way of classifying databases involves the type of their contents, for example : bibliographic, document-text, statistical. Digital database are managed using database management system, which stores database contents, allowing data creation and maintainance,and search and other access.

As we know that database is organized collection of data or information so data can be organized in many different ways. Some standard forms are : array, linked list, stacks, queues, trees and graphs.

The data appearing in our data structures are processed by means of certain operations. They are :

â-ª Traversing : Accessing each data exactly once.

â-ª Searching : Finding the location of the record with a given key value.

â-ª Insertion : Adding a new records to the structure.

â-ª Deletion : Removing a record from the structure.

## NOTE : This term paper deals only with insertion techniques for various forms of database.

## INSERTION IN DATABASE

## â-º LINEAR ARRAY

A linear array is alist of finite number n of homogenous data elements (i.e. data elements of the same type) such that :

â-ª the elements of the array are referenced respectively by an index set consisting of n consecutive numbers.

â-ª the elements of the array are stored respectively in successive memory locations.

The elements of an array A may be represented by :

â-ª subscript notation

A1, A2, A3,â€¦â€¦â€¦â€¦â€¦, An

â-ª parentheses notation

A(1), A(2), A(3),â€¦â€¦â€¦â€¦A(N)

â-ª bracket notation

A[1], A[2], A[3],â€¦â€¦â€¦â€¦A[N]

## Representation of linear array in memory

1000

1001

1002

Conputing Memory

## INSERTION IN ARRAY

Inserting an element at the "end" of a linear array can be easily done provided the memory space allocated for the array is large enough to accommodate the additional element. On the other hand, suppose we need to insert an element in the middle of the array. Then, on average, half of the element must be moved downward to new locations to accommodate the new location and keep the order of the other elements.

The following algorithm insert a data element ITEM into Kth position in a linear array LA with N elements. The first 4 steps create space in LA by moving downward one location each element from Kth position on. These elements are moved in reverse order otherwise data might be erased. Step 5 inserts ITEM into the array in the space created. Before the exit from algorithm, the number N of elements in LA is increased by 1 to account for the new element.

## Algorithm :

Step 1 : [Initialize counter] Set J : = N.

Step 2 : Repeat steps 3 and 4 while J >= K.

Step 3 : [Move Jth element downward.] Set LA[J + 1] : = LA[J].

Step 4 : [Decrease counter.] Set J : = J - 1.

Step 5 : [Insert element] Set LA[K] : = ITEM.

Step 6 : [Reset N] Set N = N+ 1.

Step 7 : Exit.

From the above analysis, we came to the conclusion that if insertions are to be made in a collection of data elements, then a linear array may not be the most efficient way of sorting the data.

## â-º LINKED LISTS

A linked list, or one way list, is a linear collection of data elements, called nodes, where the linear order is given by the means of pointers. Linked lists are flexible data structures that provide a convenient way to store data. We do not have to specify the size of the list in advance. Memory is allocated is dynamically.

Linked lists are useful in operations where frequent manipulation of data is required. There are various linked list, each having a unique feature. The choice of a particular type of linked list is based on the problem at hand.

## Defining linked lists

A linked list is a chain of elements in which each element consists of data as well as a link to the next element. The link stores the address of the next logically similar element in the list.

Each such element of a linked list is called node.

## Data Address of next node

## Aaddress

Structure of a node

START

Data

Data 222

Data 111

NULL

Structure of a linked list

Each node contain the address of the next node in the list. However, there is no node that contains the address of the first node. To keep track of the first node of the list, a variable START is used that contains the address of the first node in the list. When the list does not contain any node, START is set to the value NULL. The last node does not contain the address of any other node. Therefore, the content of the NEXT field of the last node is set to NULL, so that the end of the list could be identified.

## INSERTION IN LINKED LIST

Algorithm which insert nodes into linked lists come up in various situations : at the beginning, after the node with a given location and into a sorted list.

## â-ª Inserting at the beginning

â- START

X

## â-

## â- â-â-

## â€¦â€¦â€¦â€¦

Item

## â-

NEW

Insertion at the Beginning of a list

Step 1 : [Overflow ?] If AVAIL = NULL, then: Write : OVERFLOW, and Exit.

Step 2 : [Remove first node from AVAIL list]

Set NEW = AVAIL and AVAIL = LINK [AVAIL].

Step 3 : Set INFO [NEW] = ITEM. [Copies new data into new node]

Step 4 : Set LINK [NEW] = START.

Step 5 : Set START = NEW.

[Changes START so it points to the new node.]

Step 6 : Exit

## â-ª Inserting after a given node

Algorithm inserts ITEM so that ITEM follows the node with location LOC or insert ITEM as the first node when LOC = NULL.

Step 1 : [Overflow ?] If AVAIL = NULL, then: Write : OVERFLOW, and Exit.

Step 2 : [Remove first node from AVAIL list]

Set NEW = AVAIL and AVAIL = LINK [AVAIL].

Step 3 : Set INFO [NEW] = ITEM. [Copies new data into new node]

Step 4 : If LOC = NULL, then : [Insert as first node]

Set LINK [NEW] = START and START = NEW.

Else : [Insert after node with location LOC.]

Set LINK [NEW] = LINK [LOC] and LINK[LOC] = NEW.

Step 6 : Exit

## â-ª Inserting into a sorted Linked List

Suppose ITEM is to be inserted into a sorted linked LIST. Then ITEM must be inserted b/w nodes A and B so that

INFO(A) < ITEM <= INFO(B)

First we will traverse the list, using a pointer variable PTR and comparing ITEM with INFO[PTR] at each node. While traversing, we will keep the track of the location of the preceding node by using a pointer variable SAVE. Thus SAVE and PTR are updated by the assignments

SAVE = PTR and PTR = LINK[PTR]

The traversing continues as long as INFO[PTR] > ITEM. Then PTR points to node B, so SAVE will contain the location of the node A.

Algorithm to find location LOC of the last node in a sorted list such that

INFO[LOC] < ITEM, or sets LOC = NULL.

Step 1 : [list empty ?] If START = NULL, then : Set LOC = NULL, and Return.

Step 2 : [Special case ?] If ITEM < INFO [START], then : set LOC = NULL, and Return.

Step 3 : Set SAVE = START and PTR = LINK[START]. [Initialize pointers.]

Step 4 : Repeat steps 5 and 6 while PTR not equal to NULL.

Step 5 : If ITEM < INFO[PTR], then :

Set LOC = SAVE, and Return.

[End of structure]

Step 6 : Set SAVE = PTR and PTR = Link[PTR]. [Update pointers]

[End of step 4 loop]

Step 7 : Return.

Now we will combine previous two algorithm to get algorithm for insertion into a sorted linked list.

Step 1 : [Prcedure to find the location of the node preceding ITEM.]

Step 2 : [Procedure to insert ITEM after the node with location LOC.]

Step 3 : Exit.

## Applications of linked list

â-ª Implemented in various gaming application.

Consider a game in which the player protects himself from the enemy by firing bullets. Whenever a bullet is fired. Its details need to be stored somewhere. These details include the size, colour, and coordinates of the bullet at a particular point of time.

â-ª File system in Operating System

It is used to implement the internals of a file system.

## â-º STACKS

Consider an example of a card game called Rummy. To start the game, a stock pile and a discard pile are placed in the centre, A player can draw either the topmost card of the stock pile or the top most card of the discard pile. If the drawn card does not make a valid sequence in the player's hand, the player can discard the card by placing it on the top of the discard pile. The next player can then draw either the topmost card of the stock pile or the discard pile, and so on.

To represent or manipulate such types of a discard pile in a computer program, we need a data structure that allows insertion and deletion at only one end. It should ensure that the last item inserted is the first one to be removed. A data structure that implements this concept is called a stack.

Thus we can say that " stack is a collection of data items that can be accessed at only one end, called top." It is also known as Last-In-First-Out(LIFO).

When we want to insert an element into a stack, we can say that we have pushed the element onto the stack.

## IMPLEMENTATION USING ARRAY

An array should be used to implement a stack only when the maximum number of elements in the stacks is known in advance. When a stack is implemented by using an array, we must ensure that the array is declared large enough to store max. number of elements in the stack.

## Insertion in stack (Implementing PUSH operation)

PUSH ( STACK, TOP, MAXSTK, ITEM)

STACK - Linear array

TOP - Pointer variable

MAXSTK - A variable which gives max. no. of elements that can be held by the stack.

The condition TOP = 0 or TOP = NULL will indicate that stack is empty.

Step 1 : [Stack already filled ?]

If TOP = MAXSTK, then : Print : OVERFLOW , and Return.

Step 2 : Set Top = TOP + 1.[Increase TOP by 1.]

Step 3 : Set STACK[TOP] = ITEM. [Insert ITEM in new TOP position.]

Step 4 : Return.

## IMPLEMENTATION USING LINKED LIST

When a stack is implemented by using an array, the max. size of the stack needs to be specified in advance. This limitation is overcome by using satack with linked list.

The INFO fields of the nodes hold the elements of the stack and the LINK fields hold pointers to the neighbouring element in the stack. The START pointer of the linked list behaves as the TOP pointer variable of the stack and the null pointer of the last node in the list signals the bottom of stack.

## Insertion in stack

A PUSH operation in stack is accomplished by insertion a node into the front or start of the list.

Push 'www' into STACK

Top

zzz

yyy

xxx

STACK after push operation

zzz

yyy

xxx

www Top

Step 1 : [Available space ?] If AVAIL = NULL, then write

OVERFLOW and Exit.

Step 2 : [Remove first node from AVAIL list]

Set NEW = AVAIL and AVAIL = LINK [AVAIL].

Step 3 : Set INFO[NEW] = TOP [Copies ITEM into new node]

Step 4 : Set LINK [NEW] = TOP [New node points to the original top node in the stack]

Step 5 : Set TOP = NEW [Reset TOP to point to the new node at the top of the stack]

Step 6 : Exit.

## Aplication of stack

## â-ª Expression evaluation and syntax parsing.

## â-ª Runtime memory management.

## â-ª Implementing function calls.

## â-ª maintaining the UNDO list for an application.

## â-ª Conversion of Number base.

## â-º QUEUES

## Consider a scenario of a bank, where there is only one counter to resolve customer queries. Therefore, customers have to stand in a queue to get their queries resolved. To avoid the inconvenience to the customers, the bank has decided to set up a new system.

## Under the system, whenever a customer visits the bank, a request entry will be made into the system and the customer will be given a request. The request will be stored in the system in order in which they were received. The request number of the earliest request will be automatically flashed on the query counter, to indicate that the customer with that request number can come next to get his query resolved. When a customer's request has been processed, the request will be removed from the system.

## To implement this kind of a system, we need a data structure that stores and retrieves the requests in order of their arrival. A data structure that implements this concept is a queue.

## Thus we can say that " A queue is a lineaer list of elements in which items are inserted at one end of the queue and deleted from the other end of the queue."

## The end at which elements are inserted is called rear and the end from which the elements are deleted is called front. A queue is also called a First-In-First-Out (FIFO).

## Front Rear

C

E

A

B

Structure of a queue

## ARRAY REPRESENTATION OF QUEUE

We should implement a queue by using an array only if we are sure about the maximum number of elements in the queue. This is because the size of the array needs to be specified in advance.

A B C D

0 1 2 3

Front Rear

To represent a queue in an array, we need to declare an array to store the element in the queue. In addition to declaring an array to store the element in the queue, we also need to declare two integer, FRONT and REAR, to keep track of the front and rear index position of the queue respectively.

QINSERT (QUEUE, N, FRONT, REAR, ITEM)

N : no. of elements in queue.

Step 1 : [Queue already filled ?]

If FRONT = 1 and REAR = N, or if FRONT = REAR + 1, then :

Write : OVERFLOW, and Return.

Step 2 : [Find new value of REAR.]

If FRONT = NULL, then : [Queue initially empty.]

Set FRONT = 1 and REAR = 1.

Else if REAR = N, then :

Set REAR = 1.

Else :

Set REAR = REAR + 1.

[End of If structure.]

Step 3 : Set QUEUE [REAR] = ITEM [This insert new element.]

Step 4 : Return.

## Special case :

10 16

Front 2 Rear 3

In the above fig. we can see that the REAR has reached the last index position and its value cannot be increment further. Therefore, it is not possible to insert any more elements in the queue. Although, there are two vacant position in the beginning of the array, there is no provision to fill these position.In such case, these empty position go waste.

An efficient way to solve this problem is to implement the array as circular array. In this approach, if the last index position of the array is occupied with the element, then we can start inserting elements from the beginning that is from the index position zero, provided there is free space at the beginning. Therefore, the cells in the array are treated as if they are arranged in a ring.

C:\Users\Amit\Desktop\amit.png

## LINKED REPRESENTATION OF QUEUE

A linked queue is a queue implemented as linked list with two pointer variables FRONT and REAR pointing to the nodes which is in the FRONT and REAR of the queue. The INFO fields of the list hold the elements of the queue and the LINK fields hold pointers to the neighbouring element in the queue.

CCC X

BBB

AAAQueue Q :

For Insertion into a linked queue, we need to borrow a node from the AVAIL list and carrying item to be inserted is added as the last node of the linked list representing the queue. The REAR pointer is updated to point to the last node just added to the list.

Insert 'EEE' into queue Q :

EEE X

CCC

BBB

AAA

Front Rear Rear

LINKQ_INSERT (INFO, LINK, FRONT, REAR, AVAIL, ITEM)

Step 1 : [Available space ?] If AVAIL = NULL, then Write

OVERFLOW and Exit.

Step 2 : [Removes first node from AVAIL list]

Set NEW = AVAIL and AVAIL = LINK [AVAIL]

Step 3 : Set INFO [NEW] = ITEM and LINK [NEW] = NULL

[Copies ITEM into new node]

Step 4 : If (FRONT = NULL) then FRONT = REAR = NEW

[If Q is empty then ITEM is the first element in the queue Q]

Else set LINK[REAR] = NEW and REAR = NEW

[REAR points to the new node appended to the end of the list]

Step 5 : Exit.

## Applications of Queues :

â-ª Printer Spooling

â-ª CPU Scheduling

â-ª Mail Service

â-ª Keyboard buffering

â-ªElevator