T/UDOM/2020/05241

DATA STRUCTURE AND ALGORITHM

SUMMARY ON DATA STRUCTURE

INTRODUCTION:
A data structure is a specialized format for organizing, processing, retrieving and
storing data. There are several basic and advanced types of data structures, all
designed to arrange data to suit a specific purpose. Data structures make it easy for
users to access and work with the data they need in appropriate ways. Most
importantly, data structures frame the organization of information so that machines
and humans can better understand it.

 The data structure is not any programming language like C, C++, java, etc. It
is a set of algorithms that we can use in any programming language to
structure the data in the memory.

 In general, data structures are used to implement the physical forms of

abstract data types.

 Data structures are a crucial part of designing efficient software. They also
play a critical role in algorithm design and how those algorithms are used
within computer programs.

NOW LETS OBSERVE TYPES OF DATA STRUCTURE.

The data structure type used in a particular situation is determined by the type of operations
that will be required or the kinds of algorithms that will be applied. The various data structure
types include the following:

A. Linear data structures

In linear data structures, the elements are arranged in sequence one after the other. Since elements are

arranged in particular order, they are easy to implement.

However, when the complexity of the program increases, the linear data structures might not be the

best choice because of operational complexities.

Popular linear data structures are:

1. Array Data Structure

In an array, elements in memory are arranged in continuous memory. All the elements of an array are

of the same type. And, the type of elements that can be stored in the form of arrays is determined by

the programming language.

To learn more, visit Java Array.

An array with each element

represented by an index

2. Stack Data Structure

In stack data structure, elements are stored in the LIFO principle. That is, the last element stored in a

stack will be removed first.

It works just like a pile of plates where the last plate kept on the pile will be removed first. To learn

more, visit Stack Data Structure.

3. Queue Data Structure

Unlike stack, the queue data structure works in the FIFO principle where first element stored in the

queue will be removed first.

It works just like a queue of people in the ticket counter where first person on the queue will get the

ticket first. To learn more, visit Queue Data Structure.

4. Linked List Data Structure

In linked list data structure, data elements are connected through a series of nodes. And, each node

contains the data items and address to the next node.

Ad

To learn more, visit Linked List Data Structure.

A linked list

Non linear data structures

Unlike linear data structures, elements in non-linear data structures are not in any sequence. Instead

they are arranged in a hierarchical manner where one element will be connected to one or more

elements.

Non-linear data structures are further divided into graph and tree based data structures.
 1. Graph Data Structure

In graph data structure, each node is called vertex and each vertex is connected to other vertices

through edges.

To learn more, visit Graph Data Structure.

Popular Graph Based Data Structures:

 Spanning Tree and Minimum Spanning Tree

 Strongly Connected Components

 Adjacency Matrix

 Adjacency List

2. Trees Data Structure

Similar to a graph, a tree is also a collection of vertices and edges. However, in tree data structure,

there can only be one edge between two vertices.

To learn more, visit Tree Data Structure.

 Tree data structure example

Popular Tree based Data Structure

 Binary Tree

 Binary Search Tree

 AVL Tree

 B-Tree

 B+ Tree

 Red-Black Tree

IN SUMMARRY

1. Array. An array stores a collection of items at adjoining memory locations. Items that are
the same type are stored together so the position of each element can be calculated or
retrieved easily by an index. Arrays can be fixed or flexible in length.
2. Stack. A stack stores a collection of items in the linear order that operations are applied.
This order could be last in, first out (LIFO) or first in, first out (FIFO).
3. Queue. A queue stores a collection of items like a stack; however, the operation order can
only be first in, first out.
4. Linked list. A linked list stores a collection of items in a linear order. Each element, or
node, in a linked list contains a data item, as well as a reference, or link, to the next item in
the list.
5. Tree. A tree stores a collection of items in an abstract, hierarchical way. Each node is
associated with a key value, with parent nodes linked to child nodes -- or subnodes. There is
one root node that is the ancestor of all the nodes in the tree.
6. Heap. A heap is a tree-based structure in which each parent node's associated key value is
greater than or equal to the key values of any of its children's key values.
7. Graph. A graph stores a collection of items in a nonlinear fashion. Graphs are made up of a
finite set of nodes, also known as vertices, and lines that connect them, also known as edges.
These are useful for representing real-world systems such as computer networks.
8. Trie. A trie, also known as a keyword tree, is a data structure that stores strings as data
items that can be organized in a visual graph.
9.Hash table. A hash table -- also known as a hash map -- stores a collection of items in an
associative array that plots keys to values. A hash table uses a hash function to convert an
index into an array of buckets that contain the desired data item. These are considered
complex data structures as they can store large amounts of interconnected data.

CHARACTERISTICS OF DATA STRUCTURE

Data structures are often classified by their characteristics. The following three characteristics
are examples:
I) Linear or non-linear. This characteristic describes whether the data items are arranged in
sequential order, such as with an array, or in an unordered sequence, such as with a graph.
II) Homogeneous or heterogeneous. This characteristic describes whether all data items in a
given repository are of the same type. One example is a collection of elements in an array, or
of various types, such as an abstract data type defined as a structure in C or a class
specification in Java.
III) Static or dynamic. This characteristic describes how the data structures are compiled.
Static data structures have fixed sizes, structures and memory locations at compile time.
Dynamic data structures have sizes, structures and memory locations that can shrink or
expand, depending on the use.

Some examples of how data structures are used include the following:
Example 1. Storing data. Data structures are used for efficient data persistence, such as
specifying the collection of attributes and corresponding structures used to store records in a
database management system.
Example 2. Managing resources and services. Core operating system (OS) resources and
services are enabled through the use of data structures such as linked lists for memory
allocation, file directory management and file structure trees, as well as process scheduling
queues.
Example 3. Data exchange. Data structures define the organization of information shared
between applications, such as TCP/IP packets.
Example 4. Ordering and sorting. Data structures such as binary search trees -- also known as
an ordered or sorted binary tree -- provide efficient methods of sorting objects, such as
character strings used as tags. With data structures such as priority queues, programmers can
manage items organized according to a specific priority.
Example 5. Indexing. Even more sophisticated data structures such as B-trees are used to
index objects, such as those stored in a database.