java - 链表算法

Question

这里是LinkedList算法的一个实现。算法在 beginner 处、给定节点之后或列表末尾插入节点。

package LinkedList;

class LinkedList {
    Node Head;

    class Node {
        int data;
        Node Next;

        public Node(int d) {
            data = d;
            Next = null;
        }
    }

    public void insert(int value) {
        if (Head ==null) {
            Head = new Node(value);
            return;
        }
        Node new_node = new Node(value);
        new_node.Next = Head;
        Head = new_node;
    }

    public void display() {
        Node a = Head; 
        while (a != null) {
            System.out.println("value:" + a.data);
            a = a.Next;
        }
    }

    public void insertMiddle(int valueToInsert, Node prev_node) {
        if (Head == null) {
            System.out.println("Cant put value after last node");
        }
        Node new_node = new Node(valueToInsert);
        new_node.Next = prev_node.Next;
        prev_node.Next = new_node;
    }

    public void last(int value){
            Node new_node = new Node(value);
        if(Head == null){
            Head = new Node(value);
            return;
        }
        new_node.Next = null;

        Node last = Head;
        while(last != null){
            last = last.Next ;
        }
        last = new_node;
            return;
    }
}

public class LinkedList_Insertion {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        LinkedList list = new LinkedList();
        list.insert(8);
        list.insert(20);
        list.insert(0);
        list.insertMiddle(999, list.Head.Next);
        list.display();
        System.out.println("--------------");
        list.last(10000);
        list.display();
    }
}

在上面的代码中，在使用方法插入时:

public void insert(int value) {
    if(Head ==null){
        Head = new Node(value);
        return;
    }
    Node new_node = new Node(value);
    new_node.Next = Head;
    Head = new_node;
}

为什么我们不使用 Head.next = new_node;

同样，对于方法:

public void last(int value){
    Node new_node = new Node(value);
    if(Head == null){
        Head = new Node(value);
        return;
    }
    new_node.Next = null;

    Node last = Head;
    while(last != null){
        last = last.Next ;
    }
    last = new_node;
    return;
}

我们为什么不使用 last.next = new_node;？

我经常一次又一次地犯同样的错误。如果有人能澄清这个概念，我将不胜感激。
期待你的回复!

Answer 1

头部情况:

你可以有 Head->node1->node2->node3->...->lastNode

如果您执行 Head.next = newNode，则 node1->node2->node3->...->lastNode 将丢失。

如果你有一个双向链表，你可以做 Head.prev = newNode; Head = Head.prev(prev表示上一个)

最后一个案例:

这段代码:

public void last(int value){
    Node new_node = new Node(value);
    if(Head == null){
        Head = new Node(value);
        return;
    }
    new_node.Next = null;

    Node last = Head;
    while(last != null){
        last = last.Next ;
    }
    last = new_node;
    return;
}

看起来很奇怪，条件实际上应该是 while (last.next != null)，但即使那样你也没有插入，你首先获得对列表中最后一个元素的引用，然后您将该引用指向另一个对象，它实际上应该是 last.next = newNode，您是对的。

实现链表是理解 java 引用如何工作的好方法，继续练习并尝试实现双向链表。