单链表-数据结构逻辑

Question

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

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 作为后端。如果您想实现它的行为以了解它的工作原理，请不要使用为您做所有事情的class。

单链表-数据结构逻辑

Single linked list - data structure logic

java

data-structures

singly-linked-list