Обращение связанного списка в Java без изменения оригинала

Question

Я пытаюсь изменить связанный список, который работает, но когда я пытаюсь распечатать оригинал, он не работает (только печатает голову). Мой вопрос заключается в том, почему реверсирование влияет на оригинал. Ниже мой код. LinkedList - это мой собственный класс, так что это Node. Перед реверсом, если я пытаюсь распечатать свой список, это работает.

public static void main(String[] args) { 
    LinkedList list; 
    ... 
    Node head = list.getHead(); 
    Node rev = reverse(head); 
    Node temp = rev; 
    while (temp != null) { 
     System.out.println(temp); 
     temp = temp.next; 
    } 

    temp = head; 
    while (temp != null) { 
     System.out.println(temp); 
     temp = temp.next; 
    } 
} 

private static reverse(Node head) { 
    // Reversing the linked list 
} 

EDIT :: Это кажется Java вещь. Java передает объект по ссылке. Когда я передаю головку в качестве параметра, она передается по ссылке, и любое изменение, внесенное в нее, отражается в вызывающей функции. Выполнение узла h = head, а затем передача h в качестве параметра не будет работать, так как h будет тем же объектом, что и голова. Единственный вариант, о котором я могу думать, это создать новый объект, скопировать связанный список и передать его как параметр.

Мой вопрос будет, есть ли лучшее решение?

Answer 1

Чтобы понять это, картина ваш список выглядит следующим образом

list (list.head =a) --> a (a.next=b) --> b (b.next= c) -> c (c.next = null) 

Если вы получаете голову, то вы получаете объект «а». Затем вы изменяете объект 'a'. Итак, вы можете видеть, что редактируете список, делая это.

Что вам нужно сделать, это: Получить голову Создать копию Reverse копию Получить следующий элемент Скопируйте его Reverse это вступите к последнему и так далее

С вами используют классы собственных классов, а не классы java, самый простой способ - убедиться, что reverseNode() только редактирует копию того, который вы передаете, и возвращает копию. Сначала убедитесь, что ваш класс Node имеет конструктор, который копирует другой узел, а затем сделать что-то вроде этого:

private static Node reverse(Node original) 
{ 
    Node retval = new Node(original); 
    // or you could use clone() as Bhavik suggested, if your Node class implements it 
    // modify retval 
    // I haven't shown code to reverse it as I assume you already have that and you didnt specify if it was a bidirectional list or just one direction. 

    return retval; 
} 

Или вы можете добавить статический метод в классе Node, который строит новый узел, который обращенный:

static Node createReverse(Node n) 
{ 
    return new Node(n.data,n.next,n.prior); 
} 

Или нестационарный метод класса узлов, который возвращает обратную копию самого себя;

Node createReverse() 
{ 
    return new Node(this.data,this.next,this.prior); 
} 

Но вы должны учитывать это может получить очень некрасиво, потому что ваши копии будут по-прежнему иметь указатели, указывающие в существующий список!

Лучшей техникой может быть создание нового пустого списка, а затем начать с конца оригинала, сделать копию и добавить ее в начало нового списка.

Вы можете использовать рекурсию для этого, но может легко закончиться память.

Но вместо этого вручную вы можете посмотреть пакеты java.util и переключиться на использование одного из их типов LinkedList и списка. Эти классы уже решили все проблемы с этим.

Тогда вы могли бы (если вам нужно сохранить исходный список немодифицированным): - Сделайте копию всего вашего списка. - отмените копию, указанную ниже

Если вы не заботитесь о сохранении оригинала, просто используйте этот метод (ниже) в своем списке, поэтому не нужно делать копию.

От java.util.Collections:

Collections.reverse(List a_list); 

Коллекция класс будет выбрать эффективный способ обратного список, в зависимости от того, является ли он двунаправленным, однонаправленное и т.д.

Answer 2

ответа Chunko является прямо в том, что вы должны создавать копии своих узлов, а не просто передавать ссылки на них.
Однако, я думаю, вы могли бы быть overthinking это:

LinkedList reversedList = new LinkedList(); 
for (int i = originalList.size()-1; i >= 0; i--) { 
    reversedList.add(list.get(i)); 
} 

в Java LinkedList не имеет метод getHead(), так что я предполагаю, что вы используете некоторые домашние задания, связанные с пользовательской реализации связанного списка. Тем не менее, ваша реализация должна иметь метод add(), который добавляет новый список Node в список, а также метод get(int), который возвращает элемент в данной позиции.
Вы можете использовать эти методы для создания нового списка и заполнить его элементами исходного списка в обратном порядке.