9

我在下面有这段代码，我将一个新整数插入到整数的排序 LinkedList 但我不认为这是“正确”的做事方式，因为我知道有指向下一个值的单链表和双链表指向下一个和上一个值的指针。我尝试使用 Nodes 来实现以下情况，但 Java 正在导入这个 import org.w3c.dom.Node（文档对象模型）所以卡住了。

插入案例

  1. 插入空数组
  2. 如果要插入的值小于所有值，则在开头插入。
  3. 如果要插入的值大于所有值，则插入最后一个。

  4. 如果值小于/大于 LL 中的某些值，则可能介于两者之间。

    import java.util.*;

public class MainLinkedList {
public static void main(String[] args) {
LinkedList<Integer> llist = new LinkedList<Integer>();

llist.add(10);
llist.add(30);
llist.add(50);
llist.add(60);
llist.add(90);
llist.add(1000);
System.out.println("Old LinkedList " + llist);

//WHat if you want to insert 70 in a sorted LinkedList
LinkedList<Integer> newllist = insertSortedLL(llist, 70);
System.out.println("New LinkedList " + newllist);
}

public static LinkedList<Integer> insertSortedLL(LinkedList<Integer> llist, int value){

    llist.add(value);
    Collections.sort(llist);
    return llist;

}

    }

4

7 回答 7

21

如果我们使用 listIterator，那么 get 的复杂度将是 O(1)。

public class OrderedList<T extends Comparable<T>> extends LinkedList<T> {

    private static final long serialVersionUID = 1L;


    public boolean orderedAdd(T element) {      
        ListIterator<T> itr = listIterator();
        while(true) {
            if (itr.hasNext() == false) {
                itr.add(element);
                return(true);
            }

            T elementInList = itr.next();
            if (elementInList.compareTo(element) > 0) {
                itr.previous();
                itr.add(element);
                System.out.println("Adding");
                return(true);
            }
        }
    }
}
于 2013-10-27T02:43:59.660 回答
11

这可能完美地满足您的目的：

使用此代码：

import java.util.*;

public class MainLinkedList {
    private static LinkedList<Integer> llist;

    public static void main(String[] args) {
        llist = new LinkedList<Integer>();

        addValue(60);
        addValue(30);
        addValue(10);
        addValue(-5);
        addValue(1000);
        addValue(50);
        addValue(60);
        addValue(90);
        addValue(1000);
        addValue(0);
        addValue(100);
        addValue(-1000);
        System.out.println("Linked List is: " + llist);

    }

    private static void addValue(int val) {

        if (llist.size() == 0) {
            llist.add(val);
        } else if (llist.get(0) > val) {
            llist.add(0, val);
        } else if (llist.get(llist.size() - 1) < val) {
            llist.add(llist.size(), val);
        } else {
            int i = 0;
            while (llist.get(i) < val) {
                i++;
            }
            llist.add(i, val);
        }

    }

}

这种方法将在不使用的情况下以排序方式管理列表中的插入Collections.sort(list)

于 2013-08-09T15:53:45.023 回答
2

您可以简单地在 log (N) 时间复杂度内完成。无需遍历所有值。您可以使用二进制搜索向排序的链表添加值。只需在该函数的上限位置添加值即可。检查代码...您可能会更好地理解。

    public static int ubound(LinkedList<Integer> ln, int x) {
        int l = 0;
        int h = ln.size();
        while (l < h) {
            int mid = (l + h) / 2;
            if (ln.get(mid) <= x) l = mid + 1;
            else h = mid;
        }
        return l;
    }

    public void solve() 
    {
        LinkedList<Integer> ln = new LinkedList<>();
        ln.add(4);
        ln.add(6);
        ln.add(ubound(ln, 5), 5);
        out.println(ln);

    }

输出：[4,5,6]

您可以在以下位置了解有关二分搜索的更多信息：https ://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/

于 2017-12-26T23:12:57.363 回答
1

@Atrakeur

“每次添加新元素时对所有列表进行排序效率不高”

确实如此，但如果您需要列表始终处于排序状态，那么它确实是唯一的选择。

“最好的方法是直接将元素插入它必须在的位置（在他的正确位置）。为此，您可以循环所有位置以找到该数字所属的位置”

这正是示例代码所做的。

“或者使用 Collections.binarySearch 让这个高度优化的搜索算法为你完成这项工作”

二进制搜索是有效的，但仅适用于随机访问列表。因此，您可以使用数组列表而不是链表，但是随着列表的增长，您必须处理内存副本。如果列表的容量高于元素的实际数量（这很常见），你也会消耗比你需要的更多的内存。

因此，采用哪种数据结构/方法将在很大程度上取决于您的存储和访问要求。

[编辑] 实际上，示例代码存在一个问题：循环时会导致多次扫描列表。

int i = 0;
while (llist.get(i) < val) {
    i++;
}
llist.add(i, val);

对 get(i) 的调用将遍历列表一次以到达第 i 个位置。然后对 add(i, val) 的调用再次遍历它。所以这会很慢。

更好的方法是使用 ListIterator 遍历列表并执行插入。该接口定义了一个 add() 方法，可用于在当前位置插入元素。

于 2013-09-28T13:28:59.637 回答
1

看看com.google.common.collect.TreeMultiset。

这实际上是一个允许相同值的多个实例的排序集。

对于您正在尝试做的事情，这是一个很好的折衷方案。插入比 ArrayList 便宜，但您仍然可以获得二叉树/树搜索的搜索优势。

于 2016-10-25T14:52:48.407 回答
0

您必须通过了解订单条件来找到插入数据的位置。

简单的方法是暴力搜索插入位置（遍历列表，二进制搜索......）。

如果您知道数据的性质，另一种方法是估计插入位置以减少检查次数。例如，如果您插入“Zorro”并且列表按字母顺序排列，您应该从列表的后面开始......或者估计您的字母可能在哪里（可能接近结尾）。如果您知道数字的来源和分布方式，这也适用于数字。这称为插值搜索：http ://en.wikipedia.org/wiki/Interpolation_search

还要考虑批量插入：如果您快速插入大量数据，您可能会考虑一次性进行多次插入，然后只排序一次。

于 2013-08-09T10:43:02.927 回答
0

链表不是 SortedList 的更好实现

此外，每次添加新元素时对所有列表进行排序也效率不高。最好的方法是将元素直接插入它必须在的位置（在他的正确位置）。为此，您可以循环所有位置以查找该数字所属的位置，然后将其插入，或使用 Collections.binarySearch 让这个高度优化的搜索算法为您完成这项工作。

如果在列表中找到对象，则 BinarySearch 返回对象的索引（如果需要，您可以在此处检查重复项）或 (-(insertion point) - 1) 如果对象不在列表中（并且插入点是需要放置对象以保持顺序的索引）

于 2013-08-09T10:46:57.057 回答