Data structures are specialized methods for arranging and storing data in computers so that actions on the stored data can be carried out more quickly. The use of data structures is widespread and varied in the domains of computer science and software engineering.
Nearly all software systems and programs that have been created involve data structures. The fundamentals of computer science and software engineering also include data structures.
-
Arrays
An array is a fixed-size structure that can house objects of the same data type. It may be a string, a floating-point number, an array of strings, an array of arrays, or even an array of arrays (such as 2-dimensional arrays). Because arrays are indexed, random access is possible.
Operation on arrays
- Traverse: Print each element after going through it.
- Search: Look for a particular element in the array. You can look up an element using either its value or its index.
- Update: Change an element's value at a specific index.
Applications of arrays:
- Used as the building blocks to construct various data structures, such as vectors, matrices, heaps, array lists, and hash tables.
- Used for many sorting algorithms, including bubble sort, merge sort, insertion sort, and rapid sort.
-
Linked Lists
A sequential structure called a linked list is made up of a series of elements in a linear order that are connected to one another. As a result, sequential access to data is required; random access is not an option. Linked lists offer a straightforward and adaptable representation of dynamic sets.
Let's think about the terms below as they relate to linked lists.
- A linked list's components are referred to as nodes.
- Each node has a key and a pointer to the node that comes after it, called next.
- The attribute head indicates the linked list's top element.
- The tail refers to the final member of a linked list.
- The several kinds of linked lists that are accessible are listed below.
- Single-linked list: Items can only be traversed in the forward direction.
- Doubly linked list: Items in the list can be traversed both forward and backward. Every node has a second reference called prev that points to the node before it.
- Linked lists that are circular in nature are those in which the previous head pointer points to the tail and the subsequent tail pointer points to the head.
Operations on linked lists
- A simple linear search is used to locate the first element with key k in the provided linked list, and it delivers a pointer to that element.
- Insert: Add the connected list's key. There are three alternative ways to enter text into a list: in the midst of the list, at the end of the list, or the beginning.
- Delete: Removes a specified linked list's element x. A node cannot be removed in a single action. There are three alternative ways to delete something from a list: starting at the beginning, finishing at the end, or starting in the middle.
Application of linked lists
- used in the design of compilers for managing symbol tables.
- Utilized while utilizing Alt + Tab to jump between apps (implemented using Circular Linked List).
-
Stacks
A stack is a LIFO (Last In, First Out) structure that is frequently used in many computer languages. The final element inserted can be accessed first. Because it resembles a stack of plates in the real world, this structure is called a "stack."
Stack operations:
The two fundamental operations that can be carried out on a stack are listed below.
- Push: Place a component on top of the stack.
- Pop: Remove the first element, then restore it.
- The extra functions listed below are available to examine a stack's status.
- Peek: Bring back the stack's top element without deleting it.
- isEmpty: Determine whether the stack is empty.
- Is full: Determine if the stack is full.
Application of Stacks
- Used to evaluate the expression (e.g., a shunting-yard algorithm for parsing and evaluating mathematical expressions).
- Used in recursive programming to implement function calls.
-
Queues
A queue is a First In, First Out (FIFO) structure, frequently used in many programming languages, and refers to the idea that the element placed first can be accessed first. Because of how much it resembles a line of people waiting to do something in the real world, this structure is called a "queue."
Queue operations:
The two fundamental operations that can be carried out on a queue are listed below.
- Enqueue: Insert an element at the end of the queue.
- Dequeue: Take the item out of the front of the queue.
Applications of queues:
- Used for multithreading thread management.
- Used to put queuing systems into practice (e.g., priority queues).
-
Hash Tables
A data structure called a hash table stores values that each have a key associated with them. Furthermore, if we know the key connected to the value, it facilitates lookup effectively. Because of this, regardless of the volume of data, it is incredibly effective at inputting and searching.
Direct Addressing uses a one-to-one mapping between the values and keys when storing data in a table. When there are many key-value pairs, however, there is an issue with this method. Given the memory space on a standard computer, the table will be enormous with so many records and may be difficult or even impossible to store. Hash tables are used to get around this problem.
Hash Function
A unique function known as the hash function (h) is used to address the issue above directly.
When using direct access, a value is kept in the slot k with key k. We determine the index of the table (slot) where each value belongs using the hash function. The hash value, which identifies the table's index to which the data is mapped, is the value that the hash function calculates for a given key.
h(k) = k % m
- h: Hash function k: Key from which to calculate the hash value m: Hash table size (number of slots available). M should be a prime number far from an exact power of 2.
- When the hash table's size is 20, the hash function h(k) = k% 20 is used. We want to calculate each key's hash value to identify the index where it belongs in the hash table given a set of keys. Consider that we have the hash and the hash table index as our keys.
- 1 → 1%20 → 1
- 5 → 5%
- 20 → 5 \s23 → 23%20 → 3
- 63 → 63%20 → 3
As demonstrated by the final two instances above, collisions can happen when the hash function produces the same index for several keys. We may avoid collisions by choosing an appropriate hash function, h, and employing strategies like chaining and open addressing.
- Utilizes hash tables
- utilized for creating database indexes.
- Employed to create associative arrays.
- Used in the "set" data structure's implementation.
-
Trees
A tree is a hierarchical structure where information is arranged in levels and connected. In contrast to a linked list, which linearly links elements, this structure does not.
Binary Search Trees
As the name implies, a binary search tree (BST) is a binary tree in which data is arranged hierarchically. Values are kept in this data structure in descending order.
The following qualities are present in each node of a binary search tree.
- Key: The node's value that is stored.
- Left: The child's left pointer.
- The arrow points to the appropriate child.
- p: The parent node's pointer.
- A binary search tree displays a special characteristic that differentiates it from other trees. The binary-search-tree property is the name given to this property.
In a binary search tree, let x be a node.
Y.key = x.key if y is a node in the left subtree of x.
If y is a node in x's right subtree, then Y.key = X.key.
Applications of Trees
- Binary Trees: These are the building blocks for expression solvers and parsers.
Many search applications use binary search trees, where data is constantly entering and exiting.
-
Heaps
A Heap is a particular instance of a binary tree in which the values of the parent nodes are compared to those of their offspring, and the nodes are sorted accordingly.
Heaps can be of 2 types:
- According to Min Heap, the parent's key is lower than or equal to that of its children. The term "min-heap property" refers to this. The heap's lowest value will be at the root.
- According to Max Heap, the parent's key is greater than or equal to that of its children. The term for this is the max-heap attribute. The greatest value of the heap will be at the root.
Applications of Heaps
According to Min Heap, the parent's key is lower than or equal to that of its children. The term "min-heap property" refers to this. The heap's lowest value will be at the root.
