Einfügen in doppelt verkettete Liste

PhiRie

Mitglied
Hallo,

ich habe die Aufgabe bekommen: Ich soll eine Klasse DLinkedList<T> erstellen die alle Methoden der abstrakten Klasse List<T> mit einer doppelt verketten Liste implementiert. So weit so gut, das alles war keine Problem nun zu meiner Frage:

Weiterhin sollen die Operation (zB. einfügen eines neuen Elements in die Liste an bestimmte Position) gegebenenfalls vom Ende der Liste aus laufen, wenn dies günstiger ist.

Ich weiß wie ich ein neues Element vom Ende der Liste aus einfüge, das funktioniert auch wunderbar. Nur habe ich die Frage wie prüfe ich vorher ob vom Beginn oder vom Ende aus eingefügt werden soll.

Ich habe eine Variable die die Anzahl der Elemente in der Liste hochzählt, kann ich daraus einfach den Mittelwert bilden und dann schauen ob die Einfügeposition größer ist ( also vom Ende aus einfügen) oder kleiner (also vom Anfang aus einfügen) außerdem ist das ja nur sinnvoll wenn ab 3 Elementen in der Liste, oder hat jemand ne einfacher oder bessere Idee? Ich steh gerade auf dem Schlauch...

Hier mein Code:
Java:
public void add(int p, T x) {

		Node t = new Node();
		t.key = x;
		Node current;

		mitte = anzahl / 2;

		if (anzahl < 3 || p <= mitte) {

			System.out.println("Head");
			current = head;

			for (int i = 1; i < p; i++) {

				current = current.next;

				if (current == z) {

					throw new RuntimeException("ungueltiger Index p");
				}
			}

			t.next = current.next;
			current.next.prev = t;

			current.next = t;
			t.prev = current;

		} else {

			System.out.println("Back");
			current = z;

			for (int i = anzahl; i > p; i--) {

				current = current.prev;

				if (current == head) {

					throw new RuntimeException("ungueltiger Index p");
				}
			}

			t.prev = current.prev;
			t.next = current;

			current.prev.next = t;
			current.prev = t;
		}
		anzahl++;
	}
 

eRaaaa

Top Contributor
Also ich weiss ja nicht was du hier mit Mittelwert meinst, ich denke du meinst einfach die Mitte? :)
Ja, so könntest du das machen, einfach schauen ob der übergebene Index / Position kleiner als size >> 1 ist, dann vorwärts durchlaufen, ansonsten rückwärts. (size >> 1 = Mitte)
So machts btw auch die Liste aus dem JDK :D
 

PhiRie

Mitglied
Ja ich meinte damit die Mitte, also dann werd ich das wohl so beibehalten. Gibt es ne möglichkeit den Code der Liste aus dem JDK anzeigen zu lassen?
 
S

sklafdsljkjf

Gast
natürlich, google mal "Java SE 6 JDK Source Code" - aber für ungeübte wird das nicht lesbar sein.
 

PhiRie

Mitglied
OK, danke, hab auch im Java Verzeichnis eine src.zip gefunden wo wohl der ganze Sourcecode enthalten ist. Werd mir das mal anschauen. Trotzdem vielen Dank für eure schnelle Hilfe. War wirklich super

Gruß
 
S

sklafdsljkjf

Gast
jo, ausgewählte klassen befinden sich dort.

bei netbeans genügt ein alt+o.

interessant ist Methode addBefore. Diese macht grundsätzlich zwei Sachen. den Nachfolger des Vorgängers auf das neue Element setzen, und den Vorgänger des Nachfolgers auf das neue Element setzen. bringt dir aber wahrscheinlich nichts oder?
 

PhiRie

Mitglied
Nee bringt mir ja nichts da ich das ganze ja selber implementieren sollte. Aber ich habs jetzt mit einer Variable mitte gelöst. Ich werd mal den Code posten vielleicht hilfts ja noch anderen weiter:

Java:
public class DLinkedList<T> implements List<T> {

	public class Node {

		private T key;
		private Node next;
		private Node prev;
	}

	private Node head, z;
	private int anzahl;
	private int mitte; // Zur unterscheidung ob von head/z begonnen wird.

	public DLinkedList() {

		head = new Node();
		z = new Node();

		head.next = z;
		z.next = head;

		head.prev = z;
		z.prev = head;

		anzahl = 0;
		mitte = 0;
	}

	public void add(int p, T x) {

		Node t = new Node();
		t.key = x;
		Node current;

		mitte = anzahl / 2;

		if (anzahl < 3 || p <= mitte) {

			System.out.println("Head");
			current = head;

			for (int i = 1; i < p; i++) {

				current = current.next;

				if (current == z) {

					throw new RuntimeException("ungueltiger Index p");
				}
			}

			t.next = current.next;
			current.next.prev = t;

			current.next = t;
			t.prev = current;

		} else {

			System.out.println("Back");
			current = z;

			for (int i = anzahl; i > p; i--) {

				current = current.prev;

				if (current == head) {

					throw new RuntimeException("ungueltiger Index p");
				}
			}

			t.prev = current.prev;
			t.next = current;

			current.prev.next = t;
			current.prev = t;
		}
		anzahl++;
	}

	public T get(int p) {

		Node current;

		mitte = anzahl / 2;

		if (anzahl < 3 || p <= mitte) {

			current = head;

			for (int i = 1; i <= p; i++) {

				current = current.next;

				if (current == z) {

					throw new RuntimeException("ungueltiger Index p");
				}
			}

		} else {

			current = z;

			for (int i = anzahl; i >= p; i--) {

				current = current.prev;

				if (current == head) {

					throw new RuntimeException("ungueltiger Index p");
				}
			}
		}

		return current.key;

	}

	public int indexOf(T x) {

		int index = -1;
		int k = 0;

		for (Node current = head; current != z; current = current.next) {

			if (current.key == x) {

				index = k;
				break;
			}
			k++;
		}

		return index;
	}

	public boolean isEmpty() {

		return head.next == z;
	}

	public T remove(int p) {

		Node current, tmp = null;
		T key = null;

		mitte = anzahl / 2;

		if (anzahl < 3 || p <= mitte) {

			current = head;

			for (int i = 1; i < p; i++) {

				current = current.next;

				if (current == z) {

					throw new RuntimeException("ungueltiger Index p");
				}
			}

			tmp = current.next;
			current.next = current.next.next;
			current.next.next.prev = current;

		} else {

			current = z;

			for (int i = anzahl; i > p; i--) {

				current = current.prev;

				if (current == head) {

					throw new RuntimeException("ungueltiger Index p");
				}
			}

			tmp = current.prev;
			current.prev = current.prev.prev;
			current.prev.prev.next = current;

		}

		anzahl--;
		return tmp.key;

	}

	public int size() {

		return anzahl;
	}

}
 
S

sklafdsljkjf

Gast
kann mir nicht alles angucken, aber:

- was ist z ? ... die mitte?
- Exception irgendwo in der Methode ist ganz schlecht, wenn der Index nicht gültig ist, kann man das vorher prüfen
- das Verknüpfen des neuen Elements mit Vorgänger/Nachfolger kann in eienr extra Methode sein
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Y Einfügen in eine doppelt verkettete Liste Java Basics - Anfänger-Themen 8
N doppelt verkettete liste einfügen Java Basics - Anfänger-Themen 7
M Doppelt verkettete Liste Zeiger Vorgänger beim Einfügen Java Basics - Anfänger-Themen 2
G Einfügen aus Zwischenablage - alles doppelt? Java Basics - Anfänger-Themen 2
Hilde22 Neu Start JButton einfügen Java Basics - Anfänger-Themen 2
Nitrogames Variablen Variable aus JOptionPane Abfrage in Array einfügen Java Basics - Anfänger-Themen 4
melaniemueller setCharAt Leerzeichen zusätzlich einfügen Java Basics - Anfänger-Themen 8
S Algorithmus Datensätze einfügen wenn... Java Basics - Anfänger-Themen 26
E In Array Werte einfügen? Java Basics - Anfänger-Themen 5
districon Element in Liste einfügen Java Basics - Anfänger-Themen 1
Gaudimagspam Attribute einfügen private Java Basics - Anfänger-Themen 3
marcooooo Separator zwischen allen Zeichen eines Strings einfügen Java Basics - Anfänger-Themen 29
R Inventar und Items auf ein 2D ArrayFeld einfügen Java Basics - Anfänger-Themen 2
S Bild einfügen // NEU Java Basics - Anfänger-Themen 12
S Datenbank Tabelle eine Zeile an einer bestimmten Stelle einfügen Java Basics - Anfänger-Themen 2
V_Fynn03 Erste Schritte Einen Wert in ein TextField einfügen aus einer anderen Klasse Java Basics - Anfänger-Themen 3
E Datentypen Einfügen von Objekten in eine Map Java Basics - Anfänger-Themen 2
O Naives links rechts einfügen in ADT Baum Java Basics - Anfänger-Themen 8
O BinärBaum einfügen Java Basics - Anfänger-Themen 13
M Sqlite table löschen und daten einfügen Java Basics - Anfänger-Themen 5
M Erste Schritte Mit Variable verschiedene Texte in Textfeld einfügen Java Basics - Anfänger-Themen 27
M Klasse in JTable einfügen Java Basics - Anfänger-Themen 7
J In einer Klasse ein AlertDialog einfügen Java Basics - Anfänger-Themen 4
S Elemente in Liste einfügen Java Basics - Anfänger-Themen 2
S Interface (WindowBuilder) Panels in einen Frame einfügen Java Basics - Anfänger-Themen 10
x-tshainge Java Bilder einfügen Java Basics - Anfänger-Themen 1
T Variablen “ in String einfügen Java Basics - Anfänger-Themen 1
Orkanson Objekte in ein Array einfügen Java Basics - Anfänger-Themen 5
S Doppelte Liste Einfügen Java Basics - Anfänger-Themen 1
X Objekte in ArrayList einfügen Java Basics - Anfänger-Themen 10
jaleda100 JTextArea Zeile einfügen Java Basics - Anfänger-Themen 1
R Spielfeldbegrenzung einfügen (Java)? Brauche Hilfe! Java Basics - Anfänger-Themen 15
D B-Baum einfügen und löschen Java Basics - Anfänger-Themen 2
S Einfach verkettete Liste Element an bestimmter Position einfügen Java Basics - Anfänger-Themen 24
JavaNewbie2.0 Tausende Wörter in Arrays automatisch einfügen Java Basics - Anfänger-Themen 10
J Wie kann ich Images per Tastendruck anzeigen/einfügen? Java Basics - Anfänger-Themen 3
F In LinkedList einen Wert ersetzen oder neu einfügen Java Basics - Anfänger-Themen 7
C Verkettete Liste - sortiert einfügen Java Basics - Anfänger-Themen 7
J Scroll-Leiste einfügen Java Basics - Anfänger-Themen 12
U Sound einfügen Java Basics - Anfänger-Themen 6
P String zerstückeln und in Excel einfügen Java Basics - Anfänger-Themen 11
J Objecte in TreeSet einfügen klappt nicht Java Basics - Anfänger-Themen 5
P Variablen Wie kann ich eine lokale Variable in eine andere Methode einfügen? Java Basics - Anfänger-Themen 27
S Bild einfügen Java Basics - Anfänger-Themen 16
D Taschenrechnerereignisse einfügen Java Basics - Anfänger-Themen 18
B Vererbung In offener Hash Tabelle einfügen Java Basics - Anfänger-Themen 4
W Listenelement einfügen Java Basics - Anfänger-Themen 9
P OOP Eingabevariablen der Klasse Raum in der Methode addEvent ans Ende einer ArrayList einfügen Java Basics - Anfänger-Themen 3
8 Eigenes Bild in email einfügen Java Basics - Anfänger-Themen 1
D Datenbankzugriff - Leere Zeile einfügen Java Basics - Anfänger-Themen 2
GadgetSofa IOException fehlt aber wo einfügen? Java Basics - Anfänger-Themen 6
K JTable Bild einfügen Java Basics - Anfänger-Themen 1
A Objekte in eine Liste einfügen Java Basics - Anfänger-Themen 7
J Methoden Einfügen von Objekten nach Alphabet in ArrayList funktioniert nicht Java Basics - Anfänger-Themen 2
S jList --> Array einfügen und Liste löschen Java Basics - Anfänger-Themen 5
J Buchstabe (char) an zufällige Position eines Strings einfügen Java Basics - Anfänger-Themen 1
C Kalender in Applet einfügen Java Basics - Anfänger-Themen 0
M JFrame Bild einfügen Java Basics - Anfänger-Themen 3
D Bild in Frame einfügen Java Basics - Anfänger-Themen 11
F Collections Sortierung und Einfügen von Elementen Java Basics - Anfänger-Themen 1
K Erste Schritte Classe in andere Einfügen?? Java Basics - Anfänger-Themen 12
P Klasse in Klasse einfügen (arrayliste) Java Basics - Anfänger-Themen 7
F Bibliotheken einfügen ??? Java Basics - Anfänger-Themen 2
P Hintergrundbild in Swing einfügen Java Basics - Anfänger-Themen 3
T HashMap Werte einfügen, durchsuchen und auslesen Java Basics - Anfänger-Themen 17
K JTextField in ein Spiel einfügen Java Basics - Anfänger-Themen 2
Q Erste Schritte In CharArrayWriter Zeichen an Stelle einfügen Java Basics - Anfänger-Themen 4
J Daten in eine JList einfügen Java Basics - Anfänger-Themen 6
J Neue Zeile an bestimmter Stelle in Textdatei einfügen Java Basics - Anfänger-Themen 2
D Durch Button klick wert in JTextField einfügen Java Basics - Anfänger-Themen 5
J Button in extra Klasse festlegen und in anderer Klasse einfügen? Java Basics - Anfänger-Themen 3
J GUI Button Klasse in anderer Klasse einfügen Java Basics - Anfänger-Themen 3
E HILFE Projekt für die Schule--> Bilder einfügen Java Basics - Anfänger-Themen 9
D 2 Fragen: Position ändern vs. LayoutManager / Bilder einfügen im Vordergrund Java Basics - Anfänger-Themen 3
D String aus txt in label für Tabelle einfügen Java Basics - Anfänger-Themen 8
A Aktuelles Datum einfügen.. Java Basics - Anfänger-Themen 4
I fertige xml-datein in eine noch aufzubauende xml-datei einfügen Java Basics - Anfänger-Themen 4
N JTable - Zellfarben ändern, GUI-Komponenten in Zellen einfügen Java Basics - Anfänger-Themen 5
B Ordner in jar dateien einfügen Java Basics - Anfänger-Themen 4
S Erste Schritte Bluej Automatisches Einfügen von Objekten Java Basics - Anfänger-Themen 4
A String aus anderer Klasse in JTextArea einfügen Java Basics - Anfänger-Themen 7
J Bild einfügen Java Basics - Anfänger-Themen 3
S Musik einfügen funktioniert noch nicht Java Basics - Anfänger-Themen 6
K paint() mit einfügen Java Basics - Anfänger-Themen 14
A Sortiertes Einfügen in Liste Java Basics - Anfänger-Themen 2
B org.apache.commons.... Folder in Projekt einfügen Java Basics - Anfänger-Themen 6
Kenan89 String in ObjectList einfügen Java Basics - Anfänger-Themen 2
H Bilder im GUI einfügen Java Basics - Anfänger-Themen 12
A SwingX in Eclipse einfügen Java Basics - Anfänger-Themen 5
B Einfügen von Dateien Java Basics - Anfänger-Themen 10
M Java String " einfügen Problem Java Basics - Anfänger-Themen 2
M Video in ClassLoader einfügen Java Basics - Anfänger-Themen 7
S Itext und eine neue Zeile einfügen Java Basics - Anfänger-Themen 2
P JPanel in JTable einfügen Java Basics - Anfänger-Themen 23
D Werte aus Excel in Diagramm einfügen Java Basics - Anfänger-Themen 6
K Fehler beim Einfügen eines Programm Icons Java Basics - Anfänger-Themen 6
Binary.Coder Vor und nach jeder Codezeile etwas einfügen Java Basics - Anfänger-Themen 3
A Problem beim einfügen in eine Datenbank Java Basics - Anfänger-Themen 2
D Input/Output Zeilen aus txt-datei in Java-Liste einfügen Java Basics - Anfänger-Themen 9
J JPG in einem Label einfügen und anzeigen lassen Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben