排序链表实现

Question

我是一名新手程序员，具体来说，我正在学习 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());
    }


}

}

Answer 1

如果您必须使用 LinkedList，您真正需要做的就是覆盖“add”方法，以便它在正确的位置插入您的元素。您可以通过调用将元素插入特定位置的 add(integer,Object) 方法来做到这一点。

这是我正在谈论的内容的快速和肮脏（和非通用：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);
    }
}