Data Structure and Algorithms 102: Deep Dive into Data Structure and Algorithms, Java

GerryJ — Tue, 28 Jun 2022 19:46:20 +0000

In my previous article, I highlighted an overview of the various data structures and the difference between time and space complexities. However, that was just a scratch on the surface; This article will dig deeper to offer more understanding into linear data structures while also providing some examples. We will highlight some of the most commonly used data types, i.e, arrays and stacks.\

Common Data Structure Operations

These are the fundamental operations that ought to be possible on all data structures.

Access

This operation deals with the accessibility of the pieces that are currently kept in the structure.

Search

The position of a certain element within a specific structure is handled by this procedure.

Insertion

This procedure outlines the procedure for adding additional elements to the structure.

Deletion

The removal of existing elements from the structure is described in this operation.

Arrays

A fixed number of comparable elements with the same name are stored in an array. These elements are stored in contagious memory locations. It is one of the simplest data structures. The majority of contemporary programming languages come with arrays by default.

In the sample block below, I've initialized my list of colors into an array denoted by the square brackets[] and assigned them indexes based on their position in the array

Arrays can be also be multidimensional (2D), see the image below;

Running the above will print out below

Advantages of Arrays

Arrays represent multiple data items of the same type using a single name.
In arrays, the elements can be accessed randomly by using the index number.
Arrays allocate memory in contiguous memory locations for all its elements. Hence there is no chance of extra memory being allocated in case of arrays. This avoids memory overflow or shortage of memory in arrays.
Using arrays, other data structures like linked lists, stacks, queues, trees, graphs etc can be implemented.
Two-dimensional arrays are used to represent matrices.

Disadvantages of arrays

The number of elements to be stored in an array should be known in advance.
An array is a static structure (which means the array is of fixed size). Once declared the size of the array cannot be modified. The memory which is allocated to it cannot be increased or decreased.
Insertion and deletion are quite difficult in an array as the elements are stored in consecutive memory locations and the shifting operation is costly.
Allocating more memory than the requirement leads to wastage of memory space and less allocation of memory also leads to a problem.

Stacks

Stack is kind of data structure which allows operations on data only at one end. It allows access to the last inserted data only. Stack is also called LIFO (Last In First Out) data structure and Push and Pop operations are related in such a way that only last item pushed (added to stack) can be popped (removed from the stack).
There is few more operations supported by stack which are following.

Peek − get the top element of the stack.
isFull − check if stack is full.
isEmpty − check if stack is empty.

Push Operation

// push item on the top of the stack 
public void push(int data) {

   if(!isFull()){
      // increment top by 1 and insert data 
      intArray[++top] = data;
   }else{
      System.out.println("Cannot add data. Stack is full.");
   }      
}

Pop Operation

// pop item from the top of the stack 
public int pop() {
   // retrieve data and decrement the top by 1 
   return intArray[top--];        
}

The main funcation implementing the array would be:

Advantages of Stack

Stack is easy to learn and implement for beginners.
Stacks are used to solving problems that work on recursion.
It allows you to control how memory is allocated and deallocated.

Disadvantages of Stack

Random access of elements is impossible in stacks.
Stacks are neither flexible nor scalable.

Data Structures 101: Introduction to Data Structures and Algorithms.

GerryJ — Mon, 20 Jun 2022 04:43:49 +0000

Difference between Data Structures and Algorithms?
An algorithm is "a finite sequence of instructions, each of which has a clear meaning and can be completed with a finite amount of effort in a finite amount of time_" for a specific activity. Simply put, an algorithm defines a collection of instructions that must be followed in a certain order to get the intended result. Algorithms are often written without regard to the underlying programming languages; that is, an algorithm can be written in more than one computer language.
The capacity of computer scientists to create an effective algorithm is dependent on their ability to arrange data properly. As a result, data structures are systemic methods of structuring data for certain operations. To note, no single data structure works well for all purposes, therefore, it is important to learn the strengths and limitations of several of them.

Data structures can be categorized into;

Linear Data Structure
Non-linear Data Structure

Linear Data Structure

If the elements of a data structure combine to generate a certain order, it is said to be linear. A linear relationship between all the pieces represented by a linear memory location is one technique of describing such linear structure inside memory. A good example of such are Arrays.
The second method uses the idea of pointers or links to create a linear relationship between all of the objects displayed, e.g, Linked lists.
Arrays, Queues, Stacks, and Linked Lists are all instances of linear data structures.

Non-Linear Data Structure

This structure is mostly used to describe data that has a hierarchical relationship between the various parts.

The following are some examples of non-linear data structures;

Graphs
Trees

Characteristics of an Algorithm

Unambiguous − Each of its steps and their inputs/outputs should be clear and must lead to only one meaning.
Input− Have 0 or more well-defined inputs.
Output − Have 1 or more well-defined outputs, and should match the desired output.
Finite− Must terminate after a finite number of steps.
Feasibility− Should be feasible with the available resources.
Independent− An algorithm should have step-by-step directions, which should be independent of any programming code.

Efficiency of an algorithm

The efficiency of an algorithm can be determined by two main factors; time and space

Time complexity

Entails calculating the amount of time it takes to run an algorithm. the rule of thumb is that an effective algorithm should take the shortest time possible given a set of inputs.

Space Complexity

Calculates the amount of memory an algorithm requires to run given a certain set of inputs. the rule of thumb here is that an algorithm should use the minimum amount of memory space possible.

DEV Community: GerryJ