Java: Linear Data Structures

What are the Data Structures -

Data structure is a an organization system of data (same data type) collection. It is a system to store the data (like arrays) in the memory on the computer and the method to access and manipulate the data efficiently. There are two types of data structures -

Linear Data Structures -

In Linear data structures, data is stored sequentially and linked to previous and next elements (data). They are linked on the single level and connected in such a way that they are traversed sequentially. The data elements can be traverse in the single run using the iterations (loops). The examples of Linear Data Structures are - Arrays, Queue, Stack and LinkedList. Classes and interfaces - Arrays, Stack, Queue and LinkedList, can be accessed through java.util package. We already discussed briefly about data structures Arrays and Stack in our earlier posts - Arrays and How to create a class stack.

Stack -

• Stack is a collection of same data type elements / class objects.
• New data element is pushed (added) on top of the stack, and only the data element on the top is popped out (retrieved).
• Always the data element last pushed in the stack, will be popped out - LIFO (Last In First Out).
• Stack data elements are stored in contiguous memory locations.
• Push - pushes (appends) the new data element on top of the stack and points to the last element of the stack.
• Pop - pops (gets) the top element from the stack, uses it and the second last data element comes on top (points to the second last data element). The last retrieved element has no connection with the stack.
• Empty stack - When the last data element in the stack is popped up, stack is empty - there are no data elements left in the stack.
• Full stack - When the stack has the data elements equals to the stack size, no other element can be pushed in, the stack is full.
• Java has its own generic (For all data types) class as Stack and it has methods - push(), pop(), peek(), empty(), search()
• Example of how stack works - I have created a custom class Stack of integers in the post - How to create a class Stack.

Queue -

• Queue is a collection of same data type elements / class objects.
• New data element is put (added) in start of the queue, but only the data element in the end is got out (retrieved).
• Always the data element first put in the queue, will be retrieved - FIFO (First In First Out).
• Queue data elements are stored in contiguous memory locations.
• Put - puts (appends) the new data element on start of the queue and points to the first element of the queue.
• Get - gets (retrieves) the first element from the queue, uses it and the second data element becomes the first data element (points to the second data element). The last retrieved element has no connection with the queue.
• Empty queue - When the last data element in the queue is got out, queue is empty - there are no data elements left in the queue.
• Full queue - When the queue has the data elements equals to the queue size, no other element can be put in, the queue is full.
• Java has its own generic (For all data types) interface as Queue and to implement this interface, the programmer has to override the methods - add(), offer(), remove(), poll(), element() and peek().

Linked List -

• Linked List is a collection of same data type elements / class objects.
• New data element can be added at start, end or middle of the Linked List.
• LinkedList data elements are not stored in contiguous memory locations. Each data element is like a container which has two parts - data and address to the next data element. The last data element has address as null. 
• Any data element can be accessed randomly by using index no, and can be referred any time till it is not removed explicitly.
• Java has its own generic (For all data types) class as LinkedList and it has several methods to add, remove or manipulate data elements in the list - getFirst(), getLast(), removeFirst(), removeLast(), addFirst(), addLast(), contains(), size(), add(), remove(), addAll(), clear(), get(), set(), indexOf(), listIterator() and toArray() etc.

Non-Linear Data Structures -

In Non-Linear Data Structures, data is stored in multi-level hierarchy, and are complex to implement. The data elements can not be accessed sequentially and can't be traversed in the single run by using the iterations (loops). The examples of Non-Linear Data Structures are - Trees and Graphs.

Note: I will cover Non-Linear Data Structures in a separate post.