Fragen zu generischer doppelt verketteter Liste (bei fehlendem Grundverständnis)

[jens.ru]

Ahoi. Wir sollen dieses Mal eine generische doppelt verkettete Liste programmieren. Nur leider fehlt mir (trotz intensivem googlen, recherchieren und wälzen der Unterlagen) noch immer das nötige Grundverständnis. Wir haben ein Interface gestellt bekommen und sollen damit eine Klasse programmieren, welche für die Verwaltung/Erstellung von Einträgen dieser Liste zuständig ist. Den aktuellen Code habe ich beigefügt.

import java.util.*;

public class AuDSequentialQueue<ElementType extends Comparable<ElementType>> implements AuDQueue {
	// Unterschied zwischen ElementType und Comparable? Wo wird was verwendet?
	protected Comparable head;
	protected Comparable tail;
	protected int size;

	public static void main(String args[]) {
		AuDSequentialQueue schlange = new AuDSequentialQueue();
		System.out.println(schlange.isEmpty());
		schlange.enqueue("a");
		System.out.println(schlange.isEmpty());
	}

	public AuDSequentialQueue() {
		head = null;
		tail = null;
		size = 0;
	}

	public boolean isEmpty() {
		return (size == 0);
	}

	public int size() {
		return size;
	}

	public void clear() {
		head = null;
		tail = null;
		size = 0;
	}

	public boolean exists(Comparable element) {
		return false;
	}

	public boolean exists(Comparable[] elements) {
		return false;
	}

	public Comparable getHead() throws NoSuchElementException {
		return head;
	}

	public Comparable getTail() throws NoSuchElementException {
		return tail;
	}

	public void enqueue(Comparable element) {
		Comparable elem = this.head;

		while (elem != null) {
			elem = ((ListNode<ElementType>) elem).getNext();
		}
		elem.setNext(new ListNode<ElementType>(element));
		element.setNext(null);
		size++;
	}

	public void enqueue(Comparable[] elements) {

	}

	public Comparable dequeue() throws NoSuchElementException {
		size--;
		return null;
	}

	public void moveElementsFrom(AuDQueue other) {

	}

	public String toString() {
		return null;
	}

	// ////////////////////// Innere Klasse für Listeneinträge
	protected class ListNode<ElementType extends Comparable<ElementType>> {
		protected Comparable data;
		protected Comparable next;
		protected Comparable prev;

		public ListNode(Comparable data) {
			this.data = data;
			this.next = null;
			this.prev = null;
		}

		public void setNext(Comparable next) {
			this.next = next;
		}

		public void setPrev(Comparable prev) {
			this.prev = prev;
		}

		public Comparable getNext() {
			return next;
		}

		public Comparable getPrev() {
			return prev;
		}

		public Comparable getData() {
			return data;
		}
	}

}

Nun weiß ich nicht so recht, was es mit diesem extends Comparable von ElementType auf sich hat?
Im Interface steht als Parameter überall ElementType, ich habe Eclipse automatisch die ganzen Methoden übernehmen lassen, dann steht in der Klasse auf einmal Comparable?
Comparable heißt irgendwie nur, dass man nur Objekte erzeugen kann, die man miteinander vergleichen kann, habe ich irgendwie aus diversen Google Einträgen herausgelesen? Nun habe ich überall als Parameter Comparable eingetragen und trotzdem bring Eclipse mir bei der Methode enqueue die Fehlermeldung

The method setNext(AuDSequentialQueue<ElementType>.ListNode<ElementType>) is undefined for the type Comparable

Warum? Irgendwie komm ich mit diesem generischen Sch**** nicht so richtig klar. Abgabe ist am Sonntag, deswegen werde ich langsam auch ein wenig nervös 🙂

Danke schon im Voraus recht herzlich für Antworten aller Art.

P.s. Ja. ListNode muss eine innere Klasse sein.

 

[Flown]

Weil du nicht immer alles automatisch erzeugen lassen sollst. Eine einfache LinkedList hier:

import java.util.NoSuchElementException;

public class LinkedList<T extends Comparable<T>> implements MyQueue<T> {
  
  private ListNode head, tail;
  private int size;
  
  public LinkedList() {
    clear();
  }
  
  @Override
  public boolean isEmpty() {
    return size == 0;
  }
  
  @Override
  public int size() {
    return size;
  }
  
  @Override
  public void clear() {
    head = null;
    tail = null;
    size = 0;
  }
  
  @Override
  public boolean exists(T element) {
    for (ListNode node = head; node != null; node = node.next) {
      if (element == null ? element == node.data : element.compareTo(node.data) == 0) {
        return true;
      }
    }
    return false;
  }
  
  @Override
  public T getHead() throws NoSuchElementException {
    if (isEmpty()) {
      throw new NoSuchElementException("list is empty");
    }
    return head.data;
  }
  
  @Override
  public T getTail() throws NoSuchElementException {
    if (isEmpty()) {
      throw new NoSuchElementException("list is empty");
    }
    return tail.data;
  }
  
  @Override
  public void enqueue(T element) {
    if (isEmpty()) {
      head = tail = new ListNode(element, null);
    } else {
      tail.next = new ListNode(element, null);
      tail = tail.next;
    }
    size++;
  }
  
  @Override
  public void enqueue(T[] elements) {
    for (T element : elements) {
      enqueue(element);
    }
  }
  
  @Override
  public T dequeue() throws NoSuchElementException {
    if (isEmpty()) {
      throw new NoSuchElementException("list is empty");
    }
    T elem = head.data;
    if (head == tail) {
      head = tail = null;
    } else {
      head = head.next;
    }
    size--;
    return elem;
  }
  
  @Override
  public void moveElementsFrom(MyQueue<T> other) {
    while (!other.isEmpty()) {
      enqueue(other.dequeue());
    }
  }
  
  private class ListNode {
    public T data;
    public ListNode next;
    
    public ListNode(T data, ListNode next) {
      this.data = data;
      this.next = next;
    }
  }
  
  public static void main(String... args) {
    LinkedList<Integer> list = new LinkedList<>();
    System.out.println(list.size());
    list.enqueue(1);
    System.out.println(list.size());
    System.out.println(list.dequeue());
    System.out.println(list.size());
  }
  
}

interface MyQueue<T> {
  boolean isEmpty();
  
  int size();
  
  void clear();
  
  boolean exists(T element);
  
  T getHead() throws NoSuchElementException;
  
  T getTail() throws NoSuchElementException;
  
  void enqueue(T element);
  
  void enqueue(T[] elements);
  
  T dequeue() throws NoSuchElementException;
  
  void moveElementsFrom(MyQueue<T> other);
}