This content originally appeared on DEV Community and was authored by JudoCoder
Data Structures and Algorithms are a very important topic for every beginner programmer to learn about.
Data structures and algorithms are two terms that are often mentioned in the same sentence. In a data structure, you will find the different types of data, such as arrays, linked lists, queues, stacks, and trees. What exactly are they? How do they work? How can you use them to solve real-world problems?
To answer these questions, this article will provide 8 types of data structures and algorithms that you might encounter in your everyday life. The article starts by giving the basics for each data structure or algorithm before explaining its function. As an example for each type of data structure or algorithm, we’ve included a brief case study where it has been used.
What is a Data Structure?
A data structure is a way to organize and manage data. Data structures can be implemented in many different programming languages, but they typically have four main components.
The first component of a data structure is the "struct." The struct is what holds all of the data for your data structure. This "struct" part also often refers to functions that are used to manipulate the data being stored in the struct.
The second component of a data structure is "pointers." Pointers are variables that reference other variables. For example, you could use pointers to point to a person's name or their address.
In some languages, you might even be able to pass a pointer as an argument when calling a function.
The third component of a data structure is "memory allocation." Memory allocation helps you allocate memory for the struct and any variables that it stores values into. It ensures that your program doesn't run out of memory while performing tasks.
Finally, the last component of a data structure is "algorithms." Algorithms are functions that are applied to your struct or any variables stored within that struct. They help your program perform tasks like search or sorting through your struct's values more efficiently than without them.
Types of Data Structures
While there are numerous types of data structures, we here are only covering eight types of data structures: arrays, linked lists, stacks, queues, binary trees, sets/bags, graphs and hash tables. Below we give a brief explanation of how each of them work with some examples of each type.
Arrays
Arrays can be an effective way to organize a list of data. To use an array, start by naming your array and assigning values to each index in the array. Arrays are often used for storing lists as well as individual data items such as letters in a word game.
Linked Lists
Linked lists are a data structure that uses two pointers and an ordering number, which is typically represented as a string of characters. The first pointer is called the head and the second pointer is called the tail. This type of data structure can also be implemented with just one pointer.
Linked lists are used for storing and organizing any type of data, including strings, integers, or even other linked lists. They're useful because they can be accessed from anywhere within the list without need for searching. Additionally, they're easy to add items to and remove items from the list because objects only need to be added at one end and removed at the other.
Some examples of use include building a queue, implementing a stack, or linking together large amounts of related data structures in order to create a graph.
Stacks
A stack is a data structure where objects are pushed on the back and popped off the front. This means that each time an object is added to or removed from the stack, the entire stack must be shifted. A stack is typically represented as an array of pointers.
Stacks can be implemented with any language but most commonly use underlying LIFO (last-in, first-out) representations where the last object pushed onto the stack is the first object popped off of it.
One common use for stacks is in algorithms that retrieve items from a series of lists based on their index number. For example:
class Stack {
public:
function Stack() { } // Constructor
void remove(int i) { int k = curr[i]; delete curr[i]; return k; } // Removes and returns a value from this stack
void push(int i, int j) { curr[i] = j; } // Inserts an item into this stack
}
// To remove a value at position position in stack stk1:
stk1.remove(99);
Queues
A queue is a data structure that can be used for storing and retrieving elements in first-in-first-out order. Queues are often used to store information that has a limited, fixed size and allows accessing any element without having to search through the entire list. For example, there might be a queue of people who have reserved tables at your local restaurant.
Each person's reservation is placed in the queue with their name and time until their reservation starts. When someone arrives at the restaurant, they check in at the front desk. The person who checked in last will likely have their table waiting for them while those waiting will get added to the back of the list as they continue checking in.
Queues are typically implemented using linked lists or arrays. To implement queues with linked lists, we would use a doubly linked list where each node stores two pointers: one pointing to the next node and one pointing to the element stored at that node (or NULL if it is empty). This implementation has advantages over arrays because it prevents singly or doubly linked nodes from becoming duplicated or lost when inserting or removing items from the queue.
Binary Trees
A binary tree is a data structure made up of nodes with two child nodes, each of which may have one or more children. It's a type of hierarchical data structure.
Binary trees are used in various ways: they are the building blocks for linked lists, the storage format for sets and bags, and they can be used in graphs and hash tables too, among other things. A binary tree can also be simulated with stacks, queues and arrays.
Sets
In a set, you have an explicit list of the values that are in it. In a set, you can add or remove any value to or from the data structure without affecting the other values in it.
A set is used to store unique items--anything that doesn't already exist in a set is considered logically "unique." This is often used for things like passwords, where one password per user would be stored as a set.
Graphs
Graphs are an excellent data structure for representing networks. They're used in many fields, such as social science, to represent relationships between people, objects and events. For example, a graph could be created to represent your Facebook friends and their relationship status to you.
A node is the main point of interest in a graph while edges are the connections between nodes. Nodes are usually represented by points in a two dimensional plane while edges may have one or more vertices connecting them to other nodes. In order to make graphs easy to read and understand, the nodes usually have names that describe the types of relationships they have with the other nodes in the graph.
The eight basic types of graphs are: undirected graphs (simple), directed graphs (simple), weighted graphs, sparse graph, dynamic graph (diameter), directed acyclic graph (directed simple) and hypergraph.
Hash Tables
A hash table is a data structure that maps a key to a value. The map is called a hash function, and the map data structure is called a hash table. We use this data structure when we need to quickly find an item in our list or set.
In computer programming, we use hash tables to store associations between keys and values. A common example of its usage can be found in the command line interface in Linux or Mac OS X when we see "hash:" before the item name.
Those two examples mentioned above are just some examples of how you might use a hash table; there are many other uses as well.
Like arrays, hash tables allow for quick lookups by key. Hash table has a constant-time lookup O(1) in the best case scenario and O(N) lookup in the worst case scenario (such as when there are collisions in the list)
Conclusion
While there are many types of data structures, these are the most used/common ones that you will find being used everywhere in your everyday life. We intend this article to serve as an introduction to data structures that you can use to build your knowledge upon.
Knowledge of data structures is important because it allows you to build complex applications and you will be asked about them in your technical interview.
The good news is, JudoCoder.com provides handpicked selection of all sorts of data structures and algorithm questions, most of these questions have been asked in a real interview!.
I would suggest you create a free account at judocoder.com and start practicing your skills. You will be prepared in no time!..
No matter what you do, make sure you practice! You'll be happy you did when it's time for your interview.
This content originally appeared on DEV Community and was authored by JudoCoder
JudoCoder | Sciencx (2021-12-13T23:06:02+00:00) 8 Types of Data Structures for Beginners. Retrieved from https://www.scien.cx/2021/12/13/8-types-of-data-structures-for-beginners/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.