时间戳

首页 > 解决方案 > 了解链表中的插入

java - 了解链表中的插入

问题描述

我无法理解如何在链接列表中插入。我在网上找到了一些示例，但我似乎无法 100% 理解它。在这段代码中，我对我认为代码中发生的事情发表了评论，以及我正在努力的事情。一些帮助将不胜感激。谢谢！

    private static final class Node {
        final Person person;
        Node next;

        Node(Person person) {
            this.person = person;
        }
    }

   public boolean insert(Person person) {
        Node n = new Node(person);
        //insert as the first element
        if (head == null) {
            head = n;
            size++;
            return true;
        }

        Node current = head;
        Node prev = null;
        int comparison;

        while (current != null) {
            //until the list is empty compare 
            comparison = person.name.compareTo(current.person.name);
            //that person already exists
            if (comparison == 0) {
                return false;
            } else if (comparison > 0) { 
                //if the next spot in the list is empty place the person there
                if (current.next == null) { 
                    current.next = n;
                    break;
                }
            } else { 
            //this is the part I dont understand
                if (prev == null) { 
                    Node oldHead = head;
                    head = n;
                    head.next = oldHead;
                    break;
                }
                //dont understand this either
                prev.next = n;
                n.next = current;
                break;
            }
            //keep moving through the list
            prev = current;
            current = current.next;
        }
        size++;
        return true;
    }

标签： javamethodslinked-list

解决方案

根据您在代码中所做的所有比较，这似乎是一个排序的链表，而不是一个普通的链表。

这段代码是说，如果插入的值小于头，我们希望这个新值是头，原始头是列表中的第二个值。因此 oldHead 是 head 的一个引用变量，只是为了临时保存该值。之后，head = n 只是将头（也就是列表中的第一个节点）设置为新节点，所以现在第一个节点就是被插入的节点。然后 head.next = oldHead 将列表中的下一个值设置为等于列表的原始头部。现在插入的值是列表中的第一个值，原始头部是列表中的第二个值。

if (prev == null) { 
        Node oldHead = head;
        head = n;
        head.next = oldHead;
        break;
}

这段代码只是设置链接，因此所有变量都链接在一起。

//dont understand this either
prev.next = n;
n.next = current;
break;

推荐阅读