图使用邻接表的实现是否正确？

Question

我是DSA的初学者，最近几天我一直在尝试使用邻接列表找到图形的正确实现。

下面我给出了我认为邻接列表是如何实现的整个代码。

我从头开始创建了一个SiinglyLinkedlist。并且我正在使用一个Hashmap来改进时间复杂性。

Hashmap中的整数键充当顶点&在其值中包含一个Linkedlist。

在顶点中，我存储了整数ID，在Linkedlist中，我存储了该ID的所有好友名。

图中有3种方法-

1]insertVertice（int ID）-这将在hashmap中的给定ID处创建一个空linkedlist。

2]insertDataAtID（int ID,String data）-这将以给定的ID在linkedlist中插入数据。

3]printAllDataAtID（int ID）-这将打印链接列表中以给定ID/键显示的所有好友名称或数据。

你能检查一下实施过程并给出任何错误的建议吗？或者更好的一些建议如何更有效地实现邻接列表？

谢谢你的努力。

import java.util.HashMap;

public class demo {

    static HashMap 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 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 NullPointerExcepthtml" target="_blank">ion {
         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;
    }
}

Answer 1

如果要维护tail节点，则不需要遍历要插入的列表。

void insertNode(String data) {
    Node newNode = new Node();
    newNode.data = data;
    if (head == null) {
        head = tail = newNode;
        newNode.next = null;
    } else {
        tail.next = newNode;
        newNode.next = null;
        tail = tail.next;
    }
}