Reversing a LinkedList using Stack in Java

Hello people, this is another blog dedicated to reversing a LinkedList using a Stack. Although it can be done in several ways like recursion, iteration, using constant auxiliary space, etc, 'Stack' is a very easy and efficient method to do the same.

This has been demonstrated in the code.

import java.util.*;

class TestClass {

static class Node {

int data;

Node next;

public Node(int data) {

this.data = data;

this.next = null;

}

}

static Node head;

public static void main(String[] args) {

Stack<Integer> stack = new Stack<Integer>();

for(int i = 0; i < 10; i++) {

Node temp = new Node(i);

if(head == null) {

head = temp;

} else {

Node p = head;

while(p.next != null) {

p = p.next;

}

p.next = temp;

}

}

System.out.print("Printing the LinkedList: ");

Node x = head;

while(x != null) {

System.out.print(x.data + " ");

x = x.next;

}

System.out.println();

try {

Node p = head;

while(p != null) {

stack.push(p.data);

p = p.next;

}

System.out.print("Reversing the LinkedList using stack: ");

while(!stack.isEmpty()) {

System.out.print(stack.pop() + " ");

}

System.out.println();

} catch (EmptyStackException exception) {

System.out.println("The stack is Empty!");

}

}

}

People, please let me know if this could be improvised and let me know the concerns if any!

Finding the middle Node of the Linked List using fast and slow method

Fast and slow pointers are very useful in LinkedList especially when traversal of the LinkedList is required several times.

Here is an implementation of fast and slow method for finding the middle of the LinkedList without traversing the whole array.

class Node {

int data;

Node next;

public Node(int data) {

this.data = data;

this.next = null;

}

}

class LinkedList {

static Node head;

public static Node printMiddle(Node head) {

Node fast_ptr = head;

Node slw_ptr = head;

if(head != null) {

while(fast_ptr != null && fast_ptr.next != null) {

fast_ptr = fast_ptr.next.next;

slw_ptr = slw_ptr.next;

}

System.out.println("The middle element is: " + slw_ptr.data);

}

return slw_ptr;

}

public static void main(String[] args) {

head = new Node(1);

head.next = new Node(2);

head.next.next = new Node(3);

head.next.next.next = new Node(4);

head.next.next.next.next = new Node(5);

head.next.next.next.next.next = new Node(6);

head.next.next.next.next.next.next = new Node(7);

head.next.next.next.next.next.next.next = new Node(8);

head.next.next.next.next.next.next.next.next = new Node(9);

printMiddle(head);

}

} 

Please feel free to comment over for any suggestions / doubts.

Breadth First Search of a graph using Adjacency List

Breadth First Search of a graph using Adjacency List.



This post is an implementation of a breadth first search of a Graph using Adjacency List in Java. In this, we go level by level and add all the elements onto the queue and maintain a array of boolean values to mark them as visited. The boolean array is required just to make sure we do not get into a circular graph.

As said, the algorithms uses the FIFO, thus queue is required as a data structure in this implementation.

More details on it coming soon...

import java.util.Iterator;

import java.util.LinkedList;

import java.util.Scanner;

@SuppressWarnings("unchecked")

class BreadthFirstSearch {

private int v;

private LinkedList<Integer> adj[];

public BreadthFirstSearch(int v) {

this.v = v;

adj = new LinkedList[v];

for (int i = 0; i < v; ++i) {

adj[i] = new LinkedList();

}

}

void addEdge(int v, int w) {

adj[v].add(w);

}

void breadthFirstSearch(int s) {

boolean[] visited = new boolean[v];

LinkedList<Integer> queue = new LinkedList<Integer>();

// Adding the first element to the queue

visited[s] = true;

queue.add(s);

// Adding its adjacent elements to the queue

while (queue.size() != 0) {

s = queue.poll();

System.out.print(s + " ");

Iterator<Integer> iterator = adj[s].listIterator();

while (iterator.hasNext()) {

int next = (int)iterator.next();

if(!visited[next]) {

visited[next] = true;

queue.add(next);

}

}

}

}

public static void main(String[] args) {

BreadthFirstSearch bfs = new BreadthFirstSearch(4);

bfs.addEdge(0, 1);

bfs.addEdge(0, 2);

bfs.addEdge(1, 2);

bfs.addEdge(2, 0);

bfs.addEdge(2, 3);

bfs.addEdge(3, 3);

System.out.print("BreadthFirstSearch starting at vertex 1: ");

bfs.breadthFirstSearch(1);

System.out.println();

}

}

Please leave your comments for any suggestion or query.