What is Data Structure?

Every algorithm which solves useful problem has data structure. Data structures are mechanism to keep data (primitive data type) arranged inside computer’s memory in some structure. They help algorithm to meet efficiency which otherwise not possible. It is not unusual to map computational problem into data structure at very first stage of problem solving. They are building blocks of modern computer programming model.

Students in classroom - real life data structure example

Students in classroom

Let’s consider we want to arrange the name of students in alphabetical order using program. When we formulate a solution we need a way to keep the list of students before we apply the sorting algorithm. Obviously we will use an array (list) where we will keep them and use our algorithm to iterate over it and do sorting algorithm. We can see array and other important data structures are so indispensable and often used, they offered as core features of programming language.

Data Structure in real life

Dictionary book

Dictionary

In dictionary, words are sorted in alphabetical order and it enables to search word quickly. If words (data) are not structured in sorted order than it’s impossible to search any word. Dictionary is an example of data structure we use in real life. There are many other examples of real life data structure use, in fact they are inspiration to computational data structure for long time.

Abstract Data Types

Abstract data type (ADT) are blueprint for data structure implementation. They specify operations to carry out as well as computational complexity for those operations. Data structures are concrete implementation of Abstract Data Types. Abstract Data Type is a mathematical model which define the operation, values and behaviours of the data type in user’s perspective.

Integers

Integers are ADT with

values: .. -2, -1, 0, 1, 2, ..

Operations:  addition, subtraction, multiplication, division

as per general mathematics.

However computers are free to represent Integer as they want to.

Important Abstract Data Types

Container

Container is a collection of other objects.

Container Abstract Data Type

Container Abstract Data Type

Three important characteristics:

  1. Access – How we access the objects? It will be using index in case of Array, LIFO (Last in First Out) in case of Stacks and FIFO (First in First Out) in case of Queue.
  2. Storage – How we are storing the object in container?
  3. Traversal – How we are traversing the objects of the container?

Following operations on the Container Class desired:

  1. Create
  2. Insert
  3. Delete
  4. Delete all
  5. Access the object
  6. Access the objects count

All operations are self-explanatory. It is to explain the essence of Abstract Data Types. In real life Container have various types of implementation.

List

List has values and we can count the number of values. Same value may seem multiple times. List is a basic example of container.

List Abstract Data Type

List Abstract Data Type

Set

Set has distinct values not in a particular order.

Set Abstract Data Type

Set Abstract Data Type

Map

Map built of collection of pairs (Key, Value). Key appear only once in the collection. It is also known as associative array, symbol table, or dictionary.

Map Abstract Data Type

Map Abstract Data Type

Graph

Graph abstract data types made up of Nodes (also called vertices or points) and Edges (also called arcs or lines). Few operations are like adjacent of a node, neighbours of a node, adding node (vertex), removing node (vertex) or others.

Graph Abstract Data Type

Graph Abstract Data Type

Stack

Stack abstract data type is collection of elements with two important operations:

  1. Push – Adding element in collection.
  2. Pop – Removing element from collection. Elements removed from collection in Last In First Out (LIFO) order.
Stack abstract data type lifo

Stack abstract data type lifo

Queue

Queue abstract data type a collection of elements where element added in rear side (called Enqueue) and removed from front side (called Dequeue). It is also known as First In First Out  (FIFIO) data structure.

Queue FIFO abstract data type

Queue FIFO abstract data type

This is a brief introduction of Data Structure to get started our journey to understand it in deep. Please see the reference section to go through more details about terminologies used in this article.

Reference

  1. Data structure wikipedia article. Ref
  2. Abstract Data Type wikipedia article. Ref
  3. A very good introduction to data structure. Youtube Video Ref

3 Replies to “What is Data Structure?”

  1. Very very good post keep it up, and do some more tutorials like this on other essential data structures please.

    1. Thanks for reading. It’s satisfying that you find it useful. You will be updated with new articles as they published. I have plan to cover most of the important data structures over coming days. Hope you will like them too.

Leave a Reply

Your email address will not be published. Required fields are marked *