Einfügen in doppelt verkettete Liste

[PhiRie]

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:

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]

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 😀

 

[PhiRie]

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?

 

[sklafdsljkjf]

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

 

[PhiRie]

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ß

 

[sklafdsljkjf]

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]

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:

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;
	}

}

 

[sklafdsljkjf]

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