This is my story as a proud Binusian!

Diary of Binusian

Posted on by Posted in Data Structures

A data structure is a specialized format for organizing and storing data. General data structure types include the array, the file, the record, the table, the tree, and so on. Any data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropriate ways.

Data structure could be divided into:

  1. Static Memory Allocation (Homogenous)
  2. Dynamic Memory Allocation (Heterogenous)

Some common examples of data structures include:

  • Arrays
  • Linked lists
  • Queues
  • Stacks
  • Binary trees
  • Hash tables

 

ARRAY

Arrays in C act to store related data under a single variable name with an index, also known as a subscript. It is easiest to think of an array as simply a list or ordered grouping for variables of the same type. As such, arrays often help a programmer organize collections of data efficiently and intuitively.

Characteristics of array:

  • A collection of similar data elements
  • These data elements have the same data type (homogenous)
  • The elements of the array are stored in consecutive memory locations and are referenced by an index
  • Array index starts from zero

Storing array values:

  • Initialize the elements
  • Input values for the elements
  • Assign values for the elements

There are a number of operations that can be performed on arrays. They are:

  • Traversing (It is used to access each data item exactly once so that it can be processed)
  • Insertion (It is used to add a new data item in the given collection of data items)
  • Searching (It is used to find out the location of the data item if it exists in the given collection of data items)
  • Deletion (It is used to delete an existing data item from the given collection of data items)
  • Merging (It is used to combine the data items of two sorted files into single file in the sorted form)
  • Sorting (It is used to sort the data items based on given instructions)

 

POINTER

Pointer is a data type whose value refers to another value stored elsewhere in computer memory using its address. Like any variable or constant, you must declare a pointer before using it to store any variable address.

The two most important operators used with pointer type are:

  • & the address operator
  • * the dereferencing operator

How to use pointers?

There are a few important operations, which we will do with the help of pointers very frequently. (a) We define a pointer variable, (b) assign the address of a variable to a pointer and (c) finally access the value at the address available in the pointer variable. This is done by using unary operator* that returns the value of the variable located at the address specified by its operand. The following example makes use of these operations:

LINKED LIST

A linked list is a linear collection of data elements, called nodes pointing to the next node by means of pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

Following are important terms to understand the concepts of Linked List:

  1. Link − Each Link of a linked list can store a data called an element.
  2. Next − Each Link of a linked list contain a link to next link called Next.
  3. LinkedList − A LinkedList contains the connection link to the first Link called First.

As per above shown illustration, following are the important points to be considered.

  1. LinkedList contains an link element called first.
  2. Each Link carries a data field(s) and a Link Field called next.
  3. Each Link is linked with its next link using its next link.
  4. Last Link carries a Link as null to mark the end of the list.

Types of Linked List:

  1. Simple Linked List − Item Navigation is forward only.
  2. Doubly Linked List − Items can be navigated forward and backward way.
  3. Circular Linked List − Last item contains link of the first element as next and and first element has link to last element as prev.

Basic operations of Linked List:

  1. Insertion − add an element at the beginning of the list.
  2. Deletion − delete an element at the beginning of the list.
  3. Display − displaying complete list.
  4. Search − search an element using given key.
  5. Delete − delete an element using given key.

Linked List vs Array

Array:

  • Linear collection of data elements
  • Store value in consecutive memory locations
  • Can be random in accessing of data

Linked List:

  • Linear collection of nodes
  • Doesn’t store its nodes in consecutive memory locations
  • Can be accessed only in a sequential manner

 

 

QUEUE

Queue is also an abstract data type or a linear data structure, in which the first element is inserted from one end called REAR(also called tail), and the deletion of exisiting element takes place from the other end called as FRONT(also called head). This makes queue as FIFO data structure, which means that element inserted first will also be removed first.

The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.

Basic features of Queue

  1. Like Stack, Queue is also an ordered list of elements of similar data types.
  2. Queue is a FIFO( First in First Out ) structure.
  3. Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.
  4. peek( ) function is oftenly used to return the value of first element without dequeuing it.

Applications of Queue

Queue, as the name suggests is used whenever we need to have any group of objects in an order in which the first one coming in, also gets out first while the others wait for there turn, like in the following scenarios :

  1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
  2. In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service representative is free.
  3. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive, First come first served.

 

STACK

A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack. Stack is used to store the data in such a way that element inserted into the stack will be removed at last (LIFO / Last In First Out).

There are basically three operations that can be performed on stacks .

  1. inserting an item into a stack (push).
  2. deleting an item from the stack (pop).
  3. displaying the contents of the stack(pip).

 

BINARY TREE

What is binary tree?

  • A data structure which is defined as a collection of elements called the nodes
  • Every node contains a left pointer, a right pointer, and a data element

More tree terminology:

  • The depth of a node is the number of edges from the root to the node.
  • The height of a node is the number of edges from the node to the deepest leaf.
  • The height of a tree is a height of the root.
  • A full binary tree.is a binary tree in which each node has exactly zero or two children.
  • A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.

 

DATA TYPE

Data Type is a collection of objects and a set of operations that act on those objects.

For example, the data type int consists of:

  • objects : 0, +1, -1, +2, -2, etc
  • operations : +, -, *, /, %, etc

Example of predefined data types are int, char, float.

 

ABSTRACT DATA TYPE

Abstract Data Type (ADT) is a data type that is organized in such a way that the specification of the objects and the specification of the operations on the objects is separated from the representation of the objects and the implementation of the operations.

C/C++ has a concept called class and struct which assist the programmer in implementing abstract data type.

Example of ADT:

For example, an abstract stack, which is a last-in-first-out structure, could be defined by three operations: push, that inserts a data item onto the stack; pop, that removes a data item from it; and peek or top, that accesses a data item on top of the stack without removal. An abstract queue, which is a first-in-first-out structure, would also have three operations: enqueue, that inserts a data item into the queue; dequeue, that removes the first data item from it; and front, that accesses and serves the first data item in the queue. There would be no way of differentiating these two data types, unless a mathematical constraint is introduced that for a stack specifies that each pop always returns the most recently pushed item that has not been popped yet. When analyzing the efficiency of algorithms that use stacks, one may also specify that all operations take the same time no matter how many data items have been pushed into the stack, and that the stack uses a constant amount of storage for each element.

 

Leave a comment

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