Common Data Structures and their applications.

A data structure is a particular format of organizing data for efficient processing, retrieval and storage. There are several reasons why data structures are very important. Data has become a very crucial part of every sector around the globe this may be attributed to an explosive advancement in technology in the past few years. If you’re in working in the technology sector being able to handle data well and derive value from it is an invaluable skill. This is one of the reasons why recruiters demand that their prospective employees should have knowledge in data structures and algorithms.

In this article I’ll be highlighting some of the most commonly used data structures, operations performed on them and their respective applications.

1. Arrays.

Photo by American Public Power Association on Unsplash

It is the simplest and most common data structures whose usage extends across most programming languages.

Arrays are used to store homogenous data in contiguous memory locations. Any data item that is stored in an array is referred to as an element and each element is allocated a unique identifier in the memory that is known as an index.

Contiguous memory allocations refer to model of storing data that entails storage of data items in successive memory blocks. Homogenous data refers to data of similar type and format we also have heterogenous data which is simply the opposite.

Author

There are two types of arrays; One dimensional arrays and Multi-dimensional arrays (An array of arrays).

There are various operations performed on arrays depending on the usage one intends to put them into:

Insertion operation — as the word suggests this is the addition of an element at a specific index location

Deletion operation — removing an element from a specific index location in an array.

(Both insertion an deletion are performed with O(n) complexity)

Traversing — This process involves visiting each and every element in the array, can be done with intent to return a particular element or all elements.

Applications of Arrays.

Implementing other data structures such as stacks, queues, hash tables and heaps.

Performing mathematical matrix operations.

One dimensional arrays are used in implementing searching and sorting algorithms.

Arrays are also applied in implementing CPU scheduling algorithms.

2.Stacks.

A stack of Books Photo by Delano Ramdas on Unsplash

A linear data structure that follow that last in first(LIFO) out approach in performing operations. The LIFO principal can be likened to a pile plates neatly arranged on top of each other where the last plate is the one that can be removed first. As with a pile of plates where one can add or remove a plate from the pile, a stack has its own set of operations that resemble.

Operations Performed on Stacks.

Pop — Involves removing an element from the stack.

Push — This operation is performed when adding elements to the stack.

Peek — This is used to return the topmost element without removing it from the stack.

IsEmpty — Carried out before popping an element to determine if the stac is empty or not.

IsFull — Carried out before pushing an element into the stack to determine if the stack is full or not.

When implementing this operations using an array they all take a constant time complexity of O(1).

Applications of Stack.

1. The redo and undo feature in editors and compilers which saves us time when you’ve messed on the original document and would like to go back to the previous state.
2. Applied in algorithms such as Tower of Hanoi and in tree traversals.
3. It is also used in evaluating and conversion of infix, postfix and prefix expressions.
4. Stack can also applied in reversing strings.
5. It is used in storing solutions if previous problems during the backtracking process . (Backtracking is a recursive algorithm used in solving optimization problems)

3.Queue.

Photo by Melanie Pongratz on Unsplash

Is a linear data structure that allows operations to be performed on both ends of the queue. It follows the First In First Out approach, which simply means that the first element to be added to a queue is the first one the first to exit.

A group of people who have lined to receive services from a common service point is a perfect example of how queues behave.

A queue normally has two sections the front part and the end of the queue.

Operations Performed on Queue.

Dequeue — This is the process of removing an element from any queue at the front of the queue

Enqueue — Involves adding elements to the queue at the end of a queue.

IsEmpty — This is an operation aimed at establishing whether a queue contains elements or not. Normally performed with intent to return an element from the queue.

IsFull — Used to determine whether a queue has any space left or not. Performed with ana intent to add an new element to the queue.

Peek — Used to return a value from the front of the queue without removing it from the queue.

Queues can be implemented across all the common programming languages. Arrays are mostly used in implementing queues although stacks and linked lists can also be used.

There are five common types of queues and this include: The Simple queues, Circular queues, double ended queues and the priority queues.

Application Queues.

1. Handling interrupts in real time systems in a FIFO approach.
2. Emergence call centers queue phone calls whenever the calling rate is intense.
3. Disk and CPU scheduling whenever users are accessing a common shared resource at the same time.

4.Linked Lists.

Source: Geeks for Geeks

It is one of the most used linear data structure. A linked list consists of a sequence of Nodes, that store data as well as an address to the next node. The last node of any linked list points to null, signifying the end .

There are three different kinds of LinkedList: Doubly linked lists, circular linked lists and singly linked lists.

1.Singly Linked lists have the simplest form, every node contains some data and an address to the next node.

2.Doubly linked lists on the other hand have nodes that store data and have two address. The two address point in opposite making it possible to move back and forth between two nodes.

3.Circular linked lists can be either singly or doubly. They have one unique characteristic though, the last node has an address that links it to the node at the start of the list.

Each and every type of linked lists have their own advantages and disadvantages. For instance doubly linked are easier to traverse than the other types. But I wouldn't cover that here.

Operations performed of linked lists.

Traversing — Involves visiting each an every node.

Insertion — Adding nodes to a linked list; at the beginning, end or in between other nodes.

Deletion — Removing a node from a linked lists.

Merging — Combining two linked lists into one.

Sorting — Arranging nodes in a linked lists in a particular order.

Applications of Linked Lists.

Useful in implementing stacks and queues.

Allocation of Dynamic memory.

Storage of records in phone directories.

Used in representation of sparse matrices.

Applied in navigation of previous and next browser pages , images in images viewers as well as songs in music applications.

I might as well add Trees , Tries and Graphs but this post would be very long. They deserve a separate post.

Thanks for reading.

Isaac Tonyloi.