In this article, you learn about data structure, types of data structure in Java, operations on data structures and complexity of algorithms.
What is data Structure?
Data Structure is used for organising, managing and storing data efficiently in memory for easy data access and modification.
Data Structure study includes the below points:
- Memory needed for data storage
- Time required to process the data
- Representation of the data in memory
- Operations performed on that data
Data structure in Java is broadly classified into the following two categories:
- Primitive Data structure
- Non-primitive data structure
Primitive Data Structure in Java:
- Primitive data structures in Java are fundamental data structures.
- They can be directly operated by machine instructions.
- They are available in most programming languages as built in types.
- The size of a primitive data structure depends upon the type of data structure.
- Primitive data structure holds a single value at a particular location unlike non primitive data structure.
- int, float, boolean, char are few examples of primitive data structures in Java.
Non-Primitive Data Structure in Java:
- Non-Primitive data structures in Java are derived from primitive data structures.
- They are more complicated than primitive data structures in Java
- They are broadly classified into the following 2 categories:
- Linear data Structure
- Non-Linear data Structure.
Linear data structure in Java:
- A Linear data structure in Java is one in which data is stored in a linear or sequential order
- Linear data structures can be represented in two different ways in memory.
- In the first way, elements are sequentially stored in memory. For example, an array occupies memory in sequential order.
- In the second way, elements have a linear relationship using a link. For example, nodes of the linked list are linked together because their nodes are arranged in memory in non-sequential order.
- Operations performed using linear data structure are traversal, insertion, deletion, searching, sorting and merging.
- Linear data structures do not always make best use of memory and may lead to memory wastage.
- E.g. of linear data structures are as follows:
- Linked list
- An array is a fixed size collection of elements of same data type.
- An array is the most commonly used data structure in many algorithms.
- Elements in an array are stored in contiguous memory locations and are accessed using index.
- The basic operations which can be performed on the array are insert, delete, search, update, and traverse an array.
- Arrays can be of type – one dimensional array, Multidimensional Arrays and Dynamic Arrays
- A linked list is a data structure which contains a set of nodes.
- Each node stores data and address of the next node.
- The nodes connect together to form a structure similar to a chain.
- Linked list can be of type – Single linked list, Double link list and circular linked list.
- A stack is a data structure in Java in which elements are inserted and deleted from one end only.
- Stack is also known as last in first out (LIFO) data structure.
- Array or Linked List can be used to implement a Stack.
- The basic operations a stack could perform are:
- Push — to insert data into a stack and place it on top.
- Pop — to delete the data from the top.
- Peek — to look at the data at the top without removing it.
- Queue is a data structure which allows insertion at one end and deletion at the other end.
- The end at which deletion occurs is called FRONT end.
- The end where insertion occurs is called REAR end.
- Queue is also known as First in First out (FIFO) data structure.
- The queue data structure is implemented with the help of Array.
- Operations which can be performed on the queue are:
- Enqueue — to insert data in a queue and place them at the rear.
- Dequeue — to remove the data from the front.
- Peek — to return the data at the front without removing it.
Hierarchical or Nonlinear data structures in Java:
- Nonlinear data structures store data in a non-sequential order forming a hierarchical relationship between parent and child elements.
- They are spread inside the memory in various places and can only be traced by the address
- Nonlinear data structures in Java are memory efficient.
- Types of nonlinear data structure in Java are as follows:
- A tree is defined as a set of data nodes in which data is arranged in branches and sub-branches.
- Trees represent hierarchical relationships between different elements.
- Tree consists of nodes which are connected by links. A node is represented by a circle and links are used to connect the nodes.
- Unlike the linked list where a node can be connected to only one node, a tree could have a node connected to two or more nodes.
- Trees can be of type: general tree, binary tree, binary search tree etc.
- A graph is a collection of nodes and logical relations between the nodes.
- Graphs can be of type Directed graph, undirected graph, mixed graph, simple graph etc.
Operations on data structures:
The most common operations performed on data structure are as below:
- Select: Select refers to accessing a particular data within a data structure.
- Update: It updates or modifies data in a data structure.
- Search: It finds the presence of a data within a data structure
- Sort: Sorting is a process of arranging all elements in the data structure in a particular order either ascending or descending
- Merge: Merging combines data from two data structures of the same type into a single structure.
- Traverse: traverse each and every node in a systematic order.
Time and Space complexity of algorithms:
Algorithms are programmes using which data structures are implemented.
There are two main measures of the efficiency of an algorithm
- Time complexity: It is a function which determines the amount of time the algorithm takes
- Space complexity: It is a function which determines the amount of memory space the algorithm takes.
Complexity is broadly classified into worst case analysis, average case analysis and best-case analysis.