Exploring Linear Data Structures
A Comprehensive Overview in Java
Linear data structures are fundamental concepts in computer science that organize and store data in a linear or sequential manner, to use it in the most effective way. The main reason to classify them is that we need less time complexity and space.
Here are some common linear data structures in Java:
1. Arrays
An array is a collection of items of same data type stored at contiguous memory locations.
Types of Arrays
One-Dimensional Array: Simplest form of an array, which consists of a single row of same data type elements. Elements in a 1D array are accessed using a single index.
public class Main {
public static void main(String[] args) {
// Declare an array of integers with a size of 5
int[] arr= new int[5];
// Initialize the array with values
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 4;
arr[4] = 5;
// Access and display array elements
System.out.print("Array Elements: ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
// Displaying using a for-each loop
for (int element : arr) {
System.out.println(element);
}Two-Dimensional Array (matrix): A two-dimensional array is an array of arrays. It's organized into rows and columns, forming a grid-like structure. Elements in a 2D array are accessed using two indices, one for the row and one for the column.
public class TwoDimensionalArrayExample {
public static void main(String[] args) {
// Declare and initialize a 2D array of integers (3x3)
int[][] arr = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// Access and display array elements
System.out.println("Array Elements:");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println(); // Move to the next row
}
}
}Multi-Dimensional Array: Arrays can have more than two dimensions, leading to multi-dimensional arrays. They are used to represent structured data in multiple dimensions, allowing for more complex and organized data structures.
Types of Array operations
Accessing Elements: Accessing a specific element in an array by its index is a constant-time operation; possible because it stores elements at contiguous elements. It has a time complexity of O(1).
Insertion: Inserting an element to the end of an array is a constant-time operation, O(1) but insertion at the beginning or any specific index takes O(n) time because it requires shifting all of the elements.
Deletion: Same as insertion, deleting the last element is a constant-time operation, O(1) but deletion of element at the beginning or any specific index takes O(n) time because it requires shifting all of the elements, leading to a linear-time operation.
Searching: Linear Search takes O(n) time which is useful for unsorted data and Binary Search takes O(logn) time which is useful for sorted data.
2. Linked Lists
A linked list is a sequence of elements called nodes, where each node contains data and a reference (or link) to the next node in the same sequence. Linked lists are dynamic data structures that can efficiently grow or shrink in size.
Types of Linked List
Single Linked List — every node stores the address or reference of the next node in the list and the last node has the next address or reference as NULL.
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class SinglyLinkedList {
Node head;
public SinglyLinkedList() {
this.head = null;
}
// Insert a node at the beginning of the list
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
// Insert a node at the end of the list
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
// Delete a node with a given value
public void delete(int data) {
if (head == null) {
return;
}
if (head.data == data) {
head = head.next;
return;
}
Node current = head;
while (current.next != null && current.next.data != data) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next;
}
}
// Display the elements of the list
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
}
public class Main {
public static void main(String[] args) {
SinglyLinkedList list = new SinglyLinkedList();
list.insertAtBeginning(3);
list.insertAtBeginning(2);
list.insertAtBeginning(1);
list.insertAtEnd(4);
list.insertAtEnd(5);
list.display(); // Output: 1 -> 2 -> 3 -> 4 -> 5 -> null
list.delete(3);
list.display(); // Output: 1 -> 2 -> 4 -> 5 -> null
}
}Doubly Linked List — Each node has two pointers; one pointing to the next node and the other one pointing to the previous node. This bidirectional structure allows for efficient traversal in both directions.
class Node {
int data;
Node next;
Node prev;
public Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
private Node head;
private Node tail;
public DoublyLinkedList() {
this.head = null;
this.tail = null;
}
// Insert a node at the beginning of the list
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
}
// Insert a node at the end of the list
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
} else {
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
}
}
// Delete a node with a given value
public void delete(int data) {
Node current = head;
while (current != null) {
if (current.data == data) {
if (current == head) {
head = current.next;
if (head != null) {
head.prev = null;
} else {
tail = null;
}
} else if (current == tail) {
tail = current.prev;
tail.next = null;
} else {
current.prev.next = current.next;
current.next.prev = current.prev;
}
return;
}
current = current.next;
}
}
// Display the elements of the list forwards
public void displayForward() {
Node current = head;
while (current != null) {
System.out.print(current.data + " <-> ");
current = current.next;
}
System.out.println("null");
}
// Display the elements of the list backwards
public void displayBackward() {
Node current = tail;
while (current != null) {
System.out.print(current.data + " <-> ");
current = current.prev;
}
System.out.println("null");
}
}
public class Main {
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.insertAtBeginning(3);
list.insertAtBeginning(2);
list.insertAtBeginning(1);
list.insertAtEnd(4);
list.insertAtEnd(5);
list.displayForward(); // Output: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> null
list.displayBackward(); // Output: 5 <-> 4 <-> 3 <-> 2 <-> 1 <-> null
list.delete(3);
list.displayForward(); // Output: 1 <-> 2 <-> 4 <-> 5 <-> null
}
}Circular Linked Lists: First and the last nodes are also connected to each other to form a circle, there is no NULL at the end.
Types of Linked List Operations
Accessing Elements: Accessing a specific element in a linked list takes O(n) time since nodes are stored in non contiguous locations.
Searching: Searching of a node in linked list takes O(n) time as whole list needs to traversed.
Insertion: O(1) time.
Deletion: O(1) time.
3. Stacks
A stack follows the Last-In-First-Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed and vice-versa.
Stack Operations
push(): An element is inserted into the stack.
pop(): An element is removed from the top of the stack and is returned.
peek(): Returns the last inserted element that is at the top without removing it.
display(): Displays all the elements stored in the stack in the reverse order (FILO).
class StackC{
int size;
int top;
int[]stack;
public Stack(int size){
this.size = size;
top = -1; //Initially, the stack is empty.
stack = new int[size];
}
// Insertion of elements in the Stack
public void push(int value){
if (top == size-1){
System.out.println("Stack full");
}
else{
top++;
stack[top] = value;
System.out.println(stack[top]);
}
}
//Deletion of elements in the Stack
public int pop(){
if (top == -1){
System.out.println("Stack is empty");
}
return stack[top];
top--;
}
// Returns the top vlaue without removing it from the Stack
public int peek(){
if (top == -1){
System.out.println("Empty Stack");
}
else{
return stack[top];
}
//Displays all the elements stored in the Stack
public void display(){
for (int i = top; i>-1; i--){
System.out.print(stack[i] + " ");
}
}
}
public class Main{
public static void main{
StackC stack = new StackC(4);
stack.push(23);
stack.push(33);
stack.push(43);
stack.push(53);
stack.display();
stack.pop();
stack.pop();
stack.display();
}
}4. Queues
A queue follows the First-In-First-Out (FIFO) principle, meaning the first element added is the first one to get removed and vice-versa.
Queue Operations
enqueue(): Adds an element to the end of the queue.
dequeue(): Removes element from the start of the queue.
peek(): Acquires the data element available at the front node of the queue without deleting it.
display(): Displays all the elements stored in the queue (FIFO).
lass Queue {
int size = 4;
int[]queue = new int[size];
int front;
int rear;
public Queue(){
//Initially, the queue is assumed to be empty
front = -1;
rear = -1;
}
//Adding elements at the back(rear) of the queue
void enQueue(int element){
if (front == 0 && rear == size -1){
System.out.println("Queue is full");
}
else{
if(front==-1)
front = 0;
rear++;
queue[rear] = element;
System.out.println("Element " + element + " is added ");
}
}
//Deleting elements at the start(front) of the queue
int deQueue(){
int element;
if(front == -1){
System.out.println("Empty Queue");
return -1;
}
else{
element = queue[front];
}
if(front>=rear){
front = -1;
rear = -1;
}
else{
front++;
}
System.out.println(element + " is deleted");
return (element);
}
//Displays all the elements stored in the queue
void display(){
for(int i = front; i<=rear; i++){
System.out.print(queue[i] + " ");
}
}
}
public class Main{
public static void main(String[]args){
Queue q = new Queue();
q.enQueue(34);
q.enQueue(25);
q.enQueue(45);
q.enQueue(68);
q.enQueue(22);
q.display();
System.out.println();
q.deQueue();
q.deQueue();
q.display();
}
}These linear data structures play a vital role in various aspects of software development, algorithm design and are used to solve a variety of computational problems. The choice of a particular data structure depends on the requirements of the specific problem in hand, including considerations like time complexity, space complexity, and the nature of operations to be performed on the data.
