Пузырьковая сортировка двусвязного списка Java

Я пытаюсь создать пузырьковую сортировку в двусвязном списке на Java, но получаю ошибки исключения нулевого указателя. Я считаю, что это проблема, когда я вызываю метод getPrevious для головы, который, конечно, имеет значение null. Однако я не могу придумать, как выполнить пузырьковую сортировку без доступа к методу getPrevious для других узлов.

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

Мне также не удалось запустить успешную сборку этого, поэтому я даже не уверен, что код будет работать. Если у вас есть другое представление о том, как реализовать это, пожалуйста, дайте мне знать.

Любые предложения приветствуются!

 public static void bubbleSort(DoubleLinkedList list) //static method used to sort the linked list using bubble sort
  {
      int i = 0;
      int j = 0;
      Node currentNode = list.head;
      Node previousNode = currentNode;
      Node tempNext =  currentNode;
      Node tempPrevious = currentNode;


      for(i=0; i<list.getSize(); i++)
      {
          for(j=0; j<list.getSize()-1; i++)
          {
              if(currentNode.getData() > currentNode.getNext().getData())
              {
                  tempNext = currentNode.getNext().getNext();
                  tempPrevious = currentNode.getPrevious();
                  currentNode.getPrevious().setNext(currentNode.getNext());
                  currentNode.getNext().setNext(currentNode);
                  currentNode.setPrevious(currentNode.getNext());
                  currentNode.setNext(tempNext);

              }

              currentNode = currentNode.getNext();

          }
      }



  }

java sorting linked-list doubly-linked-list bubble-sort
person ZAX    schedule 26.09.2012    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Итак, у вас есть двусвязный список. Я предполагаю, что каждый элемент содержит некоторую информацию... скажем, целое число. Он также должен содержать два указателя: один на предыдущий элемент и один на следующий элемент.

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

Вы можете сделать это следующим образом:

public static void bubbleSort(DoubleLinkedList list) //static method used to sort the linked list using bubble sort {
      int i = 0;
      Node currentNode = list.head;
      Node auxNode;
      int foundChange = 1;
      while(foundChange) {
        foundChange = 0;
        for(i=0; i<list.getSize()-1; i++) {
          if (currentNode.getData() > currentNode.getNext().getData()) {
            auxNode.setData(currentNode.getData());
            currentNode.setData(currentNode.getNext.getData());
            currentNode.getNext.setData(auxNode.getData());
            foundChange = 1;
          }
          currentNode = currentNode.getNext();
        }

}

Если вы еще не определили метод setData, сделайте это. Он должен быть похож на getData, но он будет устанавливать данные объекта в значение, которое он получает в качестве параметра, вместо того, чтобы возвращать значение данных в этом объекте.

person Ionut Hulub    schedule 26.09.2012
comment
Я видел это решение раньше, но я не согласен и думаю, что это возможно, если бы узел сказал... 3,4,5 поля. - person H.Rabiee; 25.11.2014