java.util.LinkedList causing infinite loop/OutOfMemoryError

Question

I'm implementing Cloneable with one of my classes, and I need to make a shallow copy (yes, only shallow) of a java.util.LinkedList to do it. I tried using

myList.clone() //myList is a java.util.LinkedList<myType>

but that was causing my program to stall, so I switched to using the copy constructor:

new LinkedList<myType>(myList)

but it still hangs up. Now this was only happening with a myType that was an enum, but now I just had the same error with a non- enum type, though now that I think of it that type has an inner enum type. this has happened both on Sun's jdk 1.6 and openjdk 1.6. I'm sure I'm doing something wrong, but I can't figure out what I'd be doing that would break LinkedList. It's not throwing an Exception until it eventually runs out of memory, (usually I kill it before this happens). Anyway, any ideas what might be causing this?

here is the clone method:

public Note clone(){
 List<Accidental> retAcc=new LinkedList<Accidental>();
 for(Accidental acc:accidentals)retAcc.add(acc.clone());
 return new Note(retAcc,position,restFlag,new LinkedList<TieType>(beginTies),new LinkedList<TieType>(endTies),tripFlag,duration);
}

TieType is an enum type, Accidental implements Cloneable and its clone() method is reproduced below. position, restFlag, tripFlag, and duration are all primitives

public Accidental clone(){
 return new Accidental(acType,fltPosition);

}

acType is an inner enum type, fltPosition is is a float, these initialize the only two fields in accidental.

the problem is happening in the last line of the Note.clone() method when I call the LinkedList copy constructor. This used to be a call to LinkedList.clone, but I changed it in an attempt to avoid this problem. Here is the stack trace for this error (there is no error here, as I suspended the thread when it froze, rather than waiting for it to run out of memory, but as you can see, it was in the middle of the LinkedList copy constructor)

LinkedList.(Collection) line: 115
Note.clone() line: 86
Note.simplify(int) line: 98
Note.split(int, List, List) line: 179
ManagedPart$Measure.adjustRemaining(int) line: 378 ManagedPart$Measure.add(Note) line: 349
ManagedPart$Measure.access$1(ManagedPart$Measure, Note) line: 345
ManagedPart.addNote(Note) line: 216
PartEditor$EditPanel$3.actionPerformed(ActionEvent) line: 104
JButton(AbstractButton).fireActionPerformed(ActionEvent) line: 2012
AbstractButton$Handler.actionPerformed(ActionEvent) line: 2335 DefaultButtonModel.fireActionPerformed(ActionEvent) line: 404
DefaultButtonModel.setPressed(boolean) line: 259
BasicButtonListener.mouseReleased(MouseEvent) line: 253
JButton(Component).processMouseEvent(MouseEvent) line: 6108
JButton(JComponent).processMouseEvent(MouseEvent) line: 3276
JButton(Component).processEvent(AWTEvent) line: 5873
JButton(Container).processEvent(AWTEvent) line: 2105
JButton(Component).dispatchEventImpl(AWTEvent) line: 4469
JButton(Container).dispatchEventImpl(AWTEvent) line: 2163
JButton(Component).dispatchEvent(AWTEvent) line: 4295
LightweightDispatcher.retargetMouseEvent(Component, int, MouseEvent) line: 4461
LightweightDispatcher.processMouseEvent(MouseEvent) line: 4125 LightweightDispatcher.dispatchEvent(AWTEvent) line: 4055
MusedDesktopClient(Container).dispatchEventImpl(AWTEvent) line: 2149
MusedDesktopClient(Window).dispatchEventImpl(AWTEvent) line: 2478
MusedDesktopClient(Component).dispatchEvent(AWTEvent) line: 4295
EventQueue.dispatchEvent(AWTEvent) line: 604
EventDispatchThread.pumpOneEventForFilters(int) line: 275
EventDispatchThread.pumpEventsForFilter(int, Conditional, EventFilter) line: 200
EventDispatchThread.pumpEventsForHierarchy(int, Conditional, Component) line: 190
EventDispatchThread.pumpEvents(int, Conditional) line: 185 EventDispatchThread.pumpEvents(Conditional) line: 177
EventDispatchThread.run() line: 138

Also recently, I've had a similar problem with the construction of the LinkedList in the first line of Note.clone() i. e.

List<Accidental> retAcc=new LinkedList<Accidental>();

here is the stack trace for that:

Exception in thread "AWT-EventQueue-0" java.lang.OutOfMemoryError: Java heap space at java.util.LinkedList.(LinkedList.java:95) at com.mused.util.noteMgmt.Note.clone(Note.java:84) at com.mused.util.noteMgmt.Note.simplify(Note.java:98) at com.mused.util.noteMgmt.Note.split(Note.java:179) at com.mused.util.noteMgmt.ManagedPart$Measure.adjustRemaining(ManagedPart.java:378) at com.mused.util.noteMgmt.ManagedPart$Measure.insert(ManagedPart.java:335) at com.mused.util.noteMgmt.ManagedPart.insertNote(ManagedPart.java:223) at com.mused.gui.editor.PartEditor.currentIndexChanged(PartEditor.java:161) at com.mused.gui.NoteViewer.fireIndexChangeEvent(NoteViewer.java:178) at com.mused.gui.NoteViewer.setCurrentIndex(NoteViewer.java:417) at com.mused.gui.NoteViewer.updateSelected(NoteViewer.java:627) at com.mused.gui.NoteViewer.mouseMoved(NoteViewer.java:725) at java.awt.Component.processMouseMotionEvent(Component.java:6153) at javax.swing.JComponent.processMouseMotionEvent(JComponent.java:3294) at java.awt.Component.processEvent(Component.java:5877) at java.awt.Container.processEvent(Container.java:2105) at java.awt.Component.dispatchEventImpl(Component.java:4469) at java.awt.Container.dispatchEventImpl(Container.java:2163) at java.awt.Component.dispatchEvent(Component.java:4295) at java.awt.LightweightDispatcher.retargetMouseEvent(Container.java:4461) at java.awt.LightweightDispatcher.processMouseEvent(Container.java:4138) at java.awt.LightweightDispatcher.dispatchEvent(Container.java:4055) at java.awt.Container.dispatchEventImpl(Container.java:2149) at java.awt.Window.dispatchEventImpl(Window.java:2478) at java.awt.Component.dispatchEvent(Component.java:4295) at java.awt.EventQueue.dispatchEvent(EventQueue.java:604) at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:275) at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:200) at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:190) at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:185) at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:177) at java.awt.EventDispatchThread.run(EventDispatchThread.java:138)

Answer 1

Have you checked the memory allocation options to the JVM? Specifically -Xms and -Xmx. You could have just filled up all memory allocated by default. Can you try with

-Xms256m -Xmx1024m

and see if it fails in the same place?

Answer 2

There is nothing wrong with LinkedList::clone(). If it's hanging, then your list is corrupt, having somehow formed a circular link. Here's an exerpt of the only relevant code from java/util/LinkedList.java:

for (Entry e = header.next; e != header; e = e.next)
    clone.add(e.element);

This is the same algorithm used for LinkedList::toArray(), so if clone() hangs, then so should this:

System.out.println(Arrays.toString(myList.toArray()));

If that hangs, your list is corrupt. The most likely culpret would be syncronization issues. LinkedList is not thread safe. Try synching your declaration like this:

List<myType> myList = Collections.synchronizedList(new LinkedList<myType>());

Answer 3

Okay, so I figured it out. I had thought that I was doing something that caused an infinite loop in LinkedList, but what actually happened was that i wrote an infinite loop that included calls to LinkedList methods, and it just happened that whenever I suspended the thread or the system ran out of memory, it was during the execution of a LinkedList method.
Apparently those must take longer to execute than the rest of the code inside the loop or something. Because it was always in LinkedList when I looked at the stack trace, I assumed I was somehow breaking LinkedList, when in actuality my broken code was simply calling LinkedList methods repeatedly until I stopped it or it ran out of memory.