Data structures in java
A data structure is a particular way of organizing data in a computer so that it can be used effectively.
For example, we can store a list of items having the same data-type using the array data structure.
Click to enlarge
Array Data Structure
This page contains detailed tutorials on different data structures (DS) with topic-wise problems.
Topics:
Array
Linked List
Stack
Queue
Binary Tree
Binary Search Tree
Heap
Hashing
Graph
Matrix
Misc
Advanced Data Structure
Overview:
Overview of Data Structures | Set 1 (Linear Data Structures)
Overview of Data Structures | Set 2 (Binary Tree, BST, Heap and Hash)
Overview of Data Structures | Set 3 (Graph, Trie, Segment Tree and Suffix Tree)
Abstract Data Types
Arrays in data structure:
Java provides a data structure, the array, which stores a fixed-size sequential collection of elements of the same type. An array is used to store a collection of data, but it is often more useful to think of an array as a collection of variables of the same type.
Instead of declaring individual variables, such as number0, number1, ..., and number99, you declare one array variable such as numbers and use numbers[0], numbers[1], and ..., numbers[99] to represent individual variables.
This tutorial introduces how to declare array variables, create arrays, and process arrays using indexed variables.
Declaring Array Variables
To use an array in a program, you must declare a variable to reference the array, and you must specify the type of array the variable can reference. Here is the syntax for declaring an array variable −
Syntax
dataType[] arrayRefVar; // preferred way.
or
dataType arrayRefVar[]; // works but not preferred way.
Note − The style dataType[] arrayRefVar is preferred. The style dataType arrayRefVar[] comes from the C/C++ language and was adopted in Java to accommodate C/C++ programmers.
Example
The following code snippets are examples of this syntax −
double[] myList; // preferred way.
or
double myList[]; // works but not preferred way.
Creating Arrays
You can create an array by using the new operator with the following syntax −
Syntax
arrayRefVar = new dataType[arraySize];
The above statement does two things −
It creates an array using new dataType[arraySize].
It assigns the reference of the newly created array to the variable array
Declaring an array variable, creating an array, and assigning the reference of the array to the variable can be combined in one statement, as shown below −
dataType[] arrayRefVar = new dataType[arraySize];
Alternatively you can create arrays as follows −
dataType[] arrayRefVar = {value0, value1, ..., valuek};
The array elements are accessed through the index. Array indices are 0-based; that is, they start from 0 to arrayRefVar.length-1.
Example
Following statement declares an array variable, myList, creates an array of 10 elements of double type and assigns its reference to myList −
double[] myList = new double[10];
Following picture represents array myList. Here, myList holds ten double values and the indices are from 0 to 9.
Java Array
Processing Arrays
When processing array elements, we often use either for loop or foreach loop because all of the elements in an array are of the same type and the size of the array is known.
Example
Here is a complete example showing how to create, initialize, and process arrays −
Live Demo
public class TestArray {
public static void main(String[] args) {
double[] myList = {1.9, 2.9, 3.4, 3.5};
// Print all the array elements
for (int i = 0; i < myList.length; i++) {
System.out.println(myList[i] + " ");
}
// Summing all elements
double total = 0;
for (int i = 0; i < myList.length; i++) {
total += myList[i];
}
System.out.println("Total is " + total);
// Finding the largest element
double max = myList[0];
for (int i = 1; i < myList.length; i++) {
if (myList[i] > max) max = myList[i];
}
System.out.println("Max is " + max);
}
}
This will produce the following result −
Output
1.9
2.9
3.4
3.5
Total is 11.7
Max is 3.5
The foreach Loops
JDK 1.5 introduced a new for loop known as foreach loop or enhanced for loop, which enables you to traverse the complete array sequentially without using an index variable.
Example
The following code displays all the elements in the array myList −
Live Demo
public class TestArray {
public static void main(String[] args) {
double[] myList = {1.9, 2.9, 3.4, 3.5};
// Print all the array elements
for (double element: myList) {
System.out.println(element);
}
}
}
This will produce the following result −
Output
1.9
2.9
3.4
3.5
Passing Arrays to Methods
Just as you can pass primitive type values to methods, you can also pass arrays to methods. For example, the following method displays the elements in an int array −
Example
public static void printArray(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
You can invoke it by passing an array. For example, the following statement invokes the printArray method to display 3, 1, 2, 6, 4, and 2 −
Example
printArray(new int[]{3, 1, 2, 6, 4, 2});
Returning an Array from a Method
A method may also return an array. For example, the following method returns an array that is the reversal of another array −
Example
public static int[] reverse(int[] list) {
int[] result = new int[list.length];
for (int i = 0, j = result.length - 1; i < list.length; i++, j--) {
result[j] = list[i];
}
return result;
}
The Arrays Class
The java.util.Arrays class contains various static methods for sorting and searching arrays, comparing arrays, and filling array elements. These methods are overloaded for all primitive types.
Sr.No. Method & Description
1
public static int binarySearch(Object[] a, Object key)
Searches the specified array of Object ( Byte, Int , double, etc.) for the specified value using the binary search algorithm. The array must be sorted prior to making this call. This returns index of the search key, if it is contained in the list; otherwise, it returns ( – (insertion point + 1)).
2
public static boolean equals(long[] a, long[] a2)
Returns true if the two specified arrays of longs are equal to one another. Two arrays are considered equal if both arrays contain the same number of elements, and all corresponding pairs of elements in the two arrays are equal. This returns true if the two arrays are equal. Same method could be used by all other primitive data types (Byte, short, Int, etc.)
3
public static void fill(int[] a, int val)
Assigns the specified int value to each element of the specified array of ints. The same method could be used by all other primitive data types (Byte, short, Int, etc.)
4
public static void sort(Object[] a)
Sorts the specified array of objects into an ascending order, according to the natural ordering of its elements. The same method could be used by all other primitive data types ( Byte, short, Int, etc.)
Linked list in data structures:
The singly linked list is a linear data structure in which each element of the list contains a pointer which points to the next element in the list. Each element in the singly linked list is called a node. Each node has two components: data and a pointer next which points to the next node in the list. The first node of the list is called as head, and the last node of the list is called a tail. The last node of the list contains a pointer to the null. Each node in the list can be accessed linearly by traversing through the list from head to tail.
Java Program to create and display a singly linked list
Consider the above example; node 1 is the head of the list and node 4 is the tail of the list. Each node is connected in such a way that node 1 is pointing to node 2 which in turn pointing to node 3. Node 3 is again pointing to node 4. Node 4 is pointing to null as it is the last node of the list.
Algorithm:
Create a class Node which has two attributes: data and next. Next is a pointer to the next node.
Create another class which has two attributes: head and tail.
addNode() will add a new node to the list:
Create a new node.
It first checks, whether the head is equal to null which means the list is empty.
If the list is empty, both head and tail will point to the newly added node.
If the list is not empty, the new node will be added to end of the list such that tail's next will point to the newly added node. This new node will become the new tail of the list.
a. display() will display the nodes present in the list:
Define a node current which initially points to the head of the list.
Traverse through the list till current points to null.
Display each node by making current to point to node next to it in each iteration.
Program:
public class SinglyLinkedList {
//Represent a node of the singly linked list
class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
//Represent the head and tail of the singly linked list
public Node head = null;
public Node tail = null;
//addNode() will add a new node to the list
public void addNode(int data) {
//Create a new node
Node newNode = new Node(data);
//Checks if the list is empty
if(head == null) {
//If list is empty, both head and tail will point to new node
head = newNode;
tail = newNode;
}
else {
//newNode will be added after tail such that tail's next will point to newNode
tail.next = newNode;
//newNode will become new tail of the list
tail = newNode;
}
}
//display() will display all the nodes present in the list
public void display() {
//Node current will point to head
Node current = head;
if(head == null) {
System.out.println("List is empty");
return;
}
System.out.println("Nodes of singly linked list: ");
while(current != null) {
//Prints each node by incrementing pointer
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
SinglyLinkedList sList = new SinglyLinkedList();
//Add nodes to the list
sList.addNode(1);
sList.addNode(2);
sList.addNode(3);
sList.addNode(4);
//Displays the nodes present in the list
sList.display();
}
}
OUTPUT: Nodes of singly linked list:
1 2 3 4
Stacks in data structures:
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
Mainly the following three basic operations are performed in the stack:
Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.
Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.
Peek or Top: Returns top element of stack.
isEmpty: Returns true if stack is empty, else false.
stack
How to understand a stack practically?
There are many real-life examples of a stack. Consider the simple example of plates stacked over one another in a canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO/FILO order.
Time Complexities of operations on stack:
push(), pop(), isEmpty() and peek() all take O(1) time. We do not run any loop in any of these operations.
Applications of stack:
Balancing of symbols
Infix to Postfix /Prefix conversion
Redo-undo features at many places like editors, photoshop.
Forward and backward feature in web browsers
Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.
Backtracking is one of the algorithm designing technique .Some example of back tracking are Knight-Tour problem,N-Queen problem,find your way through maze and game like chess or checkers in all this problems we dive into someway if that way is not efficient we come back to the previous state and go into some another path. To get back from current state we need to store the previous state for that purpose we need stack.
In Graph Algorithms like Topological Sorting and Strongly Connected Components
In Memory management any modern computer uses stack as the primary-management for a running purpose.Each program that is running in a computer system has its own memory allocations
String reversal is also a another application of stack.Here one by one each character get inserted into the stack.So the first character of string is on the bottom of the stack and the last element of string is on the top of stack. After Performing the pop operations on stack we get string in reverse order .
Implementation:
There are two ways to implement a stack:
Using array
Using linked list
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
Implementing Stack using Arrays
/* C++ program to implement basic stack
operations */
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
class Stack {
int top;
public:
int a[MAX]; // Maximum size of Stack
Stack() { top = -1; }
bool push(int x);
int pop();
int peek();
bool isEmpty();
};
bool Stack::push(int x)
{
if (top >= (MAX - 1)) {
cout << "Stack Overflow";
return false;
}
else {
a[++top] = x;
cout << x << " pushed into stack\n";
return true;
}
}
int Stack::pop()
{
if (top < 0) {
cout << "Stack Underflow";
return 0;
}
else {
int x = a[top--];
return x;
}
}
int Stack::peek()
{
if (top < 0) {
cout << "Stack is Empty";
return 0;
}
else {
int x = a[top];
return x;
}
}
bool Stack::isEmpty()
{
return (top < 0);
}
// Driver program to test above functions
int main()
{
class Stack s;
s.push(10);
s.push(20);
s.push(30);
cout << s.pop() << " Popped from stack\n";
//print all elements in stack :
cout<<"Elements present in stack : ";
while(!s.isEmpty())
{
// print top element in stack
cout<<s.peek()<<" ";
// remove top element in stack
s.pop();
}
return 0;
}
Output :
10 pushed into stack
20 pushed into stack
30 pushed into stack
30 Popped from stack
Top element is : 20
Elements present in stack : 20 10
0 Comments