Добрый день.

Посоветуйте, пожалуйста, со структурой классов.

Необходимо реализовать двусторонний связный список.
Первое что набросал имело примерно такой вид:

   // элемент списка
   class Element {  
            private:
              данные класса;
            public:
               Element Дай элемент перед тобой();
               Element Дай элемент позади тебя();
        }
        
        // сам список
        class List {
            private:
              array (or list) (or container) elements;
            public:
              addElement(Element);
              removeElement(Element);
              Element getElement(someId);
         }

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

Однако глядя на эту структуру классов у меня возник вопрос, а нужен ли класс List?
Операцию removeElement(Element) можно легко перенести в класс Element (Element.removeMe()).
getElement() тоже переносится в Element и реализуется рекурсией (если ты не тот элемен, который мне нужен, то дай мне элемент следующий за тобой и спроси у него не он ли мне нужен). Тут главное не зациклиться бегая по списку.
AddElement() при переносе в Element будет выглядеть не соль изящно — сначала надо добежать до нужного элемена..... а хотя ... то же самое.

В общем вопрос — какая структура лучше — первая(Element + List) или вторая(где я все солью в один класс Element)? И почему?

IMHO — во втором случае реализация классов более естественна, с другой стороны пользователям этих классов надо вникать в смысл искуственного класса List.

Здравствуйте, DemAS, Вы писали:

Класс Element вовсе без надобности, а идея с его гиперумностью просто забавна. Обычно коллекция реализуется в виде обобщенного класса Collection<T>, где T — тип элемента, соответственно, элементом списка может стать любой объект, который о списке не имеет никакого понятия.

R>Класс Element вовсе без надобности, а идея с его гиперумностью просто забавна. Обычно коллекция реализуется в виде обобщенного класса Collection<T>, где T — тип элемента, соответственно, элементом списка может стать любой объект, который о списке не имеет никакого понятия.

Честно говоря не понял, а в чем различие с моим первоначальным вариантом?
Collection<T> — это мой List. Произвольный элемент списка в моем случае — экземпляр класса Element.

Здравствуйте, DemAS, Вы писали:

DAS>Честно говоря не понял, а в чем различие с моим первоначальным вариантом?
В том, что вот это:
DAS>Произвольный элемент списка в моем случае — экземпляр класса Element.
для вашего случае неверно.

Здравствуйте, rsn81, Вы писали:

DAS>>Произвольный элемент списка в моем случае — экземпляр класса Element.
R>для вашего случае неверно.

Ну, а если я напишу так:

   // сам список
        class List {
            private:
              array (or list) (or container) elements;
            public:
              addElement(<T>);
              removeElement(<T>);
              <T> getElement(someId);
         }

То будет верно?
Или ты говоришть про то, что реализациию getNext(), getPrevious нужно тоже вынести в List? Ок — разумно. Спасибо.

Здравствуйте, DemAS, Вы писали:

DAS> Необходимо реализовать двусторонний связный список.
Студент?

DAS> Первое что набросал имело примерно такой вид: [skipped]
Посмотри как в .NET Framework реализован LinkedList — как раз твой случай.
Фактически класс Element должен быть итератором (см паттерны), тогда структура будет наиболее понятной.

DAS> IMHO — во втором случае реализация классов более естественна, с другой стороны пользователям этих классов надо вникать в смысл искуственного класса List

Не думаю что посторонний человек без бутылки разберется как добавлять элемент в список, с помощью одного класса Element.

Здравствуйте, DemAS, Вы писали:

DAS>То будет верно?
Да.

DAS>Или ты говоришть про то, что реализациию getNext(), getPrevious нужно тоже вынести в List?
И это тоже, разумеется.

Здравствуйте, gandjustas, Вы писали:

G>Посмотри как в .NET Framework реализован LinkedList — как раз твой случай.
G>Фактически класс Element должен быть итератором (см паттерны), тогда структура будет наиболее понятной.
Почему класс Element? Класс LinkedList<T> реализует интерфейс IEnumerable<T>, метод GetEnumerator которого возвращает реализацию интерфейса IEnumerable (а там всего ничего, 3 метода MoveNext, Reset и Current).

Здравствуйте, rsn81, Вы писали:

R>Здравствуйте, DemAS, Вы писали:

DAS>>То будет верно?
R>Да.

ОК. Проблема в том, что язык шаблоны не поддерживает. Хотя можно ввести некого общего предка, которого и указать в List.

Здравствуйте, DemAS, Вы писали:

array и list — разные по семантике классы. В случае list — быстрое вставка/добавление элементов, в случае array быстрый индексный доступ.

Здравствуйте, DemAS, Вы писали:

DAS>ОК. Проблема в том, что язык шаблоны не поддерживает. Хотя можно ввести некого общего предка, которого и указать в List.
А какой язык, разве не C++?

Здравствуйте, rsn81, Вы писали:

DAS>>ОК. Проблема в том, что язык шаблоны не поддерживает. Хотя можно ввести некого общего предка, которого и указать в List.
R>А какой язык, разве не C++?

Нет, это я схематически структуру классов описал. Язык разработки — внутренний, самописный.

Здравствуйте, DemAS, Вы писали:
DAS> ОК. Проблема в том, что язык шаблоны не поддерживает. Хотя можно ввести некого общего предка, которого и указать в List.
Всегда думал, что впервую очередь шаблоны поддерживаются в голове разработчика программы, а не в языке программирования.

Здравствуйте, LeonidV, Вы писали:

LV>Всегда думал, что впервую очередь шаблоны поддерживаются в голове разработчика программы, а не в языке программирования.

Они там могут поддерживаться, но если язык не поддерживает объекто-ориентированную парадишму программирования — то они там и останутся.

Здравствуйте, DemAS, Вы писали:

DAS> Необходимо реализовать двусторонний связный список.

DAS> В общем вопрос — какая структура лучше — первая(Element + List) или вторая(где я все солью в один класс Element)? И почему?

По принципам объектно-ориентированного программирования пользователь не должен знать, как работает класс. Поэтому первый вариант сразу отпадает. Второй вариант тоже не пойдет, потому что пользователь желает "список значений" и дать ему нужно список значений без понятия "элемент". Т.е. пользователь должен оперировать всего двумя словами "список" и "значение". Больше в руки ему ничего давать нельзя, а то наломает дров .

Набросал вот кусочек кода. Третий вариант.

Пардон, но на с++ .

template <class T>
class MyList
{
private:
    struct Node
    {
        T        Value;
        Node*    Next;
        Node*    Prev;
    };
    ...
    public:
    T*        GetItem();
    bool    Is();
    void    Next();
    void    Prev();
    void    Begin();
    bool    Insert(T);
    bool    Insert(int pos, T);
    bool    Erase(T);
};

// Using
MyList<int>    List;
List.Insert(10);
List.Insert(20);
List.Insert(30);
List.Insert(40);

if(List.Erase(40))
    MessageBox(0, L"Item removed",0,0);
else
    MessageBox(0, L"Item not found",0,0);

List.Begin();
while(List.Is())
{
    int Value = *List.GetItem();
    // Делаем что-нибудь с Value
    List.Next();
}

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

Здравствуйте, LeonidV, Вы писали:

DAS>> ОК. Проблема в том, что язык шаблоны не поддерживает. Хотя можно ввести некого общего предка, которого и указать в List.
LV>Всегда думал, что впервую очередь шаблоны поддерживаются в голове разработчика программы, а не в языке программирования.

Шаблоны тут имеются в виду те, что в C++ templates, а в .NET generics. Поддерживать их в голове, конечно же, возможно, но чревато ошибками времени выполнения. Поэтому наличие их поддержки в компиляторе очень существенно разгружает голову для других задач.

JavaScript, например, "на ура" обходится без "шаблонов", но размеры скриптового кода для какой-либо задачи и компилируемого отличаются на порядки.

Здравствуйте, NoHate, Вы писали:

NH>По принципам объектно-ориентированного программирования пользователь не должен знать, как работает класс. Поэтому первый вариант сразу отпадает. Второй вариант тоже не пойдет, потому что пользователь желает "список значений" и дать ему нужно список значений без понятия "элемент". Т.е. пользователь должен оперировать всего двумя словами "список" и "значение". Больше в руки ему ничего давать нельзя, а то наломает дров .

+1

NH>Набросал вот кусочек кода. Третий вариант.

Не очень верно в одном классе реализовывать контейнер и итератор по нему же: а что, если понадобится пораллельно обходить один и тот же контейнер? Обычно или итератор выносят наружу или делают как-то так:

NH>

class List …
{
  T* GetFirst() const;
  T* GetNext(const T* current) const;
  T* GetPrevious(const T* current) const;
};

  //…

  for(T* item = list.GetFirst(); item != NULL; item = list.GetNext(item)) {
    // Делаем что-нибудь с Value
  }//for

Здравствуйте, DemAS, Вы писали:

DAS>Добрый день.

DAS> Посоветуйте, пожалуйста, со структурой классов.

DAS> Необходимо реализовать двусторонний связный список.
Посмотрите реализацию std::list в STL — там все уже есть.