java - 链接列表 - 单个对象如何依次存储如此多的地址？

Question

我学习了数据结构和链表，但我不明白一些东西。一个对象怎么能存储这么多地址和数据。当我了解对象时，我发现如果要为单个变量存储许多数据，则需要创建新对象，但现在在链接列表中，newNode对象将存储data1，next1，data2，next2，.... datan，nextn。

当程序运行list.insert(11)时，数据变为11，为什么旧​​数据5没有被删除？

抱歉我的英语语法，任何反馈都将不胜感激。谢谢!

以下代码是关于在链表中插入节点的代码:

节点类:

public class Node {

    int data;
    Node next;

    public int getData() {

        return data;
    }

    public Node getNext() {

        return next;
    }

    public void setData(int data) {

        this.data = data;
    }

    public void setNext(Node next) {

        this.next = next;
    }

}

MyLinkedList 类:

public class MyLinkedList {

    Node head;

    public void insert(int data) {

        Node newNode = new Node();
        newNode.setData(data); 
        newNode.setNext(null);

        if (head == null) {

            head = newNode;
        }
        else {

            Node n = head;
            while(n.getNext() != null) {

                n = n.getNext();
            }

            n.setNext(newNode);
        }
    }

    public void show() {

        Node newNode = head;
        while (newNode.getNext() != null) {

            System.out.println(newNode.getData());
            newNode = newNode.getNext();
        }

        System.out.println(newNode.getData());
    }

}

运行者类别:

public class Runner {

    public static void main(String args[]) {

        MyLinkedList list = new MyLinkedList();

        list.insert(5);
        list.insert(11);
        list.insert(9);
        list.insert(3);
        list.show();
    }

}

Answer 1

链表本身几乎对其所包含的数据一无所知。它通常只保存总大小的变量和对第一个节点的引用，即头(以及双向链表中的尾部)。

节点是一个自己的对象，它包含一个数据变量和对下一个节点的引用，后者也是一个自己的对象，依此类推。 (双向链表中的节点也有指向前一个节点的指针)

因此，为了访问第五个节点，您需要从头部开始，并跟随下一个指针到达第五个节点。链表中没有直接访问。但是，它允许通过重新排列节点的下一个指针(例如跳过节点)来轻松插入或删除元素。

另请注意，一个对象可以容纳的数据量没有限制。您完全可以将所有数据同时保存在一个对象中。此外，对象的变量只是对实际数据存储位置的引用。所以它不需要在内存中彼此相邻，它可以分散在各处。

相反，数组的所有数据都连接在内存中。这就是直接访问对于数组效果很好的原因。您拥有数组开始的基地址，知道元素的字节大小，并且可以通过它轻松计算出哪个元素开始在内存数据中的位置:

// Memory address of fifth element of an int[] array
base + 4 * sizeof(int)

这也是它们需要固定大小的原因。