A Complete Guide for Linear & Non-Linear Data Structures for Beginners

10 min readAug 20, 2022

Hello Friends, In this session will learn the most important concept Data Structures linear and non-linear.

Data Structure is nothing but a building blocks of a program. Also we can say that “Program = DataStructure + Algorithm”.

Data structures has been divided into two parts

Linear Data Structure
Non-Linear Data Structure

Linear Data Structures: In a linear data structure all the elements are arranged in the linear or sequential order. The linear data structure is a single level data structure.

Non-Linear Data Structures: The non-linear data structure does not arrange the data in a sequential manner as in linear data structures. Non-linear data structures are the multilevel data structure.

Types of Data Structure in Java

There are some common types of data structure in Java they are as follows –

Arrays
LinkedList
Stack
Queue
Graph
Set

1. Arrays

An Array is a collection of the elements of the same type stored in contiguous memory locations. It’s one of the simplest data structures, with each data element accessible at random using its index number. The first address of the array belongs to the first element and the last address to the last element of the array.

Important points about arrays:

Arrays can have data items of simple and similar types such as int or float, or even user-defined datatypes like structures and objects.
The common data type of array elements is known as the base type of the array.
Arrays are considered as objects in Java.
The indexing of the variable in an array starts from 0.
We must define an array before we can use it to store information.
The storage of arrays in Java is in the form of dynamic allocation in the heap area.
We can find the length of arrays using the member ‘length’.
The size of an array must be an int value.

Arrays can be of 3 types:

Single Dimensional Arrays
Two-dimensional Arrays
Multi-dimensional arrays

We can use an array only when we predetermine the number of elements along with its size since the memory is preserved before processing. For this reason, arrays come under the category of static data structures.

Time complexities for array operations:

Accessing elements: O(1)
Searching:
For Sequential Search: O(n)
For Binary Search [If Array is sorted]:O(log n)
Insertion: O(n)
Deletion: O(n)

Advantages of Arrays

Arrays use a single name to represent numerous data elements of the same type.
The elements in arrays can be accessed at random using the index number.
For all of its elements, arrays allocate memory in contiguous memory regions. As a result, there is no probability of extra memory being allocated. This prevents memory overflow and shortages in arrays.

Disadvantages of Arrays

The number of elements to be stored in an array should be known in advance.
Once the size of the array is declared, it cannot be modified. Memory allocated cannot be increased or decreased. Thus array is a static structure.
Allocating more memory than several elements leads to wastage of memory. Less memory allocation leads to a problem.
As the items are stored in consecutive memory regions and the shifting process is expensive, insertion and deletion are difficult in an array.

2. Linked Lists

The Linked Lists in Java is another important type of data structure. A Linked List is a collection of similar types of data elements, called nodes, which point to the next following nodes by means of pointers.

Here the elements are not stored in contiguous locations and each element is a separate object with a data part and address part.

Linked lists overcome the drawbacks of arrays because in linked lists there is no need to define the number of elements before using it, therefore the allocation or deallocation of memory can be during the processing according to the requirement, making the insertions and deletions much easier and simpler.

Types of Linked lists:

2.1 Singly-linked list

A singly-linked list is a linked list that stores data and the reference to the next node or a null value. Singly-linked lists are also known as one-way lists as they contain a node with a single pointer pointing to the next node in the sequence.

There is a START pointer that stores the very first address of the linked list. The next pointer of the last or end node stores NULL value, which points to the last node of the list which does not point to any other node.

2.2 Doubly-linked list

It is the same as a singly-linked list with the difference that it has two pointers, one pointing to the previous node and one pointing to the next node in the sequence. Therefore, a doubly-linked list allows us to traverse in both the directions of the list.

2.3 Circular Linked List

In the Circular Linked List, all the nodes align to form a circle. In this linked list, there is no NULL node at the end. We can define any node as the first node. Circular linked lists are useful in implementing a circular queue.

Time complexities for linked-list operations:

Traversing elements: O(n)
Searching an element: O(n)
Insertion: O(1)
Deletion: O(1)

We can also perform more operations like:

Concatenating two lists
Splitting list
Reversal of list

Advantages of Linked List

The linked list is a dynamic data structure. We can allocate and deallocate the memory at run-time itself.
The node can be easily inserted or deleted using the insertion and deletion function.
The linked list makes good use of memory. Because we don’t have to allocate memory ahead of time.
It has an extremely rapid access time and can be accessed at a specific time without any memory overhead.
Linear data structures like stack and the queue can be easily used linked list.

Disadvantages of Linked List

As each node of the linked list points to a pointer, it requires more memory to store the elements than an array.
Traversing the nodes of a linked list is quite tough. We won’t be able to access any node at random in this case.(As we do in the array by index.)
In a linked list, reverse traversing is harder since the pointer demands extra memory.

3. Stack

A stack is a LIFO (Last In First Out) data structure that can be physically implemented as an array or as a linked list. Insertion and deletion of elements in a stack occur at the top end only. An insertion in a stack is called pushing and deletion from a stack is called popping.

When we implement a stack as an array, it inherits all the properties of an array and if we implement it as a linked list, it acquires all the properties of a linked list.

Common operations on a stack are:

Push(): Adds an item to the top of the stack.
Pop(): Removes the item from the top of the stack
Peek(): It tells us what is on the top of the stack without removing it. Sometimes, we can also call it top().

Stacks are useful in:

Parenthesis matching
Solving the maze problem
Nested Function calls

Advantages of Stack

Stack manages the data in a LIFO method, which is not possible with a linked list and array.
Local variables are stored in a stack when a function is called, and automatically get destroyed once returned.
You can use Stack to manage how memory is allocated and deallocated.
Stack is more secure and reliable since it does not easily get corrupted.
Stack does not allow resizing of variables.

Disadvantages of Stack

Stack overflow can occur if you create too many objects on the stack.
When variable storage is overwritten, the function or programme can sometimes behave in an unpredictable manner.
Stack memory is limited.
Data cannot be randomly accessed in a stack.

4. Queue

Logically, a queue is a FIFO (First In First Out) data structure and we can physically implement it either as an array or a linked list. Whatever way we use to implement a queue, insertions always take place at the “rear” end and deletions always from the “front” end of the queue.

Common operations on a queue are:

Enqueue(): Adding elements at the rear end of the queue.
Dequeue(): Deleting elements from the front end of the queue.

Variations in Queue:

Depending on the requirements of the program, we can use the queues in several forms and ways. Two popular variations of queues are Circular queues and Dequeues (Double-ended queues).

4.1 Circular Queues

Circular Queues are the queues implemented in circle form rather than a straight manner. Circular queues overcome the problem of unutilized space in the linear queues that we implement as arrays.

4.2 Dequeues

A double-ended queue or a dequeue is a refined queue in which can add or remove the elements at either end but not in the middle.

Applications of a Queue:

Queues are useful in telephone inquiries, reservation requests, traffic flow, etc. While using telephone directory service, you might have sometimes heard “Please wait, You are in A QUEUE”.
To access some resources like printers queues, disk queues, etc.
For breadth-first searching in special data structures like graphs and trees.
For handling scheduling of processes in a multitasking operating system example FCFS (First Come First Serve) scheduling, Round-Robin scheduling, etc.

Advantages of Queue

Queues have the benefit of being able to handle a variety of data types while also being flexible and quick. In addition, queues have the potential to be infinitely long, as opposed to fixed-length arrays.

Disadvantage of Queue

A major disadvantage of a classical queue is that a new element can only be inserted when all of the elements are deleted from the queue.

5. Graph

A graph is a non-linear data structure in Java and the following two components define it:

A set of a finite number of vertices which we call as nodes.
An edge with a finite set of ordered pairs which is in the form (u, v).
V represents the Number of Vertices.
N represents the Number of Edges.

Classification of a Graph

Graph Data Structures in Java can be classified on the basis of two parameters: direction and weight.

5.1 Direction

On the basis of direction, the graph can be classified as a directed graph and an undirected graph.

A. Directed graph

A directed graph is a set of nodes or vertices connect together with each other and all the edges have a direction from one vertex to another. There is a directed edge for each connection of vertices. The figure below shows a directed graph:

B. Undirected graph

An undirected graph is a set of nodes or vertices which are connected together, with no direction. The figure below shows an undirected graph:

5.2 Weight

On the basis of weight, the graph can be classified as a weighted graph and an unweighted graph.

A. Weighted graph

A weighted graph is a graph in which the weight is present at every edge of the graph. A weighted graph is also a special type of labeled graph. The figure below shows a weighted graph:

B. Unweighted graph

An unweighted graph is the one in which there is no weight present on any edge. The figure below shows an unweighted graph:

Advantage of Graph

The fundamental benefit of a graph data structure is that it allows you to use all graph-related computer science algorithms. You can use all of the power of graph algorithms to solve your problem once you’ve worked out how to represent your domain logic as a graph.

Disadvantage of Graph

The main disadvantage is its large memory complexity.

6. Set

A Set is a special data structure in which we can not use the duplicate values. It is a very useful data structure mainly when we want to store unique elements, for example, unique IDs.

Advantages of Map

If all you care about is lookup look you know your keys (what you’re using to look up your data) fall into a fairly small integer range, an array (or, better yet, a vector) is great. With minimal fuss, you can look something up using a key in real-time.
map stores items in key order. So you can iterate over all the items in a map, from beginning to end, in sorted key order. You obviously can do this with an array/vector, how, ever as was said earlier, a map lets you have any arbitrary key type with any arbitrary ordering defined.
To insert into the middle of an array/vector, all of the objects must be shifted to the left. If you have a dynamic array and a vector, you must enlarge the vector, which will cause the entire array to be copied to fresh memory.

Disadvantages of Map

While hash-tables have constant time insertion, they will need to evolve their internal structure and re-bucket their entries periodically. This is an operation with a cost proportionate to the hash-current table’s size. As a result, insertion time does not always follow a consistent pattern.
Hash-tables, in general, do not preserve ordering, whether natural or insertion order.