DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Please enter at least three characters to search
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workkloads.

Secure your stack and shape the future! Help dev teams across the globe navigate their software supply chain security challenges.

Releasing software shouldn't be stressful or risky. Learn how to leverage progressive delivery techniques to ensure safer deployments.

Avoid machine learning mistakes and boost model performance! Discover key ML patterns, anti-patterns, data strategies, and more.

Related

  • Unlocking the Potential of Binary Search Trees with C# Programming
  • Troubleshooting Memory Leaks With Heap Profilers
  • Python Memo 2: Dictionary vs. Set
  • Manage Hierarchical Data in MongoDB With Spring

Trending

  • Recurrent Workflows With Cloud Native Dapr Jobs
  • A Guide to Container Runtimes
  • Create Your Own AI-Powered Virtual Tutor: An Easy Tutorial
  • The Modern Data Stack Is Overrated — Here’s What Works
  1. DZone
  2. Data Engineering
  3. Data
  4. Data Structures and Their Applications

Data Structures and Their Applications

Data structures are essential components in creating fast and powerful algorithms. They help to manage and organize data.

By 
Huyen Pham user avatar
Huyen Pham
·
Aug. 11, 20 · Tutorial
Likes (5)
Comment
Save
Tweet
Share
39.6K Views

Join the DZone community and get the full member experience.

Join For Free

What Is a Data Structure?

There can be many definitions for a data structure, but the easiest one to understand is the following:

A data structure is a way of organizing data in some fashion so that later on, it can be accessed, queried, or even updated easily and quickly.

It is a collection of values. The values can have relationships among them and they can have functions applied to them. Each one is different in what it can do and what it is best used for. Each is good and is specialized for its own thing.

They are essential components in creating fast and powerful algorithms. They help to manage and organize data so that it will make our code cleaner and easier to understand. Data structures can make the difference between an Okay product and an outstanding one. 

Before getting to Data structures, we have to talk about the abstraction of Data structures. In other words, let’s discuss the concept of Abstract Data Types.

What Is Abstract Data Type (ADT)?

An abstract data type (ADT) is simply an abstraction of a data structure. It provides only the interface to which a data structure must adhere to. The interface doesn’t provide any specific details about how something should be implemented or in what programming language. 

They are called “abstract” because they are just theoretical concepts and every programming language has different ways of implementing it.

Let’s now take a look at a few of some well-known data structures and applications.

Array

A static array is a fixed-length container containing n elements indexable from the range [0, n-1]. Indexable means that each slot/index in the array can be referenced with a number called index key (typically zero-based). This allows random access to any array element.  Static arrays are given as contiguous chunks of memory.

The name assigned to an array is typically a pointer to the first item in the array. It means that given an array named myArray which was assigned the value [‘a’, ‘b’, ‘c’, ‘d’, ‘e’], in order to access the ‘c’ element, we would use the index 2 to lookup the value (myArray[2]).

Arrays are traditionally ‘finite’ in size, means that we define their length/size (i.e. memory capacity) in advance, but there is a concept known as ‘dynamic arrays’ (and of which you’re likely more familiar with when dealing with certain high-level programming languages) which supports the growing (or resizing) of an array to allow for adding more elements to it. But under the hook, the new array (normally with double size compared to the original) is created in order to copy the original array element values over to.
Array values stored in contiguous memory address

Array values stored in contiguous memory address


Array's Application Examples

  • Used as the primitive building blocks to build other data structures such as array lists, heaps, hash tables, vectors and matrices.
  • Used for different sorting algorithms (insertion sort, quick sort, bubble sort and merge sort..).

Linked List

A linked list is different from an array in the order of the elements within the list that is not determined by contiguous memory allocation. Instead, the elements of the linked list can be sporadically placed in memory due to its design, which is that each element of the list (also referred to as a ‘node’) consists of two parts:

  1. The data
  2. A pointer

The data is what we’ve assigned to that element/node, whereas the pointer is a memory address reference to the next node in the list.

Unlike an array, there is no index access. So in order to locate a specific piece of data or element we will have to traverse the entire list until we find the element we’re looking for. That operation takes O(n) complexity.

This is one of the key performance characteristics of a linked list and is why (for most implementations of this data structure) we’re not able to append data/element to the list (because talking about the performance of such an operation, it would require us to traverse the entire list to find the end/last node). Instead linked lists generally will only allow prepending to a list as it’s much faster. The newly added node will then have its pointer set to the original ‘head’ of the list.

There is also a modified version of this data structure called ‘doubly linked list’ which is essentially the same idea but with the exception of the third attribute for each node: a pointer to the previous node (in a normal linked list we only have a pointer to the following node).

Applications of Linked Lists

  • Used for symbol table management in a designing compiler
  • Used in switching between applications and programs in the Operating system (implemented using Circular Linked List)

Application switch in Mac OS (Cmd + Tab)


Application switch in Windows (Alt + Tab)

Tree

A tree is a hierarchical structure where data is organized hierarchically and are connected together. This structure is different from a linked list whereas, in a linked list, items are linked in a linear order.

A tree contains “nodes” (a node has a value associated with it) and each node is connected by a line called an “edge”. These lines represent the relationship between the nodes.

The top-level node is known as the “root” and a node with no children is a “leaf”. If a node is connected to other nodes, then the preceding node is referred to as the “parent”, and nodes following it are “child” nodes.

There are various incarnations of the basic tree structure, each with their own unique characteristics and performance considerations:

  • Binary Tree
  • Binary Search Tree
  • Red-Black Tree
  • B-tree
  • Weight-balanced Tree
  • Heap
  • Abstract Syntax Tree

Tree’s Application Examples

  • Used to implement database indexes (index is a structure that exists independent of the data in the database which improves the query optimizers’ ability to execute the query quickly. In other words, an index is something we create for a column in a table to speed up searches involving that column)

An example of database index implemented with B-tree data structure

  • Heaps data structure: is used by JVM (Java Virtual Machine) to store Java objects.
  • Treap data structure: is used in wireless networking.
Data (computing) Data structure application Database Element Tree (data structure) Abstract data type

Published at DZone with permission of Huyen Pham. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

  • Unlocking the Potential of Binary Search Trees with C# Programming
  • Troubleshooting Memory Leaks With Heap Profilers
  • Python Memo 2: Dictionary vs. Set
  • Manage Hierarchical Data in MongoDB With Spring

Partner Resources

×

Comments
Oops! Something Went Wrong

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends:

Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!