java 排序链表实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7881559/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sorted linked list implementation
提问by ally
i am a novice programmer, to be specific, i am learning java programming and i am supposed to implement sortedLinkedList class that extends LinkedList class from the java library. The list has to store persons in ascending order of their surnames. I have already written my Person class that implements Comparable interface. my problem is, I have been struggling implementing this sortedLinkedClass but to no avail. My code runs without any compiling or run time error but the program does not print anything. Another thing as you can see , I am testing it with Integers instead of Persons and it throws NullPointerException when trying to add a number that is already in the list. My code is as it is below.
我是一名新手程序员，具体来说，我正在学习 Java 编程，我应该实现 sortedLinkedList 类，该类扩展了 Java 库中的 LinkedList 类。该列表必须按姓氏的升序存储人员。我已经编写了实现 Comparable 接口的 Person 类。我的问题是，我一直在努力实现这个 sortedLinkedClass 但无济于事。我的代码运行时没有任何编译或运行时错误，但程序不打印任何内容。正如您所看到的另一件事，我正在使用整数而不是人员进行测试，并且在尝试添加列表中已有的数字时会抛出 NullPointerException。我的代码如下。
import java.util.*;
public class SortedLinkedList< E> extends LinkedList<E>
{
private Link<E> first;
private Link<E> last;
/**
* Constructor for objects of class SortedLinkedList
*/
public SortedLinkedList()
{
//super();
first = null;
last = null;
}
/*
* Link class for creating Link nodes in the SortedLinkedList objects
*/
private class Link<E>
{
public Comparable<E> data;
public Link next;
}
/*
* Overiding add method from LinkedList class
*/
public boolean add(E obj)
{
Link newLink = new Link();
newLink.data = (Comparable<E>)obj;
// When the list is initially empty
if (first == null)
{
first = newLink;
last = newLink;
return true;
}
// When the element to be added is less than the first element in the list
if (newLink.data.compareTo(first.data) < 0)
{
//newLink.data = obj;
newLink.next = first;
first = newLink;
return true;
}
// When the element to be added is greater than every element in in list
// and has to be added at end of the list
if (newLink.data.compareTo(last.data) > 0)
{
//newLink.data = obj;
last.next = newLink;
last = newLink;
return true;
}
//When the element to be added lies between other elements in the list
if (newLink.data.compareTo(first.data) >= 0 && newLink.data.compareTo(last.data) <= 0)
{
//newLink.data = obj;
Link current = first.next;
Link previous = first;
while (newLink.data.compareTo(current.data) <= 0)
{
previous = current;
current = current.next;
}
previous.next = newLink;
newLink.next = current;
}
return true;
}
public static void main (String[] args)
{
LinkedList<Integer> list = new SortedLinkedList<Integer>();
list.add(4);
list.add(5);
list.add(10);
list.add(9);
//list.add(5);
ListIterator<Integer> iterator = list.listIterator();
while (iterator.hasNext())
{
System.out.println(iterator.next());
}
}
}
}
回答by Francisco Paulo
If you must use a LinkedList, all you really have to do is override the "add" method so that it inserts your element in the correct position. You can do that by invoking the add(integer,Object) method which inserts your element in a specific position.
如果您必须使用 LinkedList，您真正需要做的就是覆盖“add”方法，以便它在正确的位置插入您的元素。您可以通过调用将元素插入特定位置的 add(integer,Object) 方法来做到这一点。
Here's a quick and dirty (and non-generic :P) implementation of what I'm talking about.
这是我正在谈论的内容的快速和肮脏（和非通用：P）实现。
public class PersonLinkedList extends LinkedList<Person> {
public boolean add(Person personToAdd) {
int index = 0;
for( ; index<size() ; index++){
Person personAlreadyInList = get(index);
if(personToAdd.compareTo(personAlreadyInList) < 0){
break;
}
}
add(index, personToAdd);
return true;
};
public static void main(String[] args) {
Person amy = new Person("Amy");
Person bob = new Person("Bob");
Person claire = new Person("Claire");
PersonLinkedList list = new PersonLinkedList();
list.add(bob);
list.add(claire);
list.add(claire);
list.add(amy);
list.add(bob);
for (Iterator iterator = list.iterator(); iterator.hasNext();) {
Person person = (Person) iterator.next();
System.out.println(person);
}
}
}
class Person implements Comparable<Person>{
private String name;
public Person(String name) { this.name = name; }
public String getName() { return name; }
@Override
public String toString() { return getName();}
@Override
public int compareTo(Person p) {
return name.compareTo(p.name);
}
}
回答by Michael Krussel
The reason nothing gets printed is because you store the data in your own linked list data tree and not the LinkedList's data tree. You don't override the iterator method, so the iterator will loop through LinkedList's data which is empty. This is also a problem with all the other methods in LinkedList.
什么都不打印的原因是因为您将数据存储在自己的链表数据树中，而不是 LinkedList 的数据树中。您不会覆盖迭代器方法，因此迭代器将遍历 LinkedList 的空数据。这也是 LinkedList 中所有其他方法的问题。
Are you sure you need to inherit from the LinkedList class or are you suppose to make your own class.
您确定需要从 LinkedList 类继承还是想创建自己的类。
If you are supposed to inherit from LinkedList get rid of you node and use LinkedList for storing the data. Your add method would then use a ListIterator to find the correct spot for adding and use the add method of ListIterator.
如果你应该从 LinkedList 继承摆脱你的节点并使用 LinkedList 来存储数据。然后您的 add 方法将使用 ListIterator 找到正确的添加位置并使用 ListIterator 的 add 方法。
If you don't inherit from LinkedList then extend AbstractSequentialList.
如果您不从 LinkedList 继承，则扩展 AbstractSequentialList。
Note:
笔记：
Both of these options should not be used in real code. Adding automatic sorting breaks the List interface.
这两个选项都不应在实际代码中使用。添加自动排序打破了 List 界面。
The whole problem is a perfect example of "prefer composition over inheritance".
整个问题是“优先组合而不是继承”的完美例子。
If this is homework do it as instructed, otherwise I'd recommend changing the exercise to implement a SortedCollection backed by a LinkedList. Then implement Collection and use a List as a member variable.
如果这是作业，请按照说明进行，否则我建议更改练习以实现由 LinkedList 支持的 SortedCollection。然后实现 Collection 并使用 List 作为成员变量。
回答by Kent
besides iterator, add/removeoverride, I think your algorithm to sort is not correct. And that leads to the nullpointer exception when you add existing elements into your "sortedLinkedList".
除了iterator, add/remove覆盖之外，我认为您的排序算法不正确。当您将现有元素添加到“sortedLinkedList”时，这会导致空指针异常。
while (newLink.data.compareTo(current.data) <= 0)
{
previous = current;
current = current.next;
}
I think what you wanted is while (newLink.data.compareTo(current.data) >0). not <=0. here is the mistake.
我想你想要的是while (newLink.data.compareTo(current.data) >0)。不是<=0。这是错误。
since "=0" is in while condition, it will go through the whole list, till the last element, then execute:
由于“=0”在while条件下，它将遍历整个列表，直到最后一个元素，然后执行：
(current is the last now)
previous = current;
current = current.next; (now, current is Null, since last.next is Null)
finally, current is Null, then comes again, current = current.next; Bang! Nullpointer.
最后，current 为 Null，然后又来了，current = current.next; 砰! 空指针。
so I guess the Nullpointer was thrown at this line.
所以我猜 Nullpointer 是在这条线上抛出的。
回答by millimoose
You could use a SortedSetif you don't need to support elements with the same sort key.
如果不需要支持具有相同排序键的元素，则可以使用SortedSet。
Also, the reason your code doesn't print anything is because you override adding items to the list, but not iterating (the iterator()or listIterator()methods.) Extending LinkedListdoesn't automagically make your data structure iterable unless you modify its contents using the base class add(), remove(), and other methods.
此外，您的代码不打印任何内容的原因是因为您覆盖了向列表添加项目，但没有迭代（iterator()或listIterator()方法）。LinkedList除非您使用基类修改其内容，否则扩展不会自动使您的数据结构可迭代add()，remove()，以及其他方法。
