出于实践目的，已经为我提供了如下所示的代码，我的任务是对其进行修改，以便始终对链表进行排序。我现在的主要问题是我不知道从哪里开始或要修改什么方法。欢迎任何提示。
import java.util.Iterator;
import java.util.NoSuchElementException;
/
* This is a copy of the LinkedList class, which has been modified to only
* accept elements that can be compared.
*
* Note that the elements accepted by this list must implement the Comparable
* interface. This means that the elements can be compared as follows:
*
* x.compareTo(y) == 0 means x == y
* x.compareTo(y) < 0 means x < y
* x.compareTo(y) > 0 means x > y
*
* Your task is to modify this class so that the elements always are sorted.
*/
public class SortedLinkedList<T extends Comparable<T>> implements Iterable<T> {
/* Easy operations for a linked list
add(x): Searching for the place where the element x is to be added must
take place in the calling routine. This must set previous to
point to the node AFTER which the new element is to be inserted.
curr is set to point to the new element.
remove(): The curr element is removed from the list. Searching for this
element must take place in the calling routine. This must set
curr to point to the element to be removed. After removal curr
points to the element following the removed one.
isEmpty(): checks for an empty list
endOfList(): checks whether curr has reached and passed the end of the list
retrievecurr(): return the info part of the curr element.
reset(): resets the list so that curr points to the first element
succ(): an iterator, moves curr one step forward
Note that when a class implements the interface Iterable<T> then
it can be the target of the "foreach" statement. See IterationExample.java
*/
private Node start, curr, prev;
public SortedLinkedList() {
curr = null; // the curr position in the list
start = null; // the first element
prev = null; // the node before curr
}
public void add(T x) {
if (start == null) { // if start == null, insert a first element into an empty list
Node newNode = new Node(); // create the new element, info and link are set to null.
newNode.info = x; // and assign the data given as parameter. The link is left as null
start = newNode; // start is updated to point to the new element
curr = start; // curr is updated to point to the new first (and only) element
} else if (prev == null) { // a new first element is inserterd into a non-empty list
Node newNode = new Node(); // a new node is created ...
newNode.info = x; // and assigned the data given as parameter
newNode.link = start; // and linked before the old first element
start = newNode; // start is updated to point to the new first element
curr = newNode; // curr is updated to point to the new first element
} else { // a new element is inserted last (if prev.link == null) or between prev and curr
Node newNode = new Node(); // create a new node
newNode.info = x; // assign it the data given as parameter
newNode.link = prev.link; // link it before curr ...
prev.link = newNode; // ... and after previous
curr = newNode; // update curr to point to newNode
}
} // add
public void remove() { // removes the current node
if (isEmpty() || endOfList()) { // no node to be removed
return;
}
else { // curr points to the element to be removed
if (prev == null) { // remove a first element: start is updated!
start = start.link; // "jump over" the first element (curr/start)
curr = start; // update curr to point to the new start
}
else { // the element to be removed is in the middle of the list/last
prev.link = curr.link; // "jump over it!"
curr = curr.link; // curr is updated to the element after the removed one
}
}
} // remove
public boolean isEmpty() { // checks if the list is empty
return start == null;
}
public T retrieveCurr() { // return the curr element's data
return curr.info;
}
public void reset() { // resets a list so that curr points to the first element
curr = start; // curr starts from the beginning of the list
prev = null; // there is no previous element for curr
}
public boolean endOfList() { // has curr reached and passed the end of the list?
return curr == null;
}
public void succ() { // moves curr to the next element
curr = curr.link; // curr is set to the next node
if (prev == null) { // previous must follow; if it was null to begin with ...
prev = start; // ... it must now point to start
}
else {
prev = prev.link; // otherwise it is just moved one step forward
}
}
public Iterator<T> iterator(){ //Needed to implement the iterable interface
return new ListIterator();
}
private class Node {
T info;
Node link;
Node() {
info = null;
link = null;
}
}
/*
* An example iterator class to walk through the list from
* the start to the end. Note the similarity with the methods
* above. They implement similar functionality, but here it
* is hidden behind a standard interface.
*
* Note the class is private and the implementation of the iterator
* is therefore not visible outside.
*
* See the java api documentation for more information on
* how iterators should behave.
*/
private class ListIterator implements Iterator<T>{
private Node curr;
public ListIterator(){
curr=start;
}
public boolean hasNext(){
return curr!=null;
}
public T next(){
if(curr==null){
throw new NoSuchElementException();
}
T value=curr.info;
curr=curr.link;
return value;
}
public void remove(){
throw new UnsupportedOperationException();
}
}
}
最佳答案
我认为实现的唯一大变化是在插入元素时保持列表排序。请注意，反向操作（即删除元素）不需要更改，因为您只是扔掉了东西，不会改变列表中的任何顺序。
下面的add()方法在列表中向下移动，直到找到合适的位置。然后，它拼接新节点并在适用的情况下更新start，prev和curr指针。
public void add(T x) {
Node newNode = new Node();
newNode.info = x;
// case: start is null; just assign start to the new node and return
if (start == null) {
start = newNode;
curr = start;
// prev is null, hence not formally assigned here
return;
}
// case: new node to be inserted comes before the current start;
// in this case, point the new node to start, update pointers, and return
if (x.compareTo(start.info) < 0) {
newNode.link = start;
start = newNode;
curr = start;
// again we leave prev undefined, as it is null
return;
}
// otherwise walk down the list until reaching either the end of the list
// or the first position whose element is greater than the node to be
// inserted; then insert the node and update the pointers
prev = start;
curr = start;
while (curr != null && x.compareTo(curr.info) >= 0) {
prev = curr;
curr = curr.link;
}
// splice in the new node and update the curr pointer (prev already correct)
newNode.link = prev.link;
prev.link = newNode;
curr = newNode;
}