插入Sorted LinkedList Java
我在下面有这个代码，我将一个新的整数插入到一个有序的LinkedList中，但我不认为这是“正确”的做事方式，因为我知道有单一的链表，指针指向下一个值和双链表指向下一个和上一个值的指针。 我试图使用Nodes来实现以下情况，但是Java正在导入这个导入org.w3c.dom.Node（文档对象模型），所以卡住了。
插入案例
- 插入空数组
- 如果要插入的值少于所有内容，请在开头插入。
- 如果要插入的值大于所有值，请插入最后一个。
-
如果值小于/大于LL中的某些值，则介于两者之间。
import java.util.*; public class MainLinkedList { public static void main(String[] args) { LinkedList llist = new LinkedList(); 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 newllist = insertSortedLL(llist, 70); System.out.println("New LinkedList " + newllist); } public static LinkedList insertSortedLL(LinkedList llist, int value){ llist.add(value); Collections.sort(llist); return llist; }}
这可能完全符合您的目的：
使用此代码：
import java.util.*; public class MainLinkedList { private static LinkedList llist; public static void main(String[] args) { llist = new LinkedList (); 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); } } }
这个方法将以排序的方式管理List中的插入，而不使用Collections.sort(list)
如果我们使用listIterator，那么get的复杂性将是O（1）。
public class OrderedList> extends LinkedList { private static final long serialVersionUID = 1L; public boolean orderedAdd(T element) { ListIterator 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); } } } }
@Atrakeur
“每次添加新元素时对所有列表进行排序都不高效”
这是真的，但如果您需要列表始终处于已排序状态，那么它实际上是唯一的选择。
“最好的方法是将元素直接插入到必要的位置（在正确的位置）。为此，您可以循环所有位置以查找此数字所属的位置”
这正是示例代码所做的。
“或使用Collections.binarySearch让这个高度优化的搜索算法为您完成这项工作”
二进制搜索是有效的，但仅适用于随机访问列表。 因此，您可以使用数组列表而不是链接列表，但随着列表的增长，您必须处理内存副本。 如果列表的容量高于实际的元素数（这是非常常见的），您还将消耗比您需要的更多的内存。
因此，采用哪种数据结构/方法将在很大程度上取决于您的存储和访问要求。
[edit]实际上，示例代码存在一个问题：它在循环时导致列表的多次扫描。
int i = 0; while (llist.get(i) < val) { i++; } llist.add(i, val);
对get（i）的调用将遍历列表一次以到达第i个位置。 然后对add（i，val）的调用再次遍历它。 所以这将非常缓慢。
更好的方法是使用ListIterator遍历列表并执行插入。 此接口定义了一个add（）方法，该方法可用于在当前位置插入元素。
请查看com.google.common.collect.TreeMultiset 。
这实际上是一个排序集，允许多个相同值的实例。
对于您要做的事情，这是一个很好的妥协。 插入比ArrayList便宜，但您仍然可以获得二进制/树搜索的搜索优势。
链表不是SortedList的更好实现
此外，每次添加新元素时对所有列表进行排序效率不高。 最好的方法是将元素直接插入到必要的位置（在正确的位置）。 为此，您可以循环所有位置以查找此数字所属的位置，然后插入它，或使用Collections.binarySearch让这个高度优化的搜索算法为您完成此任务。
如果在列表中找到对象，BinarySearch将返回对象的索引（如果需要，可以在此处检查重复项）或（ – （插入点） – 1）如果对象未在列表中已全部（并且插入点为需要放置对象以维护顺序的索引）
您必须通过了解订单条件来找到插入数据的位置。
简单的方法是强制搜索插入位置（通过列表，二进制搜索…）。
如果您知道数据的性质，另一种方法是估计插入位置以减少检查次数。 例如，如果您插入’Zorro’并且列表按字母顺序排列，则应从列表的后面开始…或估计您的字母可能在哪里（可能在结尾处）。 如果您知道它们的来源以及它们的分布方式，这也适用于数字。 这称为插值搜索： http ： //en.wikipedia.org/wiki/Interpolation_search
还要考虑批量插入：如果快速插入大量数据，可以考虑一次性进行多次插入，之后只进行一次排序。
您可以简单地在log（N）时间复杂度中执行此操作。 无需遍历所有值。 您可以使用二进制搜索将值添加到已排序的链接列表。只需在该函数的上限位置添加值。 检查代码…你可能会更好理解。
public static int ubound(LinkedList 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 ln = new LinkedList<>(); ln.add(4); ln.add(6); ln.add(ubound(ln, 5), 5); out.println(ln); }
输出：[4,5,6]
您可以在以下url了解二进制搜索： https ： //www.topcoder.com/community/data-science/data-science-tutorials/binary-search/