Tag: linked list

LinkedList内存泄漏

我正在尝试调试挂起的应用程序。 该程序使用一个使用LinkedList实现的队列，在压力测试期间，我发现程序因堆内存不足而停止响应。 我分析了堆转储，发现内存似乎从LinkedList 。 堆转储的相关部分： ▶java.net.Vectior @ 0xff5eacd0 ▶▶java.util.Vector @ 0xff629f30 ▶▶▶java.lang.Object[1280] @ 0xff629f50 ▶▶▶▶class com.itnade.vsm.staticobject.TrapQueue @ 0xff6b23e8 ▶▶▶▶▶java.util.LinkedList @ 0xff6b2460 ▶▶▶▶▶▶java.util.LinkedList$Node @ 0xfb954560 ▶▶▶▶▶▶java.util.LinkedList$Node @ 0xfb959968 ▶▶▶▶▶▶java.util.LinkedList$Node @ 0xfb95ede8 ▶▶▶▶▶▶java.util.LinkedList$Node @ 0xfb964230 ▶▶▶▶▶▶java.util.LinkedList$Node @ 0xfb969638 … … 正如您在转储中看到的那样， LinkedList$Node不会被删除，并且会累积。 该计划的一般流程是： Queue.offer（）→Queue.poll→Queue.remove（object） 为什么LinkedList似乎是泄漏内存，我该如何防止这种情况发生？

在Java中覆盖Iterables 的正确方法

这是我为实现链表而编写的代码， private class DequeIterator implements Iterable { private Node pElement; DequeIterator() { pElement = first; } public boolean hasNext() { return pElement != null; } public Item next() { if (!this.hasNext()) { throw new NoSuchElementException(); } Item ret = pElement.it; pElement = pElement.next; return ret; } public void remove() { throw new UnsupportedOperationException(); } } […]

无法从Node 转换为Node ？

我只是从我的一本书中做了一些练习，我很好奇为什么我在eclipse中得到以下错误： Type mismatch: cannot convert from type DoublyLinkedList.Node to DoublyLinkedList.Node 码： import java.util.Iterator; import java.util.ListIterator; import java.util.NoSuchElementException; public class DoublyLinkedList<E extends Comparable> implements Iterable{ private int size = 0; private Node head; private Node tail; /** Returns a list iterator object for the list at * the specified index */ public DoublyLinkedList(){ } private static […]

Java：如何检查字符串是否是任何LinkedList元素的一部分？

好的，所以我有一个LinkedList，我有一个字符串。 我想检查String是否包含在任何LinkedList元素中。 例如： String a = “apple”; String listelement = “a bunch of apples”; LinkedList list = new LinkedList(); list.add(listelement); if(list.containsany(a){ System.out.println(“Hooray!”); } 会导致印刷“万岁！” 显然list.containsany不是一个真正的LinkedList方法，我只是为此目的使用它。 那我怎么模拟我的例子呢？ 谢谢

如何合并使用O（nlogn）时间和O（1）空间复杂度对链接列表进行排序

（免责声明：上学） 据我所知，递归拆分链表，然后将其发送到另一个要合并的函数是O（nlogn）时间和O（n）空间。 在O（nlogn）时间和O（1）空间复杂度的链表上是否可以进行合并？ 你会怎么做呢？ 任何帮助都表示赞赏 PS：为了确保传统的mergesort是空间复杂度0（n），这是0（n）的一个例子，对吧？ 如何改变O（1）空间？ void sortTrack() { Node merge = this.head; this.head = Node (merge); } public Node mergeSort(Node head){ if ((head == null)||(head.next == null)){ return head; } Node left = head; Node right = head.next; while((right != null) && right.next != null){ head = head.next; right = right.next.next; } right […]

冒泡手动排序Java中的链接列表

这是我的第一个问题。 我试图手动排序java中的整数链接列表，我无法弄清楚我的代码有什么问题。 有什么建议么？ 我没有得到任何错误，但我的输出仍然无序。 我尝试了几种不同的方式，但没有任何效果。 如果有人能帮助我，我感激不尽。 public class Node { int data; Node nextNode; public Node(int data) { this.data = data; this.nextNode = null; } public int getData() { return this.data; } } // Node class public class DataLinkedList implements DataInterface { private Node head; private int size; public DataLinkedList(){ this.head = null; this.size = […]

为什么LinkedList和arraylist在java中扩展AbstractList？

为什么LinkedList和ArrayList在Java中扩展AbstractList ？ 当我们想要在实现类中指定公共行为时，使用抽象类。 但是AbstractList中的所有方法都被ArrayList和LinkedList覆盖。 那么扩展这个类有什么用呢？

使用ListIterator在Java中的LinkedList上来回移动

我有一个LinkedList，我需要多次来回迭代。 我正在使用它来跟踪将动态创建的工作流中的一系列页面。 这并不像我期望的那样。 鉴于这个例子： LinkedList navigationCases; navigationCases.add(“page1”); navigationCases.add(“page2”); navigationCases.add(“page3”); navigationCases.add(“page4”); ListIterator navigationItr = navigationCases.listIterator(); navigationItr.next(); // Returns page1 navigationItr.next(); // Returns page2 navigationItr.previous(); //Returns page2 again navigationItr.next(); //Returns page2 again 我想也许我正在错误地构建我的列表，或者使用Iterator错误，但在阅读文档之后，这似乎是设计的： ListIterator没有当前元素; 它的光标位置总是位于调用previous（）返回的元素和调用next（）返回的元素之间。 和： （Next）返回列表中的下一个元素。 可以重复调用此方法以遍历列表，或者与之前的调用混合以来回传递。 （注意，对next和previous的交替调用将重复返回相同的元素。） 因此，在阅读本文之后，很明显为什么我的代码表现得像它那样。 我只是不明白为什么它应该这样工作。 甚至删除似乎是向后弯曲以适应这种实现： 请注意，remove（）和set（Object）方法没有根据光标位置定义; 它们被定义为对next（）或previous（）调用返回的最后一个元素进行操作。 从概念上讲，LinkedList似乎很好地模拟了我的工作流案例，但我不能使用行为方式的Iterator。 我在这里遗漏了什么，或者我应该只写自己的class级来维护案例列表并浏览它们？

LinkedList如何添加（int，E）O（1）复杂度？

从链表标签维基摘录： 链表是一种数据结构，其中元素包含对下一个（以及可选的前一个）元素的引用。 链接列表提供在任何位置的O（1）插入和移除 ，O（1）列表串联，以及前（和可选后）位置的O（1）访问以及下一元素访问的O（1）。 随机访问具有O（N）复杂性并且通常是未实现的。 （强调我的） 我很惊讶地读到这一点 – 如何将列表插入一个复杂度低于简单读取索引的随机索引？ 所以我查看了java.util.LinkedList的源代码 。 add(int, E)方法是： public void add(int index, E element) { addBefore(element, (index==size ? header : entry(index))); } addBefore(E, Entry方法只是指针重新分配，但也有entry(int)方法 ： if (index = size) throw new IndexOutOfBoundsException(“Index: “+index+ “, Size: “+size); Entry e = header; if (index > 1)) { for (int i = 0; […]

反转线性链表

线性链表是一组节点。 这是节点的定义方式（为了方便起见，我们不区分节点和列表）： class Node{ Object data; Node link; public Node(Object pData, Node pLink){ this.data = pData; this.link = pLink; } public String toString(){ if(this.link != null){ return this.data.toString() + this.link.toString(); }else{ return this.data.toString() ; } } public void inc(){ this.data = new Integer((Integer)this.data + 1); } public void lappend(Node list){ Node child = this.link; while(child […]