跟踪我的sortedLinkedList中的上一个节点的最佳方式

Question

我CS班的教授让我对LinkedList进行排序。我尝试使用的对linkedlist进行排序的方法是，每当向链表中添加新的int时都这样做。问题的实质是，他建议我使用的排序链表的方法要求我以某种方式跟踪链表中的前一个元素是什么，尽管它是一个单链表，而不是一个双链表。我一定要问他是否希望我创建一个双重链接的列表，他说这不是他在说的。最大的障碍是，在第二天，如果代码块在我的add函数中，这个代码在哪里？

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;
}
}
}

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

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)

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

Answer 2

如果您的列表源自java.util.List

int idx = Collections.binarySearch( list, valueToAdd );
if( idx < 0 )
idx = -idx - 1;
list.add( idx, valueToAdd );

如果使用上述方法添加所有元素，则列表中的所有元素都将按排序