Двусвязный список с общим типом узла

Question

Мне нужен двусвязный список, который может работать на разных реализациях узлов. Обратите внимание, что я не хочу узлы, которые содержат общие данные, такие как DoublyLinkedNode<T>, но что-то вроде DoublyLinkedList<N extends DoublyLinkedNode<T>>.

Если быть точным, я использую список в общем случае со стандартными узлами, но в других частях моей программы мне нужны узлы с дополнительными полями. Так что я реализовал общий узел как

public class DoublyLinkedNode<T> {
    DoublyLinkedNode<T> before, after;
    T value;
}

и специальный тип как

public class DoublyLinkedSpecialNode<T, S> extends DoublyLinkedNode<T> {
    S specialValue;
}

Теперь в моей реализации DoublyLinkedList я хочу иметь возможность обрабатывать оба случая одновременно, потому что весь код в основном работает с указателями, которые, очевидно, являются общими для обеих реализаций.

Это дает несколько требований:

1) Когда я использую специальный узел, я хочу иметь возможность вернуть его как тип DoublyLinkedSpecialNode, чтобы иметь доступ к дополнительным полям.

2) В списке должен использоваться тип DoublyLinkedNode для доступа к указателям узлов.

3) Список назначает узлы-указатели другим узлам, например, head = node.after;, поэтому тип указателей в специальном узле должен совпадать с типом в списке.

Расширение списка не имеет смысла, потому что тогда я не мог изменить тип возврата методов. Поэтому я безуспешно попробовал две идеи:

Уже упомянутое решение: общий тип узла, который расширяется от DLN

Список будет выглядеть так:

public class DoublyLinkedList<T, N extends DoublyLinkedNode<T>> {
    N head, tail;
    N tail() {
        return tail; // OK
    }
    void remove(N node) {
        if (head == node) {
            head = node.after; // Type error
        }
...

Это решение противоречит требованию 3), поскольку в списке тип представляет собой N, который простирается от DLN, но в реализации узла N указатель имеет тип базового класса / интерфейса DLN (тип указателя теоретически может быть быть более общим, чем N).

Базовый DLN вместо генериков

В этом случае список работает на узле базового класса и принимает подклассы из-за полиморфизма:

public class DoublyLinkedList<T> {
    DoublyLinkedNode<T> head, tail;
    DoublyLinkedNode<T> tail() {
        return tail; 
    }
    void remove(DoublyLinkedNode<T> node) {
        if (head == node) {
            head = node.after; // OK
        }
...

Но tail () может возвращать только узлы как общий тип, конфликтуя с 1). Я бы предпочел не использовать приведение, потому что я предполагаю, что это плохая практика (?), Но также и потому, что реализация критична к производительности. Там наверняка есть лучший способ?

Answer 1

Я нашел другое решение, которое хорошо, не очень производительно, но более элегантно, чем последнее решение.

Идея состоит в том, чтобы использовать только один тип узлов и помещать различное содержимое в общий контейнер. Код DLN выглядит следующим образом:

public class DoublyLinkedNode<C> {
    DoublyLinkedNode<C> before, after;
    C content;

    public static class ValueContent<T> {
        T value;
    }

    public static class ValueSpecialContent<T, S> extends ValueContent<T> {
        S specialValue;
    }
}

Реализация списка выглядит примерно так:

public class DoublyLinkedList<C> {
    DoublyLinkedNode<C> head, tail;

    public DoublyLinkedNode<C> head() {
        return head;
    }

    void remove(DoublyLinkedNode<C> node) {
        if (head == node) {
            head = node.after;
...

И я могу получить доступ к специальному полю из вызывающего класса следующим образом:

DoublyLinkedList<SpecialContent<SpecialType>> list;
SpecialType s = list.head().content.specialValue;

Существуют некоторые накладные расходы, потому что каждый узел должен создавать экземпляр этого класса контейнера, но я думаю, что это все же лучше, чем приведение. Я должен проверить влияние на производительность.