Skip to content

Instantly share code, notes, and snippets.

@JohnMeyerhoff
Created April 30, 2023 23:15
Show Gist options
  • Save JohnMeyerhoff/a870b1ce94277c7462bd78a3b948f2f7 to your computer and use it in GitHub Desktop.
Save JohnMeyerhoff/a870b1ce94277c7462bd78a3b948f2f7 to your computer and use it in GitHub Desktop.
Doppelt Verkettete Liste mit Ring
import java.util.NoSuchElementException;
public class RDVL<T> { // Ring doppelt verkettete Liste
private Listenelement current; // Zeiger auf Start der Liste != first weil ein Ring keinen wirklichen Anfang
// hat
private int size = 0;
public class Listenelement {
Listenelement prev;
Listenelement next;
T data; // inhalt mit Datentyp T
public Listenelement(T data) {
this.data = data;
}
public Listenelement getNext() {
return next;
}
public Listenelement getPrev() {
return prev;
}
public T getData() {
return data;
}
}
public boolean isEmpty() { // ob Liste leer ist
return (size == 0);
}
public int size() { // gibt Größe zurück
return size;
}
public Listenelement getCurrent() {
return current;
}
public void add(T e) {
Listenelement neu = new Listenelement(e);
if (isEmpty()) { // der Ring ist leer
current = neu;
current.prev = current;
current.next = current;
} else { // der Ring hat mind. ein Element
neu.next = current;
current.prev.next = neu;
neu.prev = current.prev;
current.prev = neu;
current = neu;
}
size++;
}
/**
*
* @return gelöschtes Elements
*/
public T remove() {
if (isEmpty()) { // falls Liste leer ist
throw new NoSuchElementException();
}
T removed = current.data; // spiechern des zu löschenden ELements
if (size == 1) { // wenn nur ein Element in der Liste
current = null;
} else { // mind. 2 Elemente
// a <> entry <> c
current.next.prev = current.prev; // zeiger von a nach entry
current.prev.next = current.next; // zeiger von c nach entry
current = current.next; // c ist das neue entry
}
size--;
return removed;
}
public T element() { // gibt den Inhalt der "current" position zurück
if (isEmpty()) { // Falls es leer ist
throw new NoSuchElementException();
}
return getCurrent().getData();
}
public void next(int s) { // verschieb das aktuelle ELement um s schritte nach vorne
while (s > 0) {
current = current.next; // kein nullcheck weil es ein Ring ist
s--;
}
}
public void prev(int s) { // verschiebt das aktuelle ELement um s schritte nach hinten
while (s > 0) {
current = current.prev; // kein nullcheck weil es ein Ring ist
s--;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment