I am a beginner with DSA , Since last couple days I was trying to find the correct implementation for the Graph using adjacency list.
Below I have given the entire code for the way I thought adjacency list is to be implemented.
I have created a SiinglyLinkedlist all from scratch.
And I am using a Hashmap to improve the Time complexity.
The Integer key in the Hashmap acts as the VERTICE & consists of a Linkedlist in its VALUE.
In the vertices I am storing the Integer ID and in the Linkedlist I am storing all the Friend names for that particular ID.
The Graph has 3 methods -
1] insertVertice(int ID ) - this creates a empty linkedlist at given ID in hashmap .
2] insertDataAtID (int ID , String data) - this insert the Data in the linkedlist at the given ID.
3] printAllDataAtID(int ID) - this prints all the friend names or Data present in a linkedlist at a given ID / key in the Hashmap.
Can you please go through the Implementation and advice any mistakes ?
Or better some suggestions on how a Adjacency list can be implemented more effectively ?
Thank you for this effort.
-----------------------------------------------------------
import java.util.HashMap;
public class demo {
static HashMap<Integer,SinglyLinkedlist> graph = new HashMap<>();
public static void main(String[] args){
Graph graph = new Graph();
graph.insertVertice(101);
graph.insertDataAtID(101,"Deepesh");
graph.insertDataAtID(101,"Kiran");
graph.insertDataAtID(101,"Aryan");
graph.insertVertice(201);
graph.insertDataAtID(201,"Carl");
graph.insertDataAtID(201,"Arun");
graph.insertDataAtID(201,"Kishan");
graph.insertDataAtID(201,"Betth");
graph.printAllDataAtID(101);
graph.printAllDataAtID(201);
}
}
--------------------------------------------------------------
import java.util.HashMap;
public class Graph{
HashMap<Integer,SinglyLinkedlist> maplist = new HashMap<>();
void insertVertice(Integer id ){
maplist.put(id,new SinglyLinkedlist());
}
void insertDataAtID(Integer id, String data){
if (maplist.get(id)==null){
System.out.println("No such Vertice exist with id : " + id);
System.out.println("Create the Vertice first by calling insertVertice() method.");
}
SinglyLinkedlist linkedlist = maplist.get(id);
linkedlist.insertNode(data);
}
void printAllDataAtID(Integer id) throws NullPointerException {
if (maplist.get(id) == null) {
System.out.println("No such Vertice exist with id : " + id);
System.out.println("Create the Vertice first by calling insertVertice() method.");
} else {
SinglyLinkedlist linkedlist = maplist.get(id);
linkedlist.printAll();
}
}
}
------------------------------------------------------------
public class SinglyLinkedlist {
Node head;
Node tail;
public static class Node {
Node next;
String data;
}
void insertNode(String data) {
Node newNode = new Node();
newNode.data = data;
if (head == null) {
head = tail = newNode;
newNode.next = null;
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
newNode.next = null;
tail = newNode;
}
}
void removeLastNode() {
Node temp = head;
while (temp.next.next != null) {
temp = temp.next;
}
Node removedNode = temp.next;
tail = temp;
tail.next = null;
System.out.println("Removed value : " + removedNode.data);
}
void printAll() {
if (head == null) {
System.out.println("List is Empty !");
} else {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}
}
boolean search(String data) {
if (head == null) {
System.out.println("List is Empty !");
} else {
Node temp = head;
while (temp != null) {
if (temp.data.equals(data)) {
System.out.println("Value found !");
return true;
}
temp = temp.next;
}
System.out.println("Value not found !");
}
return false;
}
}
What I have tried:
I tried google and other online resources