Data structures and algorithms in Java

In the previous post I discussed about data structures in Java. This post covers details on abstract data types in Java and the operations that can be performed on them.

Explanation:

Abstract data types or as it is known as ADT’s are the data types whose behavior is defined by a set of values and a set of operations. They define the operations to be performed on data and what is the expected behavior.

Abstract data types define the behavior that you can expect from the data type but how this behavior is implemented is hidden. It does not show how the algorithms are implemented or how the data is stored in the memory.

Abstract means to show only the essential information and hide the implementation details.

A common example of abstract data types are interfaces in Java. Interfaces contain only method declaration while the implementation is defined by the classes implementing the interface. Hence the implementation details are hidden.

List of Abstract Data Types:

• Stack ADT
• Queue ADT
• List ADT

Abstract data types in detail:

Stack ADT:

A stack stores similar data type elements in an ordered sequence. It can be imagined as a vertical array in which all the operations of the stack are performed at the top of the stack.

Stack ADT operations:

1. push(Object element): Pushes the element to the top of the stack.
2. pop(): Removes an element from the top of the stack.
3. peek(): Returns the topmost element from the stack but does not remove it.
4. isEmpty(): Returns true if the stack is empty, else returns false.
5. isFull(): Returns true if the stack is full, else returns false.
6. size(): Returns the number of elements present in the stack.

Queue ADT:

A queue stores elements of the same data type sequentially. Operations on the queue can be performed at both ends i.e front/head and rear end. Insertion operation is done at rear end and removal operation is done at front end.

Queue ADT operations:

1. add(Object element): Insert an element at the rear end of the queue.
2. remove(): Removes an element from the front of the queue.
3. peek(): Returns the front element of the queue if the queue is not empty, else returns null.
4. size(): Returns the number of elements present in the queue.
5. isEmpty(): Returns true if the queue is empty else returns false.
6. isFull(): Returns true if the queue is full else returns false.

List ADT:

List ADT stores the similar data type elements in a sequential order. List abstract data types are dynamic in nature i.e. there is no need to define their size during the declaration.

List ADT operations:

1. add(Object element): Appends the element to the end of the list.
2. add(int index, Object element): Inserts the element at specified index.
3. remove(int index): Removes the element at specified index.
4. remove(Object element): Removes the first occurrence of the specified element.
5. size(): Returns the number of elements present in the list.
6. get(int index): Returns the element at specified index.
7. isEmpty(): Returns true if the list is empty else returns false.

From the above abstract data types and the operations that can be performed on them, we can see that the operations do not define how they are implemented internally.

The Stack ADT can be implemented using an array or a linked list. The Queue ADT can be implemented using an array or a singly linked list or a doubly linked list. Hence an ADT can be implemented in many different ways but the behavior remains the same.

I hope this post helped you to understand the ADT concepts and please provide your feedback in below comments section.