如何在Java中实现LinkedList的追加和删除方法?

Question

我正在提高我的数据结构技能。我正试图从头开始实现LinkedList。以下是我目前所做的:

class Node {
    Node next = null; //reference to null
    Object data;  //value of the node
    public Node(Object d) {
        data = d;    //constructor that assigns the node's value to the node
    }
    void append(Object d) {
        Node end = new Node(d); //create the new node
        Node n = this;  
        while (n.next != null) {  //keep moving the reference until we reach null which is the reference of the last node       
            n = n.next;    
        }
        n.next = end;   //Assign the null reference to the node end which is the node to be added
    }
    Node deleteNode(Node head, Object d){
        Node n = head;    //Call the pointer to the head n;
        if (n.data == d) {  //Check if the data of the current node is same as node to be deleted
            return head.next;   //Here I got lost, I don't know why we're returning head.next
        }
        while (n.next != null) {  //as long as we have reached the last node
            if (n.next.data == d) {
                n.next = n.next.next; //I don't get this
                return head; //Why are we returning head
            }
            n = n.next;
        }
        return head;
    }
}

问题是我不理解deleteNode方法。我在《破解密码》这本书中找到了它。有人能帮我澄清一下到底发生了什么吗?整个引用的东西把我搞糊涂了

Answer 1

deleteNode方法似乎返回链表。下面是它的作用:

1. 如果链表的第一个元素是我们要查找的项目(它的数据匹配d)，那么我们只返回从第二个元素(head.next)开始的列表。没有任何东西链接到第一个元素，所以第一个元素消失了。这正是我们想要的。
2. 查看所有节点。他们通过观察n.next来做到这一点。如果它的数据与d匹配，则应该删除该节点。因此，让列表跳过该元素:将n.next设置为n.next.next(即它之后的元素)，而不是与d匹配的元素。

通常这类方法倾向于返回被删除的元素。相反，这似乎返回列表本身，它由其头部表示。这就是为什么该方法一直返回head。