Java ListNode Element einfügen ohne Bibliothek

[Alex04_]

Ich muss eine selbst-sortierende, einfach verkettete Liste in Java programmieren, ohne Bibliotheken zu verwenden.
Folgendes Interface ist gegeben:

[CODE lang="java" title="Interface"]public class ListNode {
public ListNode next; /** Pointer to next element */
public int value; /** The value of the current element */
}

public ListNode insert(ListNode head, int value);


public ListNode search(ListNode head, int value);


public ListNode minimum(ListNode head);
[/CODE]



Ich hab bis jetzt das, was aber nicht wirklich funktionieren wird, da ich mehrere Elemente einfügen muss.


[CODE lang="java" title="Insert Methode"]@Override
public ListNode insert(ListNode head, int value)
{


ListNode element1 = new ListNode();
element1.value = 34;


return element1;
}[/CODE]



Zudem habe ich noch diese Methode in der Testklasse:


[CODE lang="java" title="Testmethode"] @Test
public void testListInsert()
{
for(int i = 0; i < NUM_TESTS; ++i)
{
int[] test = getRandomArray(ARRAY_SIZE_SMALL);
ListNode head = null;
for(int j = 0; j < test.length; ++j)
{
head = ab1Impl.insert(head, test[j]);
assertNotNull(head);
}
Arrays.sort(test);
for(int j = 0; j < test.length; ++j)
{
assertEquals(test[j], head.value);
head = head.next;
}
}
}[/CODE]

 

[Oneixee5]

Mal eine dumme Frage, was soll denn head in dem Interface darstellen?

 

[Alex04_]

Head ist der Pointer auf das erste Element einer sortierten Liste.


Hab es jetzt so probiert, leider ohne Erfolg:

[CODE lang="java" title="Insert Methode"] @Override
public ListNode insert(ListNode head, int value)
{
ListNode element = new ListNode();
element.value = value;
element.next = null;

if(head == null) {
head = element;
}
else {
ListNode last = head;
while (last.next != null) {
last = last.next;
}

last.next = element;
}

return element;



}[/CODE]

 

[Oneixee5]

Ich sehe in deinem Code auch keinen Ansatz für eine "selbst-sortierende" Liste. Das Interface passt auch irgendwie nicht zu "selbst-sortierende" - hier stimmt etwas nicht. Du musst vermutlich noch mal näher erleutern, was "selbst-sortierende Liste" bedeuten soll.

 

[Kirby.exe]

Ich vermute einfach mal das deine Insert Methode einfach an die „richtige“ Stelle einfügen muss um immer eine Sortierung aufrecht zu erhalten 😉

 

[Alex04_]

Naja die Aufgabenstellung lautet so:

Einfach-verkettete, selbst-sortierende Liste: Implementieren Sie folgende Operationen auf einer einfach verketteten Liste. Gehen Sie davon aus, dass Listen, die Sie übergeben bekommen aufsteigend sortiert sind. Am Ende jeder Operation soll die Liste nach-wie-vor aufsteigend sortiert sein!
• Einfügen eines Elements (auf Sortierung achte); • Suchen eines Elements
• Finden des kleinsten Elements der Liste.
Ihre Verfahren sollen In-Place (also mit max. O(1) zusätzlichem Speicher) arbeiten.

Interface und Testmethode ist bereits vorgegeben und soll nicht verändert werden.

 

[Alex04_]

Die Methoden sind alle schon eingefügt man muss nur noch den Code schreiben