Guten Tag,
leider komme ich bei der Aufgabe einer Altklausur nicht weiter. Kann mir jemand erklären, wie diese Aufgabe funktioniert? Musterlösungen habe ich leider keine zu der genannten Aufgabe.
Grüße Niklas
Das geht so:
Man erwartet von dir dass du die Aufgabe liest, das Problem verstehst und dann eine Lösung anbietest.
Hier erwarten wir von dir dass du konkrete Fragen stellst, anstatt deine Hausaufgaben 1:1 hier einstellst und erwartest dass wir die Aufgabe lesen, für dich lösen und nebenbei noch erklären.
Es geht hier nicht um eine Hausaufgabe sondern um die Klausurvorbereitung für nächste Woche.
Ich verstehe halt leider gar nicht, was der Code macht und habe daher leider auch keinen Lösungsansatz. Es wäre echt cool, wenn du mir die Aufgabe nicht löst, aber zumindest mal erklärst, was der Code macht, bzw. was die einzelnen Zeilen im Code bedeuten.
Moin,
ich biete auch KEINE Musterlösung an, aber durch folgenden Code sollte schnell deutlich werden, was dort geschieht:
import java.util.Arrays;
public class DList {
public static class Node {
Node prev, next;
String obj;
public Node(Node prev, String obj, Node next) {
this.prev = prev;
this.next = next;
this.obj = obj;
}
@Override
public String toString() {
return "Node{" + (prev == null ? prev : prev.obj) + ", " + obj + ", " + (next == null ? next : next.obj) + "}";
}
}
private Node[] a = simulate();
public Node[] simulate() {
Node[] a = {
new Node(null, "Paul", null),
new Node(null, "Maria", null),
new Node(null, "Peter", null),
new Node(null, "Otto", null)
};
for (int i = 0; i < 3; i++) {
a[i].next = a[i + 1];
a[3 - i].prev = a[2 - i];
}
return a;
}
public void print(int lineNumber) {
System.out.println(lineNumber + ": " + Arrays.toString(a));
}
public void listAlgorithm(Node head) {
print(41);
Node t = head.next.next;
print(43);
t.next.obj = head.obj;
print(45);
head.obj = t.obj;
print(47);
t.obj = t.prev.obj;
print(49);
t.prev = head;
print(51);
head.next = t.next;
print(53);
t.prev.next.next = t;
print(55);
}
public static void main(String[] args) {
DList dList = new DList();
dList.listAlgorithm(dList.a[0]);
}
}
41: [Node{null, Paul, Maria}, Node{Paul, Maria, Peter}, Node{Maria, Peter, Otto}, Node{Peter, Otto, null}]
43: [Node{null, Paul, Maria}, Node{Paul, Maria, Peter}, Node{Maria, Peter, Otto}, Node{Peter, Otto, null}]
45: [Node{null, Paul, Maria}, Node{Paul, Maria, Peter}, Node{Maria, Peter, Paul}, Node{Peter, Paul, null}]
47: [Node{null, Peter, Maria}, Node{Peter, Maria, Peter}, Node{Maria, Peter, Paul}, Node{Peter, Paul, null}]
49: [Node{null, Peter, Maria}, Node{Peter, Maria, Maria}, Node{Maria, Maria, Paul}, Node{Maria, Paul, null}]
51: [Node{null, Peter, Maria}, Node{Peter, Maria, Maria}, Node{Peter, Maria, Paul}, Node{Maria, Paul, null}]
53: [Node{null, Peter, Paul}, Node{Peter, Maria, Maria}, Node{Peter, Maria, Paul}, Node{Maria, Paul, null}]
55: [Node{null, Peter, Paul}, Node{Peter, Maria, Maria}, Node{Peter, Maria, Paul}, Node{Maria, Paul, Maria}]
Problem: Insofern ich das richtig sehe, entsteht nach den Operationen von listAlgorithm KEINE valide zusammenhängende doppelt verkettete Liste mehr…
Das macht es schwierig, weil Prüflinge/Studierende eigentlich davon ausgehen, „sinnvolle“ Aufgaben lösen zu müssen.
Nach den Operationen ist „Otto“ nicht mehr referenziert und wird vom GC gefrühstückt…
Also, ich bin zwar nicht gut im Zeichnen, aber es sollte danach so aussehen:
Was ich allerdings gefühlt als falsch empfinde. Kann das jemand bestätigen?
Ja, Entschuldigung, ich habe mich verzeichnet…
import java.util.Arrays;
public class DList {
public static class Node {
Node prev, next;
String obj;
int index;
public Node(String obj, int index) {
this.obj = obj;
this.index = index;
}
@Override
public String toString() {
return "Node{" + (prev == null ? null : prev.index) + ", " + obj + ", " + (next == null ? null : next.index) + "}";
}
}
private Node[] a = simulate();
private Node head = a[0];
public Node[] simulate() {
Node[] a = {
new Node("Paul", 1),
new Node("Maria", 2),
new Node("Peter", 3),
new Node("Otto", 4)
};
for (int i = 0; i < 3; i++) {
a[i].next = a[i + 1];
a[i + 1].prev = a[i];
}
return a;
}
public void print(int lineNumber) {
System.out.println(lineNumber + ": " + Arrays.toString(a));
}
public void listAlgorithm(Node head) {
print(0);
Node t = head.next.next;
print(1);
t.next.obj = head.obj;
print(2);
head.obj = t.obj;
print(3);
t.obj = t.prev.obj;
print(4);
t.prev = head;
print(5);
head.next = t.next;
print(6);
t.prev.next.next = t;
print(7);
}
public static void main(String[] args) {
DList dList = new DList();
dList.listAlgorithm(dList.head);
}
}
@maki : Ich finde diese Aufgabe zu schwer, weil man sich in Gedanken zu viele Dinge merken muss. Du auch? Ich muss mir ja quasi 6-mal nacheinander den Zustand der kompletten Liste merken und diesen anschließend aufschreiben. Welchen Mehrwert hat das?
Oder anders, ich muss mir jeweils 11 „Chunks“ im Kurzzeitgedächtnis merken. Durchschnittlich merkt man sich aber nur 7 ±2 „Chunks“ im Kurzzeitgedächtnis. Um diese Aufgabe überhaupt korrekt lösen zu können, muss man also eine gewisse genetische „Prädisposition“ haben…
Hier handelt es sich um eine doppelt verkettete Liste, d.h. jedes Element kennt seinen Nachfolger und Vorgänger.
Jetzt zum Code, diese Methode macht etwas, sieht seltsam aus und ist wohl Absicht.
next ist das nächste Element, prev das vorherige
Node t = head.next.next
t zeigt also auf das dritte element (head.next.next)
t.next.obj = head.obj
Da werden die eigentlichen Nutzdaten vom 4 Listenelement „umgehängt“, also das 4. Listenelement zeigt jetzt auf die Nuztdaten die das erste Listenelement hatte, konkret „Paul“.
Das geht dan so weiter mit weiteren umhängen etc.
Du musst also nur „malen“, wie die Liste nach dieser Methode aussieht, das geht Zeilenweise 
Finde ich auch, keine Ahnung ehrlich gesagt welchen Mehrwert das hat, ist wohl nur eine Übung um Leute zu verwirren und auszusortieren…
die Grafik ist ja auch „k****“ 
Okay, vielen Dank für die ganzen Antworten. Ich habe es nun verstanden, danke!
Welche Operation soll man denn den Studenten in einer Klausuraufgabe zu verketteten Listen vorlegen, um zu sehen, ob sie ungefähr verstehen, worum es da geht? append oder insert oder remove vielleicht? Dann lernen die fleißigen „Ich-will-eine-gute-Note-damit-ich-einen-hochbezahlten-Computer-Job-bekomme“-Schlauköpfe genau diese Operationen auswendig, kriegen eine gute Note, und dann einen hochbezahlten Computer-Job, und … haben null Ahnung, was ein Computer so den ganzen Tag macht.
Aussortieren ist gut, das sollte viel mehr gemacht werden.
(Ein Nebeneffekt für die kleine Randgruppe derer, die Nerds sind, und deswegen „Empathie“ vielleicht nicht wirklich „empfinden“, aber doch auf technischer Ebene verstehen, ist vielleicht, dass sie dann merken: „Oh, das ist kompliziert und verwirrend, und das zu lesen und nachzuvollziehen macht nicht so viel Spaß - ich versuch’ in Zukunft, meinen Code besser zu schreiben, als das“)
das was da gezeichnet ist, ist keine doppelt verkette Liste - das geht definitiv besser
Um ganz exakt zu sein:
also die Nutzdaten des 4. Listenelements zeigt jetzt auf die Nutzdaten die das erste Listenelement hat
Im Grunde genommen wurde durch diese Zuweisung das gesamte 4. Objekt inkonsistent bzw. Zerstört. Die Nutzdaten die das 4. Objekt hatte sind unwiederbringlich verloren. Es wird ja nichts getauscht, sondern zugewiesen.
jup - das Ding ist völlig Mist - mal abgesehen davon, wenn Peter & Otto als Head übergeben werden, dann knallts…
mittagspause zu ende, mogel
Genau das hätte ich gemacht, das „Muster“ dieser Methoden auswendig gelernt, ja. 
Ich meine, zurzeit stehen dort einfach willkürliche Befehle, imo.
Abgesehen von eben hier, habe ich nur noch in Vorstellungsgesprächen mit verketten Listen zu tun, damit sind einfach und doppelt verkettete Listen absolut wichtig 
Ich ärgere mich jedesmal in eine Vorstellungsgespräch dazu Aufgabe zu bekommen, ist vollkommen irrelevant für die Praxis.
Meine erste einfach und doppelt verkettete Listen hab ich in den 90er Jahren selber abgetippt aus einem Programmiermagazin (lol), denn es gab keine eingebauten dyn. Speicherstrukturen in Turbo Pascal 3.0
Weiss nicht ob Informatik immer noch „überlaufen“ ist als Studiengang, aber da wurde schon heftig aussortiert was ich so mitbekommen habe.
Ja, ausserdem geht das Beispiel komplett am Sinn von verketteten Listen vorbei, Elemente umhängen wäre ein sinnvoll, anstatt die Werte umzuschiessen.
Ich weiß, man kann so etwas immer auch auf die Spitze treiben, aber so würde ein (schöner) Cluster-Graph dazu gemalt werden (die Graphviz dot engine muss dafür nicht installiert sein):
import info.leadinglight.jdot.ClusterGraph;
import info.leadinglight.jdot.Edge;
import info.leadinglight.jdot.Graph;
import info.leadinglight.jdot.Node;
import info.leadinglight.jdot.enums.Dir;
import info.leadinglight.jdot.enums.Rankdir;
import info.leadinglight.jdot.enums.Style;
import java.awt.*;
import java.io.IOException;
import java.net.URI;
import java.net.URLEncoder;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.Arrays;
public class DList {
public static class DNode {
public DNode prev, next;
public String obj;
public int index;
public DNode(String obj, int index) {
this.obj = obj;
this.index = index;
}
@Override
public String toString() {
return "Node{" + (prev == null ? null : prev.index) + ", " + obj + ", " + (next == null ? null : next.index) + "}";
}
}
private final DNode[] a = simulate();
private final DNode head = a[0];
public DNode[] simulate() {
DNode[] a = {
new DNode("Paul", 1),
new DNode("Maria", 2),
new DNode("Peter", 3),
new DNode("Otto", 4)
};
for (int i = 0; i < 3; i++) {
a[i].next = a[i + 1];
a[i + 1].prev = a[i];
}
return a;
}
public void print(int lineNumber) {
System.out.println(lineNumber + ": " + Arrays.toString(a));
}
public void showGraph() {
Graph g = new Graph("ag").setRankDir(Rankdir.LR);
g.addNode(new Node("Paul"));
g.addNode(new Node("Maria"));
g.addNode(new Node("Peter"));
g.addNode(new Node("Otto"));
for (DNode n : a) {
g.addClusterGraph(new ClusterGraph("" + n.index).addNodes(
new Node(n.index + "_1").setLabel("" + (n.prev == null ? null : n.prev.index)),
new Node(n.index + "_2").setLabel("Ref"),
new Node(n.index + "_3").setLabel("" + (n.next == null ? null : n.next.index))).addEdges(
new Edge(n.index + "_1", n.index + "_2").setDir(Dir.both),
new Edge(n.index + "_2", n.index + "_3").setDir(Dir.both)));
}
for (int i = 1; i < 4; i++) {
g.addEdge(new Edge(i + "_3", (i + 1) + "_1").setStyle(Style.Edge.invis).setDir(Dir.both));
}
g.addEdge(new Edge("Paul", "Maria").setStyle(Style.Edge.invis).setDir(Dir.both));
g.addEdge(new Edge("Maria", "Peter").setStyle(Style.Edge.invis).setDir(Dir.both));
g.addEdge(new Edge("Peter", "Otto").setStyle(Style.Edge.invis).setDir(Dir.both));
/*
for (DNode n : a) {
if (n.prev != null) {
g.addEdge(new Edge(n.index + "_1", n.prev.index + "_2"));
}
g.addEdge(new Edge(n.index + "_2", n.obj));
if (n.next != null) {
g.addEdge(new Edge(n.index + "_3", n.next.index + "_2"));
}
}
*/
try {
Files.writeString(Path.of("my-graph-ag.dot"), g.toDot());
Desktop.getDesktop().browse(URI.create("https://dreampuf.github.io/GraphvizOnline/#" + URLEncoder.encode(g.toDot(), StandardCharsets.UTF_8).replace("+", "%20")));
} catch (IOException e) {
e.printStackTrace();
}
}
public void listAlgorithm(DNode head) {
print(0);
DNode t = head.next.next;
print(1);
t.next.obj = head.obj;
print(2);
head.obj = t.obj;
print(3);
t.obj = t.prev.obj;
print(4);
t.prev = head;
print(5);
head.next = t.next;
print(6);
t.prev.next.next = t;
print(7);
showGraph();
}
public static void main(String[] args) {
DList dList = new DList();
dList.listAlgorithm(dList.head);
}
}
<!-- https://mvnrepository.com/artifact/info.leadinglight/jdot -->
<dependency>
<groupId>info.leadinglight</groupId>
<artifactId>jdot</artifactId>
<version>1.0</version>
</dependency>
So entsteht fast genau die gegebene Abbildung:
import info.leadinglight.jdot.ClusterGraph;
import info.leadinglight.jdot.Edge;
import info.leadinglight.jdot.Graph;
import info.leadinglight.jdot.Node;
import info.leadinglight.jdot.enums.Dir;
import info.leadinglight.jdot.enums.Rankdir;
import info.leadinglight.jdot.enums.Style;
import java.awt.*;
import java.io.IOException;
import java.net.URI;
import java.net.URLEncoder;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.Arrays;
public class DList {
public static class DNode {
public DNode prev, next;
public String obj;
public int index;
public DNode(String obj, int index) {
this.obj = obj;
this.index = index;
}
@Override
public String toString() {
return "Node{" + (prev == null ? null : prev.index) + ", " + obj + ", " + (next == null ? null : next.index) + "}";
}
}
private final DNode[] a = simulate();
private final DNode head = a[0];
public DNode[] simulate() {
DNode[] a = {
new DNode("Paul", 1),
new DNode("Maria", 2),
new DNode("Peter", 3),
new DNode("Otto", 4)
};
for (int i = 0; i < 3; i++) {
a[i].next = a[i + 1];
a[i + 1].prev = a[i];
}
return a;
}
public void print(int lineNumber) {
System.out.println(lineNumber + ": " + Arrays.toString(a));
}
public void showGraph() {
Graph g = new Graph("ag").setRankDir(Rankdir.LR);
g.addNode(new Node("temp").setStyle(Style.Node.invis));
for (DNode n : a) {
g.addClusterGraph(new ClusterGraph("" + n.index).addNodes(
new Node(n.index + "_1").setLabel("" + (n.prev == null ? null : n.prev.index)),
new Node(n.index + "_2").setLabel("Ref"),
new Node(n.index + "_3").setLabel("" + (n.next == null ? null : n.next.index))).addEdges(
new Edge(n.index + "_1", n.index + "_2").setStyle(Style.Edge.invis).setDir(Dir.both),
new Edge(n.index + "_2", n.index + "_3").setStyle(Style.Edge.invis).setDir(Dir.both)));
}
for (int i = 1; i < 4; i++) {
g.addEdge(new Edge(i + "_3", (i + 1) + "_1").setStyle(Style.Edge.invis).setDir(Dir.both));
}
g.addClusterGraph(new ClusterGraph("5").addNodes(
new Node("Paul"),
new Node("Maria"),
new Node("Peter"),
new Node("Otto")).addEdges(
new Edge("Paul", "Maria").setStyle(Style.Edge.invis).setDir(Dir.both),
new Edge("Maria", "Peter").setStyle(Style.Edge.invis).setDir(Dir.both),
new Edge("Peter", "Otto").setStyle(Style.Edge.invis).setDir(Dir.both)));
g.addEdge(new Edge("1_2", "Paul").setStyle(Style.Edge.invis).setDir(Dir.both).setWeight(0.5));
g.addEdge(new Edge("2_2", "Maria").setStyle(Style.Edge.invis).setDir(Dir.both).setWeight(0.5));
g.addEdge(new Edge("3_2", "Peter").setStyle(Style.Edge.invis).setDir(Dir.both).setWeight(0.5));
g.addEdge(new Edge("4_2", "Otto").setStyle(Style.Edge.invis).setDir(Dir.both).setWeight(0.5));
g.addEdge(new Edge("1_2", "temp").setStyle(Style.Edge.invis));
g.addEdge(new Edge("4_2", "temp").setStyle(Style.Edge.invis));
for (DNode n : a) {
if (n.prev != null) {
g.addEdge(new Edge(n.index + "_1", n.prev.index + "_2").setWeight(0));
}
g.addEdge(new Edge(n.index + "_2", n.obj).setWeight(0));
if (n.next != null) {
g.addEdge(new Edge(n.index + "_3", n.next.index + "_2").setWeight(0));
}
}
try {
Files.writeString(Path.of("my-graph-ag.dot"), g.toDot());
Desktop.getDesktop().browse(URI.create("https://dreampuf.github.io/GraphvizOnline/#" + URLEncoder.encode(g.toDot(), StandardCharsets.UTF_8).replace("+", "%20")));
} catch (IOException e) {
e.printStackTrace();
}
}
public void listAlgorithm(DNode head) {
print(0);
DNode t = head.next.next;
print(1);
t.next.obj = head.obj;
print(2);
head.obj = t.obj;
print(3);
t.obj = t.prev.obj;
print(4);
t.prev = head;
print(5);
head.next = t.next;
print(6);
t.prev.next.next = t;
print(7);
showGraph();
}
public static void main(String[] args) {
DList dList = new DList();
dList.listAlgorithm(dList.head);
}
}