Реализовать IList<T> без использования массивов и списков

@kv4sha · Регистрация: 09.06.2014

Студворк — интернет-сервис помощи студентам

Нужно реализовать IList<T> без использования массивов и списков. Искал где только мог, конкретного примера реализации не нашёл, киньте ссылку пожалуйста.

@insite2012 · 02.05.2015, 18:40

Сообщение от kv4sha

реализовать IList<T> без использования массивов и списков.

Это как? Где вы предполагаете хранить элементы?

@kv4sha · 02.05.2015, 18:45 **[ТС]**

Как реализация списка на C++ в отдельной структуре или классе
Вот например так, только нужно чтобы класс List<T> реализовывал IList<T>, а примера такого я найти не могу.
Лаба в универе.

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class Node<V>
    {
        private Node<V> next;
        private V element;
 
        public void SetNextNode(Node<V> _nextNode)
        {
            this.next = _nextNode;
        }
 
        public V Element
        {
            get { return this.element; }
            set { this.element = value; }
        }
 
        public Node<V> Next
        {
            get { return this.next; }
        }
    }
 
    class List<T>
    {
        public int Length { get; private set; }
        private Node<T> headNode;
        private Node<T> tailNode;
 
        public List()
        {
            // создание пустого списка
            this.headNode = null;
            this.tailNode = this.headNode;
            this.Length = 0;
        }
 
        public void Push(T element)
        {
            if (headNode == null)
            {
                // создать узел, сделать его головным
                this.headNode = new Node<T>();
                this.headNode.Element = element;
                // этот же узел и является хвостовым
                this.tailNode = this.headNode;
                // следующего узла нет
                this.headNode.SetNextNode(null);
            }
            else
            {
                // создать временный узел
                Node<T> newNode = new Node<T>();
                // следующий за предыдущим хвостовым узлом - это наш временный новый узел
                this.tailNode.SetNextNode(newNode);
                // сделать его же новым хвостовым
                this.tailNode = newNode;
                this.tailNode.Element = element;
                // следующего узла пока нет
                this.tailNode.SetNextNode(null);
            }
 
            ++this.Length;
        }
 
        public void printList(int position)
        {
            Node<T> tempNode = headNode;
            if(position == -1)
            {
                for(int i = 0; i < Length; i++)
                {
                    Console.Write(tempNode.Element);
                    tempNode = tempNode.Next;
                }
            }
            else
            {
                for (int i = 0; i < position; i++)
                    tempNode = tempNode.Next;
                Console.Write(tempNode.Element);
            }
            Console.WriteLine();
        }
 
        //public int this[int _position]
        //{
        //    get
        //    {
        //        // дабы не загромождать пример, 
        //        // опустим проверку на валидность переданного параметра '_position'
        //        Node tempNode = this.headNode;
        //        for (int i = 0; i < _position; ++i)
        //        {
        //            // переходим к следующему узлу списка
        //            tempNode = tempNode.Next;
        //            //Console.WriteLine(tempNode.Element);
        //        }
        //        return tempNode.Element;
        //    }
        //}
    }

@kypiwindy · 02.05.2015, 19:58

kv4sha, а какая сигнатура этого интерфейса?

Сообщение от kv4sha

IList<T>

@kv4sha · 02.05.2015, 20:00 **[ТС]**

kypiwindy, вы имеете ввиду методы которые нужно реализовывать?

@kypiwindy · 02.05.2015, 20:07

kv4sha, да. Стандартный Ilist из System.Collection или свой?

@OwenGlendower · 02.05.2015, 20:09

kv4sha, в чем именно трудность? Измени объявление класса List<T> так чтобы он реализовывал IList<T> и начни реализовывать методы по очереди. Те методы которые пока не знаешь как реализовать оставляй пустыми или делай throw new NotImplementedException().

@kv4sha · 02.05.2015, 20:59 **[ТС]**

kypiwindy, стандартный.

Добавлено через 2 минуты
OwenGlendower, вот пока примерная реализация, не могу понять как достать энумератор.

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
class Node<V>
    {
        private Node<V> next;
        private V element;
 
        public void SetNextNode(Node<V> _nextNode)
        {
            this.next = _nextNode;
        }
 
        public V Element
        {
            get { return this.element; }
            set { this.element = value; }
        }
 
        public Node<V> Next
        {
            get { return this.next; }
        }
    }
 
 
 
    /// ///////////////////////////////////////////
    class Gen<T> : IList<T>
    {
        public int Count
        {
            get;
            private set;
        }
 
        private Node<T> headNode;
        private Node<T> tailNode;
 
        public T this[int index]
        {
            get
            {
                if (Count > index)
                {
                    Node<T> tempNode = this.headNode;
                    for (int i = 0; i < index; ++i)
                    {
                        // переходим к следующему узлу списка
                        tempNode = tempNode.Next;
                    }
                    return tempNode.Element;
                }
                else
                    throw new IndexOutOfRangeException();
            }
            set
            {
                Node<T> tempNode = this.headNode;
                int i = 0;
                if (Count > index)
                {
                    while (i != index)
                    {
                        // переходим к следующему узлу списка
                        tempNode = tempNode.Next;
                        i++;
                    }
 
                    tempNode.Element = value;
                }
                else
                    throw new IndexOutOfRangeException();
            }
 
        }
 
        public bool IsReadOnly
        {
            get
            {
                return false;
            }
        }
 
        public void Add(T item)
        {
            if (headNode == null)
            {
                // создать узел, сделать его головным
                this.headNode = new Node<T>();
                this.headNode.Element = item;
                // этот же узел и является хвостовым
                this.tailNode = this.headNode;
                // следующего узла нет
                this.headNode.SetNextNode(null);
            }
            else
            {
                // создать временный узел
                Node<T> newNode = new Node<T>();
                // следующий за предыдущим хвостовым узлом - это наш временный новый узел
                this.tailNode.SetNextNode(newNode);
                // сделать его же новым хвостовым
                this.tailNode = newNode;
                this.tailNode.Element = item;
                // следующего узла пока нет
                this.tailNode.SetNextNode(null);
            }
 
            ++this.Count;
        }
 
        public void Clear()
        {
            headNode = null;
            tailNode = null;
            Count = 0;
        }//чуть неверно
 
        public bool Contains(T item)
        {
            Node<T> tempNode = headNode;
            if (headNode == null)
                return false;
            else
            {
                for (int i = 0; i < Count; i++)
                {
                    if (tempNode.Element.Equals(item))
                        return true;
                    else
                    {
                        tempNode = tempNode.Next;
                    }
                }
                return false;
            }
        }
 
        public void CopyTo(T[] array, int arrayIndex)
        {
            int y = 0;
            Node<T> tempNode = headNode;
 
            for (int i = 0; i < arrayIndex; ++i)
            {
                // переходим к следующему узлу списка
                tempNode = tempNode.Next;
            }
            for (int i = arrayIndex; i < Count; ++i)
            {
                array[y] = tempNode.Element;
                tempNode = tempNode.Next;
                y++;
            }
        }
 
        public int IndexOf(T item)
        {
            Node<T> tempNode = headNode;
            if (headNode == null)
                return -1;
            else
            {
                for (int i = 0; i < Count; i++)
                {
                    if (tempNode.Element.Equals(item))
                        return i;
                    else
                    {
                        tempNode = tempNode.Next;
                    }
                }
                return -1;
            }
        }
 
        public void Insert(int index, T item)
        {
            Node<T> tempNode = headNode;
            Node<T> newNode = new Node<T>();
 
            for (int i = 0; i < index - 1; ++i)
            {
                // переходим к следующему узлу списка
                tempNode = tempNode.Next;
            }
 
            newNode.Element = item;
            newNode.SetNextNode(tempNode.Next);
 
            tempNode.SetNextNode(newNode);
            Count++;
        }
 
        public bool Remove(T item)
        {
            Node<T> tempNode = headNode;
 
            for (int i = 0; i < Count; ++i)
            {
                if (i == IndexOf(item) - 1)
                {
                    tempNode.SetNextNode(tempNode.Next.Next);
                    Count--;
                    return true;
                }
                else
                    // переходим к следующему узлу списка
                    tempNode = tempNode.Next;
            }
            return false;
        }
 
        public void RemoveAt(int index)
        {
            Node<T> tempNode = headNode;
 
            for (int i = 0; i < index - 1; ++i)
            {
                // переходим к следующему узлу списка
                tempNode = tempNode.Next;
            }
            tempNode.SetNextNode(null);
            Count = index;
        }
 
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
 
        public IEnumerator<T> GetEnumerator()
        {
            return 
        }
    }

@Vigelforts · 02.05.2015, 21:15

Энумератор это класс представляющий собой итератор.Его надо писать самому

@OwenGlendower · 02.05.2015, 21:23

kv4sha, обычно это решается созданием вложенного класса который реализует IEnumerator<T>. Там всего два метода Reset/MoveNext и свойство Current. Можно передать конструктору головной элемент и затем в MoveNext переходить к следующему если он есть.

@kv4sha · 02.05.2015, 21:51 **[ТС]**

OwenGlendower, написал вложенный класс всё работает, только не могу понять что это за метод

C#
1
2
3
4
5
6
7
object IEnumerator.Current
            {
                get
                {
                    throw new NotImplementedException();
                }
            }

Полный код вложенного класса

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class ListEnumerator<S> : IEnumerator<S>
        {
            Node<S> head;
            Node<S> currentObj;
 
            int position = 0;
 
            public S Current
            {
                get
                {
                    return currentObj.Element;
                }
            }
 
            object IEnumerator.Current
            {
                get
                {
                    throw new NotImplementedException();
                }
            }
 
            public void Dispose()
            {
                position = 0;
                currentObj = head;
            }
 
            public bool MoveNext()
            {
                if (currentObj.Next != null)
                {
                    if (position > 0)
                    {
                        currentObj = currentObj.Next;
                        position++;
                        return true;
                    }
                    else
                    {
                        position++;
                        return true;
                    }
                }
                else
                    return false;
            }
 
            public void Reset()
            {
                currentObj = head;
            }
 
            public ListEnumerator(Node<S> head)
            {
                this.head = head;
                currentObj = head;
            }
 
        }

@insite2012 · 02.05.2015, 21:56

Сообщение от kv4sha

не могу понять что это за метод

Это свойство, которое возвращает текущий элемент.

@kv4sha · 02.05.2015, 21:57 **[ТС]**

insite2012, там ведь есть такое, они полностью должны быть идентичны?

@insite2012 · 02.05.2015, 22:04

kv4sha, вы используете Generic интерфейс, он наследует обычный и естественно, при реализации должны быть реализованы все методы - и обобщенного интерфейса, и не обобщенного.
https://msdn.microsoft.com/ru-... .110).aspx

@OwenGlendower · 02.05.2015, 23:31

kv4sha, ты неправильно реализовал интерфейс IEnumerator<T>. Цитата из документации:

Initially, the enumerator is positioned before the first element in the collection. At this position, Current is undefined. Therefore, you must call MoveNext to advance the enumerator to the first element of the collection before reading the value of Current.

То есть начальная позиция неправильно реализована. Второй недочет - реализация Dispose(). Он должен освобождать ресурсы. В данном случае освобождать нечего, но имеет смысл присвоить null полям head и currentObj.

Исправленная реализация IEnumerator

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class ListEnumerator<S> : IEnumerator<S>
{
    Node<S> head;
    Node<S> currentObj;
 
    public S Current { get { return currentObj.Element; } }
    object IEnumerator.Current { get { return currentObj.Element; } }
 
    public ListEnumerator(Node<S> head)
    {
        this.head = head;
    }
    
    public bool MoveNext()
    {
        currentObj = currentObj == null ? head : currentObj.Next;
        return currentObj != null;
    }
 
    public void Reset()
    {
        currentObj = null;
    }
 
    public void Dispose()
    {
        head = null;
        currentObj = null;
    }
}

Данная реализация тоже неполная. Надо еще добавить проверки не изменилась ли коллекция с момента предыдущего вызова MoveNext. И если да, то генерировать InvalidOperationException.

@kv4sha · 02.05.2015, 23:47 **[ТС]**

OwenGlendower, спасибо.

Psilon · 03.05.2015, 10:03

достаточно использовать yield return и не мучиться с ручной реализацией итераторов...

Добавлено через 15 минут
Я это вижу примерно так:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
    class MyList<T> : IList<T>
    {
        class Node
        {
            public T Value { get; set; }
            public Node Next { get; set; }
        }
 
        private Node Head, Tail;
 
        private Node FindNode(T value)
        {
            for (Node node = Head; node != Tail; node = node.Next)
                if (node.Next != null && Equals(node.Next.Value, value))
                    return node;
            return null;
        }
 
        private IEnumerable<Node> GetAllNodex()
        {
            for (Node node = Head; node != null; node = node.Next)
                yield return node;
        } 
 
        public IEnumerator<T> GetEnumerator()
        {
            return GetAllNodex().Select(x => x.Value).GetEnumerator();
        }
 
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
 
        public void Add(T item)
        {
            var newNode = new Node() { Value = item };
            if (Head == null)
            {
                Head = Tail = newNode;
            }
            else
            {
                Tail.Next = newNode;
                Tail = newNode;
            }
            Count++;
        }
 
        public void Clear()
        {
            Head = Tail = null;
            Count = 0;
        }
 
        public bool Contains(T item)
        {
            return Enumerable.Contains(this, item);
        }
 
        public void CopyTo(T[] array, int arrayIndex)
        {
            if (arrayIndex + Count > array.Length)
                throw new IndexOutOfRangeException();
            int i = arrayIndex;
            foreach (T value in this)
            {
                array[i++] = value;
            }
        }
 
        public bool Remove(T item)
        {
            var node = FindNode(item);
            if (node == null)
                return false;
            node.Next = node.Next.Next;
            Count--;
            return true;
        }
 
        public int Count { get; private set; }
 
        public bool IsReadOnly { get { return false; } }
 
        public int IndexOf(T item)
        {
            int i = 0;
            foreach (T value in this)
            {
                if (Equals(value, item))
                    return i;
                i++;
            }
            return -1;
        }
 
        public void Insert(int index, T item)
        {
            throw new NotImplementedException();
        }
 
        public void RemoveAt(int index)
        {
            throw new NotImplementedException();
        }
 
        public T this[int index]
        {
            get { throw new NotImplementedException(); }
            set { throw new NotImplementedException(); }
        }
    }

@kv4sha · 03.05.2015, 16:16 **[ТС]**

Всем спасибо!)

Новые блоги и статьи Все статьи Все блоги /
Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .

@kv4sha 26 / 26 / 14 Регистрация: 09.06.2014 Сообщений: 162

	Реализовать IList<T> без использования массивов и списков 02.05.2015, 18:34. Показов 3483. Ответов 17 Метки нет (Все метки) Нужно реализовать IList<T> без использования массивов и списков. Искал где только мог, конкретного примера реализации не нашёл, киньте ссылку пожалуйста. 0

@kv4sha 26 / 26 / 14 Регистрация: 09.06.2014 Сообщений: 162
	02.05.2015, 20:00 [ТС]
	kypiwindy, вы имеете ввиду методы которые нужно реализовывать? 0

@kypiwindy 418 / 316 / 241 Регистрация: 29.05.2010 Сообщений: 796 Записей в блоге: 1
	02.05.2015, 20:07
	kv4sha, да. Стандартный Ilist из System.Collection или свой? 0

@OwenGlendower Администратор 18298 / 14222 / 5368 Регистрация: 17.03.2014 Сообщений: 28,900 Записей в блоге: 1
	02.05.2015, 20:09
	kv4sha, в чем именно трудность? Измени объявление класса List<T> так чтобы он реализовывал IList<T> и начни реализовывать методы по очереди. Те методы которые пока не знаешь как реализовать оставляй пустыми или делай throw new NotImplementedException(). 0

@Vigelforts 141 / 117 / 26 Регистрация: 07.12.2014 Сообщений: 371
	02.05.2015, 21:15
	Энумератор это класс представляющий собой итератор.Его надо писать самому 0

@OwenGlendower Администратор 18298 / 14222 / 5368 Регистрация: 17.03.2014 Сообщений: 28,900 Записей в блоге: 1
	02.05.2015, 21:23
	Сообщение было отмечено kv4sha как решение Решение kv4sha, обычно это решается созданием вложенного класса который реализует IEnumerator<T>. Там всего два метода Reset/MoveNext и свойство Current. Можно передать конструктору головной элемент и затем в MoveNext переходить к следующему если он есть. 1

@kv4sha 26 / 26 / 14 Регистрация: 09.06.2014 Сообщений: 162
	02.05.2015, 21:57 [ТС]
	insite2012, там ведь есть такое, они полностью должны быть идентичны? 0

@insite2012 5548 / 4311 / 1218 Регистрация: 12.10.2013 Сообщений: 12,371 Записей в блоге: 2
	02.05.2015, 22:04
	kv4sha, вы используете Generic интерфейс, он наследует обычный и естественно, при реализации должны быть реализованы все методы - и обобщенного интерфейса, и не обобщенного. https://msdn.microsoft.com/ru-... .110).aspx 0

@kv4sha 26 / 26 / 14 Регистрация: 09.06.2014 Сообщений: 162
	02.05.2015, 23:47 [ТС]
	OwenGlendower, спасибо. 0

@kv4sha 26 / 26 / 14 Регистрация: 09.06.2014 Сообщений: 162
	03.05.2015, 16:16 [ТС]
	Всем спасибо!) 0

Реализовать IList<T> без использования массивов и списков

Решение