Реализация списка ссылок в Java не похожа на список ссылок, как в переполнении стека

Я просматривал LinkedList и видел реализацию в Java. В те времена, когда я пытался и реализовывал связанный список, он был с указателями и адресами, и много тяжелой работы. С Java реализация проще, но все же потребовалось немного усилий с моей стороны. То, что я знаю о связанном списке, ясно из следующей диаграммы, где 1,2,3,4 являются узлами связного списка.
введите описание изображения здесь

Однако в java код, с которым я столкнулся, заставил меня думать о LinkedList как о следующей диаграмме.введите описание изображения здесь

Код реализации связанного списка в Java выглядит следующим образом:

class LinkedListNode
{
LinkedListNode nextNode = null;//consider this member variable
int data;
public LinkedListNode(int data)
{
this.data = data;
}
void appendItemToLinkedList(int newData)
{
LinkedListNode end = new LinkedListNode(newData);
LinkedListNode temp = this;
while (temp.nextNode != null) { temp = temp.nextNode; }
temp.nextNode = end;

}
}

а также

public static void main(String[] args)
{
LinkedListNode list = new LinkedListNode(10);
list.appendItemToLinkedList(20);
list.appendItemToLinkedList(30);
list.appendItemToLinkedList(40);
list.appendItemToLinkedList(50);
list.appendItemToLinkedList(60);
}

На диаграмме вы можете ясно видеть, что объекты узла находятся внутри других объектов узла. Это действительно связанный список. Или родительский контейнер, содержащий другой контейнер внутри него и так далее?

3

Решение

Вторая диаграмма является результатом мышления, что один список содержит другой (как если бы LinkedList типа были примитивного типа).

Первая диаграмма получается, когда вы думаете об одном LinkedList привязка другой.

Так как LinkedList является ссылочным типом, а не примитивным типом, nextNode поле не хранит полный LinkedList на месте, но только ссылка на один. Таким образом, ваша первая диаграмма является правильной, даже в Java.

Смотрите также:

5

Другие решения

Реализации Linked-List в Java и в C ++ на самом деле очень похожи. Единственная разница — это естественная разница, вызванная разным языком. В обоих случаях у вас будет сущность (класс) для LinkedListNode. У обоих в этом классе будет поле next которая будет ссылкой в ​​Java или указателем в C ++ на следующий узел. Метод вставки тоже будет выглядеть одинаково. Так что в целом, это просто похоже 🙂

И схема, которая соответствует этому дизайну, конечно, первая.

1

LinkedList в Java реализован как двойной LikedList, поэтому он не является примитивным типом, как в C ++.
К сведению: из выступления Stock (Doctor Deprecator) в JavaOne 2016, java планирует отказаться от поддержки LinkedLists, Vectors и некоторых других структур данных по уникальным причинам. Отсюда путаница и техническая разница, которая может существовать.

0
По вопросам рекламы [email protected]