java - 在我的 sortedLinkedList 中跟踪前一个节点的最佳方法是什么？

Question

我在 CS 课上的教授让我对 LinkedList 进行排序。我试图用来对链表进行排序的方法是在将新的 int 添加到链表时这样做。问题的关键在于，他推荐我用来对链表进行排序的方法要求我以某种方式跟踪链表中的前一个元素是什么，尽管它是单链表而不是双链表。我一定要问他是否要我创建一个双向链表，他说那不是他在说的。最大的障碍是在我的 add 函数内的第二个 else-if 代码块上，这里的代码在哪里：

if ((int) input < (int) current.value){
                   LinkedListNode newnode = new LinkedListNode(input, current);

我不确定如何跟踪以前的。最好的方法是什么？

public class SortedLinkedList<T extends Comparable<T>> {

  private LinkedListNode head;

  SortedLinkedList() {
    head = null;
  }

  // Start from head
  // Check its value
  // 2 nodes at once
  // Check previous node
  // Check next node
  // Check after head before end
  // Check last element

  public synchronized void add(T input) {

    LinkedListNode current;

    if (head == null) {

      LinkedListNode newNode = new LinkedListNode(input, null);
      head = newNode;
      head.setIndex(0);

    } else if ((int) input < (int) head.value) {

      current = head;

      LinkedListNode newNode = new LinkedListNode(input, null);
      head = newNode;

      newNode.setNext(current);
    } else if ((int) input > (int) head.value) {
      current = head;

      while (current.getNext() != null) {

        if ((int) input < (int) current.value) {
          LinkedListNode newnode = new LinkedListNode(input, current);
        }

        current = current.getNext();
      }

    } else {

      current = head;
      int indexCounter = head.index;
      while (current.getNext() != null) {

        current = current.getNext();
        indexCounter++;

        int currentgetNEXTHOLDER;
        int currentValueHolder;

        // Loops through the functuon and switches any values less than the previous

        if ((int) current.getNext().value < (int) current.value) {
          currentgetNEXTHOLDER = (int) current.getNext().value;
          currentValueHolder = (int) current.value;

          current.getNext().value = currentValueHolder;
          current.value = currentgetNEXTHOLDER;
        }
      }

      current.setIndex(indexCounter);
      LinkedListNode mynewNode = new LinkedListNode(input, null);
      current.setNext(mynewNode);
    }
  }

  public T getValue(int index) {

    T keeptheValue = null;
    LinkedListNode current = getHead();

    while (current.getNext() != null) {
      if (current.index == index) {
        keeptheValue = (T) current.value;
      }

      current = current.getNext();
    }

    return keeptheValue;
  }

  public Boolean search(T value) {
    LinkedListNode current = getHead();
    boolean isitThere = false;
    while (current.getNext() != null) {
      if (current.value == value) {
        isitThere = true;
      }
    }
    return isitThere;
  }

  public LinkedListNode getHead() {
    return head;
  }

  public String printAllValues() {
    LinkedListNode current = head;
    String intTOStringchain = "";
    while (current.getNext() != null) {

      intTOStringchain = intTOStringchain + "," + Integer.toString((int) current.value);
    }

    return intTOStringchain;
  }

  class LinkedListNode<T extends Comparable<T>> {

    public T value;
    private LinkedListNode next;
    public int index;
    public LinkedListNode previous;

    public LinkedListNode(T value, LinkedListNode next) {
      this.value = value;
      this.next = next;
    }

    public LinkedListNode getNext() {
      return next;
    }

    public void setNext(LinkedListNode next) {
      this.next = next;
    }

    public LinkedListNode getPrevious() {
      return previous;
    }

    public void setPrevious(LinkedListNode previous) {
      this.previous = previous;
    }

    public boolean greaterThan(T otherValue) {

      int definingValue = otherValue.compareTo(value);
      if (definingValue > 0) {
        return true;
      } else {
        return false;
      }
    }

    public void setIndex(int index) {
      this.index = index;
    }
  }
}

以上是类中的所有代码，任何帮助将不胜感激。

标签： javalinked-list

Answer 1

add 方法的伪代码：

prev = null
curr = head
while curr != null and curr.value <= value:
    prev = curr
    curr = curr.next
if prev == null then:
    head = new Node(value, curr)
else:
    prev.next = new Node(value, curr)

您的代码过于复杂。真的就是这么简单。