java - 单链表——数据结构逻辑

Question

我最近开始专注于使用数据结构及其用例的编码练习。下面是我的程序，将数据插入到单个链表中，其中每个节点存储下一个节点的对象。这个程序运行良好。我想了解下面的代码有多有效，所遵循的逻辑是否有效且高效。当节点使用自定义行为实现时，链表的实际用例是什么？如何求以下程序的时间复杂度。任何指点都非常感谢。提前致谢。

public class ExplainSingleLinkedList {

    private LinkedList<Node> integerLinkedList = new LinkedList<>();
    private TreeMap<String,String> userIdList = null;
    Node head = null;

    public static void main(String[] args) {

        ExplainSingleLinkedList mainClass = new ExplainSingleLinkedList();
        mainClass.process();
    }

    private void process() {
        prepareInput();

        Iterator<Node> integerIterator = integerLinkedList.iterator();
        while(integerIterator.hasNext()){
            Node outputNode = integerIterator.next();
            System.out.println(outputNode.userId +" , " +outputNode.password +", "+ (outputNode.nextNode!=null ? outputNode.nextNode.userId:null));
        }
    }

    public void insert(String userId,String password){
        Node newNode = new Node(userId,password);
        if( head == null){
            head = newNode;
            integerLinkedList.add(head);
        }
        else{
            Node lastNode = integerLinkedList.getLast();
            if(lastNode.nextNode == null){
                if(head.nextNode ==null){
                    head.nextNode = newNode;
                }
                else{
                    lastNode.nextNode = newNode;
                }
            }

            newNode.nextNode = null;
            integerLinkedList.add(newNode);
        }

    }

    class Node
    {
        private String userId;
        private String password;
        Node nextNode;

        public Node(String firstName, String lastName){
            this.userId = firstName;
            this.password = lastName;
        }
    }

    private void prepareInput() {
        userIdList = new TreeMap<>();
        userIdList.put("a@in.com","a:123");
        userIdList.put("b@in.com","b:123");
        userIdList.put("c@in.com","c:123");
        for (Map.Entry entry : userIdList.entrySet()) {
            insert(entry.getKey().toString(),entry.getValue().toString());
        }
    }
}

输出如下，它按预期工作

a@in.com , a:123, b@in.com
b@in.com , b:123, c@in.com
c@in.com , c:123, null

Answer 1

你做错了。

通常，您总是在链表的顶部(头节点)插入，而不是在末尾。否则，每次添加元素都需要遍历整个列表。

或者，如果您想在末尾存储新元素，更好的方法是同时存储头部和尾部，并在追加时更新尾部。

此外，这里还不清楚您是否实现了任何内容，因为您使用 Java LinkdList 作为后端。如果您想实现其行为以了解其工作原理，请不要使用为您完成所有工作的类。