Data structures are fundamental to any programming language. The choice of a particular data structure has a significant impact on the functionality and performance of Java applications, thus it is worthwhile to master data structures in Java.
A data structure is defined as a format for arranging, processing, accessing, and storing data. Data structures are the combination of both simple and complex forms, all of which are made to organise data for a certain use. Users find it simple to access the data they need and use it appropriately thanks to data structures.
Data Structure in java is defined as the collection of data pieces that offers an effective means of storing and organising data in a computer. Linked List, Stack, Queue, and arrays are a few examples of java data structures.
1. Efficiency
2. Reusability
3. Processing Speed
4. Abstraction
5. Data Searching
Static Data Structures are the Data structures whose size is declared and fixed at Compile Time and cannot be changed later are called Static Data structures.
Dynamic Data Structures are the Data Structures whose size is not fixed at compile time and can be decided at runtime depending upon requirements are called Dynamic Data structures.
1. Primitive Data Structures
2. Non-primitive Data Structures
Primitive data Structures are also called Primitive Data Types. byte, short, int, float, char, boolean, long, and double are primitive Data types.
Non-primitive data structures are user-defined structures built from primitive data types, enabling the storage and manipulation of complex data, like arrays, linked lists, stacks, queues, trees, and graphs
1. Linear Data Structures
2. Non-Linear Data Structures
The elements arranged in a linear fashion are called Linear Data Structures. Here, each element is connected to one other element only. Linear Data Structures are as follows:
1. Arrays
2. Stack
3. Queue
4. Linked List
The elements arranged in a non-linear fashion are called Non-Linear Data Structures. Here, each element is connected to n-other elements. Non-Linear Data Structures are as follows:
1. Trees
2. Heap
3. Hash
Array is a linear data structure that stores a collection of elements of the same data type. Elements are allocated contiguous memory, allowing for constant-time access. Each element has a unique index number.
An array is the simplest data structure where a collection of similar data elements takes place and each data element can be accessed directly by only using its index number. Arrays are divided by two types :
1. Single Dimensional Array
2. Multi Dimensional Array
1. Random access
2. Easy sorting and iteration
3. Replacement of multiple variables
1. Size is fixed
2. Difficult to insert and delete
3. If capacity is more and occupancy less, most of the array gets wasted
4. Needs contiguous memory to get allocated
1. For storing information in a linear fashion
2. Suitable for applications that require frequent searching
Linked list is a linear data structure that stores data in nodes, which are connected by pointers. Unlike arrays, nodes of linked lists are not stored in contiguous memory locations and can only be accessed sequentially, starting from the head of list. Linked list data structure helps the required objects to be arranged in a linear order.Linked List are divided by three types :
1. Singly-linked List
2. Doubly Linked List
3. Circular Linked List
1. Dynamic in size
2. No wastage as capacity and size is always equal
3. Easy insertion and deletion as 1 link manipulation is required
4. Efficient memory allocation
1. If head Node is lost, the linked list is lost
2. No random access is possible
1. Suitable where memory is limited
2. Suitable for applications that require frequent insertion and deletion
A stack is a representation of nodes. There are two components to each node: data and next (storing address of next node). Each node’s data portion contains the assigned value, and its next pointer directs the user to the node that has the stack’s subsequent item. The highest node in the stack is referred to as the top.
1. Linear Data Structures using Java
2. Follows LIFO: Last In First Out
3. Only the top elements are available to be accessed
4. Insertion and deletion takes place from the top
5. All operation works in constant time i.e, O(1)
Example : A stack of plates, chairs, etc
1. push(ele) – used to insert element at top
2. pop() – removes the top element from stack
3. isEmpty() – returns true is stack is empty
4. peek() – to get the top element of the stack
1. Maintains data in a LIFO manner
2. The last element is readily available for use
3. All operations are of O(1) complexity
1. Manipulation is restricted to the top of the stack
2. Not much flexible
1. Recursion
2. Parsing
3. Browser
4. Editors
The queue is called an abstract data structure. Data is always added to one end (enqueued), and removed from the other (dequeue). Queue uses the First-In-First-Out approach and data item that was stored initially will be accessed first in a queue.
1. Linear Data Structures using Java
2. Follows FIFO: First In First Out
3. Insertion can take place from the rear end.
4. Deletion can take place from the front end.
5. All operation works in constant time i.e, O(1)
Example : Queue at ticket counters, bus station
1. enqueue(ele) – used to insert element at top
2. dequeue() – removes the top element from queue
3. peekfirst() – to get the first element of the queue
4. peeklast() – to get the last element of the queue
1. Maintains data in FIFO manner
2. Insertion from beginning and deletion from end takes O(1) time
Two popular variations of queues are Circular queues and Dequeues.
1. Scheduling
2. Maintaining playlist
3. Interrupt handling
Tree is a non-linear, hierarchical data structure consisting of nodes connected by edges, with a top node called the root and nodes having child nodes. It is widely used in file systems, databases, decision-making algorithms, etc.
1. Binary Tree
2. Binary Search Tree
3. AVL Tree
4. Red-Black Tree
The branches of the tree are made up of up to two child nodes for each node. The left and right nodes are the common names for the two youngsters. Child nodes make references to their parents, whereas parent nodes are nodes with children.
1. Hierarchical Data Structure
2. The topmost element is known as the root of the tree
3. Every Node can have at most 2 children in the binary tree
4. Can access elements randomly using index
Example : File system hierarchy
1. preorder(root) : print-left-right
2. postorder(root) : left-right-print
3. inorder(root) : left-print-right
1. Can represent data with some relationship
2. Insertion and search are much more efficient
1. Sorting is difficult
2. Not much flexible
1. File system hierarchy
2. Multiple variations of the binary tree have a wide variety of applications
The binary search tree is an advanced algorithm which is used to analyse the nodes, branches and many more. The BST was developed using the architecture of a fundamental binary search algorithm, allowing for quicker node lookups, insertions, and removals.
1. A binary tree with the additional restriction
2. Restriction the left child must always be less than the root node
3. Restriction the right child must always be greater than the root node
4. Insertion, Deletion, Search is much more efficient than a binary tree
1. Maintains order in elements
2. Can easily find the min and max Nodes in the tree
3. In order, traversal gives sorted elements
1. Random access is not possible
2. Ordering adds complexity
1. Suitable for sorted hierarchical data
Heap is a complete binary tree data structure that satisfies the heap property. Heaps are usually used to implement priority queues, where the smallest or largest element is always at the root of the tree.
1. Binary Heap can be visualized array as a complete binary tree
2. Arr[0] element will be treated as root
3. length(A) – size of array
4. heapSize(A) – size of heap
5. Generally used when we are dealing with minimum and maximum elements
1. Can be of 2 types: min heap and max heap
2. Min heap keeps the smallest element and top and max keep the largest
3. O(1) for dealing with min or max elements
1. Random access is not possible
2. Only min or max element is available for accessibility
1. Suitable for applications dealing with priority
2. Scheduling algorithm
3. caching
Hashing is a technique that generates a fixed-size output (hash value) from an input of variable size using mathematical formulas called hash functions. Hashing is commonly used in data structures for efficient searching, insertion and deletion and plays a key role in software applications like secure data retrieval, password storage, cryptography, digital signatures, etc.
1. Uses special Hash function
2. A hash function maps an element to an address for storage
3. This provides constant-time access
4. Collision resolution techniques handle collision
5. Collision resolution technique Chaining
6. Collision resolution technique Open Addressing
1. The hash function helps in fetching elements in constant time
2. An efficient way to store elements
1. Collision resolution increases complexity
1. Suitable for the application needs constant time fetching
Basically it is a group of edges and vertices. Graph representation G(V, E); where V(G) represents a set of vertices and E(G) represents a set of edges. The graph can be directed or undirected. The graph can be connected or disjoint
1. finding connectivity
2. Shortest path
3. min cost to reach from 1 pt to other
4. Min spanning tree
1. Storing graph(Adjacency list and Adjacency matrix) can lead to complexities.
1. Suitable for a circuit network
2. Suitable for applications like Facebook, LinkedIn, etc
3. Medical science