Перемещение последнего узла из связанного списка на фронт


Описание:

Данный связанный список переместить последний узел на фронт.

Например:

10 20 30 40 -> 40 10 20 30

Код:

class Main {
  static class Node {
    private int data;
    private Node next;

    Node(int data, Node next) {
      this.data = data;
      this.next = next;
    }

    Node append(int data) {
      Node newNode = new Node(data, null);
      Node current = this;

      while (current.next != null) {
        current = current.next;
      }
      current.next = newNode;
      return this;
    }

    public String toString() {
      Node current = this;
      StringBuilder sb = new StringBuilder();

      while (current != null) {
        // do something here
        sb.append(current.data);
        sb.append(" ");
        current = current.next;
      }
      return sb.toString();
    }
  }

  public static Node moveTailToHead(Node head) {
    if (head == null || head.next == null) {
      throw new IllegalStateException(
          "List should have atleast two elements");
    }

    Node current = head;
    Node prev = null;

    while (current.next != null) {
      prev = current;
      current = current.next;
    }
    prev.next = null;
    current.next = head;
    head = current;

    return head;
  }

  public static void main(String[] args) {
    Node head = new Node(10, null);
    head.append(20)
        .append(30)
        .append(40);
    System.out.println(head); // 10 20 30 40

    Node newHead = moveTailToHead(head);
    System.out.println(newHead); // 40 10 20 30

    try {
      System.out.println(
        "Should not happen: " + moveTailToHead(null));
    } catch (IllegalStateException e) {
      System.out.println(
        "Got expected exception for null node");
    }

    try {
      System.out.println(
        "Should not happen: " + moveTailToHead(new Node(10, null)));
    } catch (IllegalStateException e) {
      System.out.println(
        "Got expected exception for single node");
    }
  }
}

Вопрос:

Я пишу код на Java после долгого времени и хотел бы знать, если я делаю какую-либо ошибку или злоупотребление функцией Java.



Комментарии
3 ответа

Вы не только сможете получить доступ к Nodeс поля data и next из метода moveTailToHead(Node) поскольку этот метод объявлен в том же верхнем уровне класса Node. Я не знаю, почему вы выбрали этот дизайн на ваш пример кода, но то, что вы сделали Способ moveTailToHead а static метод вне класса Node а не экземпляр метод Node заставляет меня думать, что moveTailToHead это также должно работать "снаружи", не имея доступа к Node'ы внутренние детали реализации, так что мне интересно, является ли ваш код дизайн в этом отношении является преднамеренным. Если это так, то я не буду спорить против этого, но если это не так и если moveTailToHead также должна работать, если она была объявлена в разных топ-уровне класса, вы должны реализовать Способ Node чтобы обеспечить какой-то способ доступа к содержимому списка, который он представляет. Начало может быть Node для реализации интерфейса Iterable<Integer>, что потребует Node иметь iterator() метод. Этот метод может, например, выглядеть так:

@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
private Node nextNode = Node.this; //the next node to be returned by next()
private Node currentNode = null; //the last node returned by next()
private Node previousNode = null; //the node that precedes currentNode

@Override
public boolean hasNext() {
return nextNode != null;
}

@Override
public Integer next() {
if (!hasNext()) {
throw new NoSuchElementException();
} else {
if (currentNode != null) {
previousNode = currentNode;
}
currentNode = nextNode;
int nextData = nextNode.data;
nextNode = nextNode.next;
return nextData;
}
}

@Override
public void remove() {
if (currentNode == null) {
throw new IllegalStateException();
} else if (previousNode != null) {
currentNode.next = null;
previousNode.next = nextNode;
currentNode = null;
} else {
assert currentNode == Node.this;
throw new UnsupportedOperationException();
}
}
};
}

Таким образом, вы можете также избавиться от дублирования кода, когда вы выполните итерации через список, используя конструкции вроде while (current.next != null) или похожие.

Если вы посмотрите на Способ remove()становится очевидным, что то, что вы используете Node объект для обозначения собственно список сам, какие Xtreme байкер уже раскритиковал в своем ответе, является проблематичным. С головного узла также определяет перечень, это не возможно, чтобы удалить головной узел из списка, который является, почему я сделал способ бросить UnsupportedOperationException для полноты картины в этот демонстрационный код.

Но помимо этой проблемы, с Iterable реализованы, добавив другие методы для добавления и удаления элементов не должно быть очень сложно, и тогда вы можете двигать хвостом узел к голове, не имея прямого доступа к private поля Node.data и Node.next.

2
ответ дан 29 марта 2018 в 11:03 Источник Поделиться

Проблема здесь заключается в том, что каждый из Node элементы знает только о его следующему элементу. В принципе, вы сохранить только ссылку на первый Node элемент для того, чтобы ссылаться на весь связанный список.

Я бы скорее пойти с оболочкой, что делает абстракцию над Node класса так как вы можете контролировать полезные параметры, такие как размер списка, и предоставляет разработчику большую АПИ, что-то вроде этого:

public class NodeLinkedList{

private class Node{
private int data;
private Node next;

Node(int data){
this.data = data;
}

append(Node node){
this.next = node;
}

convertInLast(){
this.next = null;
}
}

//Reference to the first element
private Node list;

//Auxiliar for size
private int size;

public NodeLinkedList(int first){
list = new Node(first);
size = 1;
}

public void append(int element){
list.append(element);
size ++;
}

public void lastToFirst(){
if (size > 1){
Node first = list;
int i = 1;
while (i < size){
//Here, you do your switching stuff
}
}

}

}

0
ответ дан 29 марта 2018 в 10:03 Источник Поделиться

У меня есть некоторые замечания.

Вы можете получить лучшую производительность, если вы реализуете void appendAll(Integer[]) что только идет в конце списка после.
Сейчас создание связанного списка размер n с цепью добавляет принимает (Н-1) + (п-2) + .. = н*(н-1)/2 = О(nˆ2).

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


  • Предположение head != null это справедливо и нужно бросить NullPointerException в этом случае. Это начинает пахнуть moveTailToHead должен быть методом экземпляра узла, то вам не нужно беспокоиться об этом пограничном случае.

  • В head.next != null случай не является исключительным, и не нужно было это исключение. Или это требование? В этом случае голова=хвост, поэтому нам не нужно переключаться. Просто поймать эту базу-дело пораньше и просто вернуть аргумент. Так if (head.next == null) { return head;}

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

0
ответ дан 30 марта 2018 в 08:03 Источник Поделиться