0

我一直试图弄清楚链接列表是如何工作的，但我很难想象这个概念。我知道多种算法，但我不知道如何实现它们。

这是我的代码：

public class LL {
    private ListNode front,last; 

    public LL(){
        front = null; last = null;
    }

    //
    //methods here...
    //

    public class ListNode{
        public double coefficient;
        public int exponent;
        public ListNode next;

        public ListNode(){
            this(0, 0, null);
        }

        public ListNode(double coefficient, int exponent, ListNode next){
            this.coefficient = coefficient; 
            this.exponent = exponent;
            this.next = next;
        }
    } 
}

这是用于存储多项式的数据。我试图让他们按降序排列。并最终将具有相同指数的节点的系数相加。

我想我要使用冒泡排序算法，但我不知道如何重新排列链接。我也在考虑添加一个 remove() 方法，然后删除一个节点并将其添加到最后，直到它被排序。但这非常低效，因为我每次都必须不断制作新节点。

PS：我还有一个多项式类，它接受一个字符串并将其转换为 LL。我认为没有必要发布它，但如果你需要它，我会发布它！谢谢！

4

1 回答 1

1

排序链表确实效率低下，通常您会将列表列表复制到数组中，对其进行排序并复制回来（这就是JDK所做的）

顺便说一句，除非你有非常稀疏的缺陷，否则最好使用数组或数组列表。这不仅更简单、更高效、更快捷，而且是自然排序的。

即使您有很多零系数，数组也将使用一小部分内存和链表。

于 2014-11-16T11:27:49.137 回答