为不同类的通用链表实现 Comparable

Question

首先：我不是要重新发明轮子，这是为了学习。

我是 java 世界的新手，所以请耐心等待。

我的目标是构建一个 public class 来管理带排序插入的链表。

到目前为止我所做的（有效的）是：

import java.util.Iterator;

import package_Car.SortTypes;

class Node<E>
{
    E data;
    Node<E> next;

    Node(E data, Node<E> node)
    {
        this.data = data;
        this.next = node;
    }

    public Node<E> getNext()
    {
        return next;
    }
}

public class SortedInsertionLinkedList<E> implements Iterable<Node<E>>
{
    Node<E> root;
    Sort_Types sort;

    final class LinkedListIterator implements Iterator<Node<E>>
    {
        private Node<E> cursor;

        LinkedListIterator(Node<E> root)
        {
            cursor = new Node<E>(null, null);
            cursor = root;
        }

        public boolean hasNext()
        {       
            return cursor != null;
        }

        public Node<E> next()
        {
            Node<E> retVal = cursor;

            if (hasNext())
            {
                cursor = retVal.getNext();
            }

            return retVal;      
        }
    }   

    public Iterator<Node<E>> iterator()
    {
        return new LinkedListIterator(root);
    }

    public SortedInsertionLinkedList(Sort_Types sort)
    {
        root = null;
        this.sort = sort;
    }

    public void insert(E item)
    {
        if (item != null)
        {
            if (root == null)
            {
                root = new Node<E>(item, null);
            }
            else
            {
                Node<E> currNode = root;
                Node<E> prevNode = null;

                for (Node<E> currListNode : this) 
                {
                    if (sort.compareTo(currListNode.data, item) < 0)
                    {
                        prevNode = currListNode;
                        currNode = currListNode.next;
                    }
                }

                Node<E> t = new Node<E>(item, currNode);

                if (prevNode == null)
                    root = t;
                else
                    prevNode.next = t;

            }
        }
    }

    public void print()
    {
        for (Node<E> currNode : this)
        {
            System.out.print(currNode.data + " ");
            System.out.println();
        }
        System.out.println();
    }

    public boolean find(E x)
    {
        for (Node<E> currNode : this)
        {
            int c = sort.compareTo(currNode.data, x);

            if (c == 0)
                return true;
            if (c > 0)
                return false;
        }
        return false;
    }

    public void delete(E x)
    {
        Node<E> prevNode = null;
        for (Node<E> currNode : this)
        {
            int c = sort.compareTo(currNode.data, x);
            if (c == 0)
            {
                if (currNode == root)
                {
                    root = currNode.next;
                }
                else
                {
                    prevNode.next = currNode.next;
                }

                return;
            }
            if (c > 0)
                return;

            prevNode = currNode;
        }
    }
}

如您所见，我在 class 中添加了一个私有字段，用于定义必须使用哪种类型的排序来比较链表节点。这种排序类型是枚举

public enum Sort_Types
{
    SORT_BY_NAME
    {
        public int compareTo(Object o1, Object o2)
        {
            Car item1 = (Car) o1;
            Car item2 = (Car) o2;

            return item1.nome.compareTo(item2.nome);
        }
    },
    SORT_BY_PRICE
    {
        public int compareTo(Object o1, Object o2)
        {
            Car item1 = (Car) o1;
            Car item2 = (Car) o2;

            return Double.compare(item1.prezzo, item2.prezzo);
        }
    },
    SORT_BY_GAIN
    {
        public int compareTo(Object o1, Object o2)
        {
            double gain1;
            double gain2;

            if (o1 instanceof CarSpecificInterface)
            {
                CarSpecificInterface dummy = (CarSpecificInterface) o1;
                gain1 = dummy.gain();
            }
            else
            {
                throw new IllegalArgumentException();
            }

            if (o2 instanceof CarSpecificInterface)
            {
                CarSpecificInterface dummy = (CarSpecificInterface) o2;
                gain2 = dummy.gain();
            }
            else
            {
                throw new IllegalArgumentException();
            }

            return Double.compare(gain2, gain1);
        }
    },
    SORT_BY_URGENCY
    {
        public int compareTo(Object o1, Object o2)
        {
            double urgency1;
            double urgency2;

            if (o1 instanceof CarSpecificInterface)
            {
                CarSpecificInterface dummy = (CarSpecificInterface) o1;
                urgency1 = dummy.urgency();
            }
            else
            {
                throw new IllegalArgumentException();
            }

            if (o2 instanceof CarSpecificInterface)
            {
                CarSpecificInterface dummy = (CarSpecificInterface) o2;
                urgency2 = dummy.urgency();
            }
            else
            {
                throw new IllegalArgumentException();
            }        

            return Double.compare(urgency2, urgency1);
        }
    };

    public abstract int compareTo(Object o1, Object o2);
}

我为什么这么做？因为可以用来实例化链表的class是3:

Car
New_Car 那 extends Car
Used_Car 即 extends Car

New_Car 和 Used_Car classes 实现了一个接口

public interface Car_Specific_Interface
{
    public double gain();
    public double urgency();
}

所以我可以将我的链表用于可以接受（显然）子类的 Car 类型

Sorted_Linked_List<Car> carsSortedByName;
Sorted_Linked_List<Car> carSortedByGain;
Sorted_Linked_List<Car> carSortedByUrgency;

public DB_Mng()
{
    carsSortedByName = new Sorted_Linked_List<>(Sort_Types.SORT_BY_NAME);
    carSortedByGain = new Sorted_Linked_List<>(Sort_Types.SORT_BY_GAIN);
    carSortedByGain = new Sorted_Linked_List<>(Sort_Types.SORT_BY_URGENCY);
}

所以，总结一下：我有一个 带有排序插入 的通用链表，它可以接受不同的 classes 并且可以按特定字段或方法排序。

我想了解的是，是否有办法改变 classes 层次结构 "simply" 实现 Comparable 接口。

Answer 1

我建议完全退后一步。有了 Java8 和 lambdas 以及流，2017 年的事情确实有所不同。或者好吧，多年来。

我建议您从 Java 斯图加特 2014 论坛中查看此 presentation。一些德语的开头词，但其余都是代码，并且易于掌握。

事情是：你想写这样的代码：

collection .sort(
  Comparator
  .comparing(Person::getName)
  .reversed()
  .thenComparing(Person::getId)
);

并使用 lambdas / 方法引用 - 而不是编写所有 "manual boilerplate" 代码来访问成员字段。

Answer 2

第一步是了解 java 泛型。具体来说， java 泛型是一个编译时特性；它们绝不是 c++ 模板的 java 实现。

您无法创建 "fully general" 插入时排序列表，因为 Object 未实现任何比较功能。

您可以创建一个插入时排序的元素列表，这些元素实现了一些已知的接口或扩展了特定的 class。

Answer 3

如果 NewCar 和 UsedCar 都在实现 Car_Specific_Interface，您可以只检查比较器中的接口，例如：

        if (o1 instanceof Car_Specific_Interface)
        {
            Car_Specific_Interface dummy = (Car_Specific_Interface) o1;
            gain1 = dummy.gain();
        }
        else
        {
            throw new IllegalArgumentException();
        }

你也可以让你比较复杂的功能来支持Comparable和Comparator。例如：

private int compareItems(E firstItem, E secondItem) {
    if (sort == null) {
        if (firstItem instanceof Comparable && secondItem instanceof Comparable) {
            return ((Comparable)firstItem).compareTo(secondItem);
        } else {
            throw new IllegalArgumentException("Failed to compare");
        }
    } 
    return sort.compareTo(firstItem, secondItem);
}

为不同类的通用链表实现 Comparable

Implement Comparable for generic Linked List for different classes

java

sorting

comparable

为不同 类 的通用链表实现 Comparable

Implement Comparable for generic Linked List for different classes

java

sorting

comparable

为不同类的通用链表实现 Comparable