teratail
回答率
85.47%
質問するログイン新規登録
トップに関する質問Kotlinで双方向連結リストを実装したい。特にGetEnumeratorと型引数Tらへんに困ってます。

編集履歴

質問編集履歴

2

問題点とソースコードを更新した。

2020/12/02 13:16

投稿

picohead
picohead

スコア8

test CHANGED
File without changes
test CHANGED
@@ -20,468 +20,414 @@
20
20
 
21
21
  ```
22
22
 
23
- 上記でコンパイルするのですが
24
-
25
- コンパイルエラーがまだまだ多いため、
26
-
27
- エラーを抜粋し、私がわからない部分を補足します。
28
-
29
-
23
+ 一旦、上記でコンパイルが通るよう修正しました。
24
+
25
+ 新たな問題点は3点。（編集前の4点は保留）
26
+
27
+ (5)(4)とほぼ同義だが、型引数Tの指定方法がよくわからない。とりあえずAny？に変更した。
28
+
29
+ (6)NodeクラスもBidirectionalLinkedListIteratorクラスもBidirectionalLinkedListにだけ見えるようにしたいが、単純に内部クラスにしてしまうと、～IteratorクラスからNodeクラスが見えない。
30
+
31
+ (7)IteratorとかIterableの継承方法がよくわからない。
32
+
33
+
34
+
35
+ ### 該当のソースコード
36
+
37
+
38
+
39
+ ```Kotlin
40
+
41
+ //https://ufcpp.net/study/algorithm/col_blist.html
42
+
43
+
44
+
45
+ package Collections;
46
+
47
+
48
+
49
+
50
+
51
+ ///<summary>
52
+
53
+ /// 双方向連結リスト。
54
+
55
+ ///</summary>
56
+
57
+ ///<typeparam name = "T">要素の型</typeparam>
58
+
59
+ public class BidirectionalLinkedList {
60
+
61
+
62
+
63
+ //#region フィールド
64
+
65
+
66
+
67
+ public val dummy: Node;
68
+
69
+ public var count: Int;
70
+
71
+
72
+
73
+ //#endregion
74
+
75
+
76
+
77
+ //#region 初期化
78
+
79
+
80
+
81
+ public constructor() {
82
+
83
+ this.dummy = Node(null, null, null);
84
+
85
+ this.dummy.Next = this.dummy;
86
+
87
+ this.dummy.Previous = this.dummy;
88
+
89
+ this.count = 0;
90
+
91
+ }
92
+
93
+
94
+
95
+ //#endregion
96
+
97
+
98
+
99
+ //#region プロパティ
100
+
101
+
102
+
103
+ public val First: Node?
104
+
105
+ get() = this.dummy.Next;
106
+
107
+
108
+
109
+ public val Last: Node?
110
+
111
+ get() = this.dummy.Previous;
112
+
113
+
114
+
115
+ ///<summary>
116
+
117
+ /// リストの終端（末尾よりも後ろの番兵に当たるノード）。
118
+
119
+ ///</summary>
120
+
121
+ public val End: Node?
122
+
123
+ get() = this.dummy;
124
+
125
+
126
+
127
+ //#endregion
128
+
129
+
130
+
131
+ //#region 挿入・削除
132
+
133
+
134
+
135
+ ///<summary>
136
+
137
+ /// ノード n の後ろに新しい要素を追加。
138
+
139
+ ///</summary>
140
+
141
+ ///<param name = "e">新しい要素</param>
142
+
143
+ ///<param name = "n">要素の挿入位置</param>
144
+
145
+ ///<returns>新しく挿入されたノード</returns>
146
+
147
+ public fun InsertEAfterN(e: Any?, n: Node?): Node? {
148
+
149
+ val m: Node? = Node(e, n, n?.Next);
150
+
151
+ n?.Next?.Previous = m;
152
+
153
+ n?.Next = m;
154
+
155
+ this.count++;
156
+
157
+ return m;
158
+
159
+ }
160
+
161
+
162
+
163
+ ///<summary>
164
+
165
+ /// ノード n の前に新しい要素を追加。
166
+
167
+ ///</summary>
168
+
169
+ ///<param name = "e">新しい要素</param>
170
+
171
+ ///<param name = "n">要素の挿入位置</param>
172
+
173
+ ///<returns>新しく挿入されたノード</returns>
174
+
175
+ public fun InsertEBeforeN(e: Any?, n: Node?): Node? {
176
+
177
+ val m: Node? = Node(e, n?.Previous, n);
178
+
179
+ n?.Previous?.Next = m;
180
+
181
+ n?.Previous = m;
182
+
183
+ this.count++;
184
+
185
+ return m;
186
+
187
+ }
188
+
189
+
190
+
191
+ ///<summary>
192
+
193
+ /// 先頭に新しい要素を追加。
194
+
195
+ ///</summary>
196
+
197
+ ///<param name = "elem">新しい要素</param>
198
+
199
+ ///<returns>新しく挿入されたノード</returns>
200
+
201
+ public fun InsertFirst(elem: Any?): Node? {
202
+
203
+ return this.InsertEAfterN(elem, this.dummy);
204
+
205
+ }
206
+
207
+
208
+
209
+ ///<summary>
210
+
211
+ /// 末尾に新しい要素を追加。
212
+
213
+ ///</summary>
214
+
215
+ ///<param name = "elem">新しい要素</param>
216
+
217
+ ///<returns>新しく挿入されたノード</returns>
218
+
219
+ public fun InsertLast(elem: Any?): Node? {
220
+
221
+ return this.InsertEBeforeN(elem, this.dummy);
222
+
223
+ }
224
+
225
+
226
+
227
+ ///<summary>
228
+
229
+ /// ノード n 自身を削除。
230
+
231
+ ///</summary>
232
+
233
+ ///<param name = "n">要素の削除位置</param>
234
+
235
+ ///<returns>削除した要素の次のノード</returns>
236
+
237
+ public fun Erase(n: Node?): Node? {
238
+
239
+ if (n == this.dummy) {
240
+
241
+ return this.dummy;
242
+
243
+ }
244
+
245
+ n?.Previous?.Next = n?.Next;
246
+
247
+ n?.Next?.Previous = n?.Previous;
248
+
249
+ this.count--;
250
+
251
+ return n?.Next;
252
+
253
+ }
254
+
255
+
256
+
257
+ ///<summary>
258
+
259
+ /// 先頭の要素を削除。
260
+
261
+ ///</summary>
262
+
263
+ public fun EraseFirst(): Unit {
264
+
265
+ this.Erase(this.First);
266
+
267
+ }
268
+
269
+
270
+
271
+ ///<summary>
272
+
273
+ /// 末尾の要素を削除。
274
+
275
+ ///</summary>
276
+
277
+ public fun EraseLast(): Unit {
278
+
279
+ this.Erase(this.Last);
280
+
281
+ }
282
+
283
+
284
+
285
+ //#endregion
286
+
287
+
288
+
289
+ //#region IEnumerable<T>メンバ
290
+
291
+
292
+
293
+ operator fun iterator() = BidirectionalLinkedListIterator(this);
294
+
295
+
296
+
297
+ //#endregion
298
+
299
+
300
+
301
+ }
302
+
303
+
304
+
305
+ public class BidirectionalLinkedListIterator(val list: BidirectionalLinkedList) {
306
+
307
+ private var n: Node? = list.First;
308
+
309
+ fun next(): Node? {
310
+
311
+ return n?.Next;
312
+
313
+ }
314
+
315
+ fun hasNext(): Boolean {
316
+
317
+ return n != list.End;
318
+
319
+ }
320
+
321
+ }
322
+
323
+
324
+
325
+ ///<summary>
326
+
327
+ /// 連結リストのノード。
328
+
329
+ ///</summary>
330
+
331
+ public class Node {
332
+
333
+
334
+
335
+ //#region フィールド
336
+
337
+
338
+
339
+ private var value: Any?;
340
+
341
+ private var prev: Node?;
342
+
343
+ private var next: Node?;
344
+
345
+
346
+
347
+ //#endregion
348
+
349
+
350
+
351
+ //#region 初期化
352
+
353
+
354
+
355
+ internal constructor(_value: Any?, _prev: Node?, _next: Node?) {
356
+
357
+ this.value = _value;
358
+
359
+ this.prev = _prev;
360
+
361
+ this.next = _next;
362
+
363
+ }
364
+
365
+
366
+
367
+ //#endregion
368
+
369
+
370
+
371
+ //#region プロパティ
372
+
373
+
374
+
375
+ public var Value: Any?
376
+
377
+ get() = this.value;
378
+
379
+ set(value) {
380
+
381
+ this.value = value;
382
+
383
+ }
384
+
385
+
386
+
387
+ /// <summary>
388
+
389
+ /// 前のノード。
390
+
391
+ /// </summary>
392
+
393
+ var Previous: Node?
394
+
395
+ get() = this.prev;
396
+
397
+ internal set(value) {
398
+
399
+ this.prev = value;
400
+
401
+ }
402
+
403
+
404
+
405
+ /// <summary>
406
+
407
+ /// 次のノード。
408
+
409
+ /// </summary>
410
+
411
+ var Next: Node?
412
+
413
+ get() = this.next;
414
+
415
+ internal set(value) {
416
+
417
+ this.next = value;
418
+
419
+ }
420
+
421
+
422
+
423
+ //#endregion
424
+
425
+
426
+
427
+ }
30
428
 
31
429
  ```
32
430
 
33
- BidirectionalLinkedList.kt:186:20: error: expecting 'in'
34
-
35
- BidirectionalLinkedList.kt:187:4: error: 'return' is not allowed here
36
-
37
- など
38
-
39
- →(1)GetEnumerator周辺の実装方法がわからない
40
-
41
-
42
-
43
- BidirectionalLinkedList.kt:5:8: error: unresolved reference: System
44
-
45
- →(2)System.Collections.Genericのインポート方法がわからない
46
-
47
-
48
-
49
- BidirectionalLinkedList.kt:13:43: error: unresolved reference: IEnumerable
50
-
51
- →(3)上のインポートができれば解決するはず。。。
52
-
53
-
54
-
55
- BidirectionalLinkedList.kt:24:21: error: unresolved reference: T
56
-
57
- など
58
-
59
- →(4)全般的に型引数Tが参照できない
60
-
61
- ```
62
-
63
-
64
-
65
- ### 該当のソースコード
66
-
67
-
68
-
69
- 注意点として、私の好みで下記2点を変更しています。
70
-
71
- ・countを追加・削除時に計算に変更。
72
-
73
- ・Insert系関数の関数名と引数の順番を変更。
74
-
75
- ```Kotlin
76
-
77
- package Collections;
78
-
79
-
80
-
81
- import System.Collections.Generic;
82
-
83
- //import java.util.Iterator;
84
-
85
- //import java.lang.Iterable;
86
-
87
-
88
-
89
- ///<summary>
90
-
91
- /// 双方向連結リスト。
92
-
93
- ///</summary>
94
-
95
- ///<typeparam name = "T">要素の型</typeparam>
96
-
97
- public class BidirectionalLinkedList<T> : IEnumerable<T> {
98
-
99
- //public class BidirectionalLinkedList<T> : Iterator<T> {
100
-
101
-
102
-
103
- //#region 内部クラス
104
-
105
-
106
-
107
- ///<summary>
108
-
109
- /// 連結リストのノード。
110
-
111
- ///</summary>
112
-
113
- public class Node {
114
-
115
- //#region フィールド
116
-
117
-
118
-
119
- public var value: T;
120
-
121
- private var prev: Node;
122
-
123
- private var next: Node;
124
-
125
-
126
-
127
- //#endregion
128
-
129
- //#region 初期化
130
-
131
-
132
-
133
- internal constructor(_value: T, _prev: Node, _next: Node) {
134
-
135
- this.value = _value;
136
-
137
- this.prev = _prev;
138
-
139
- this.next = _next;
140
-
141
- }
142
-
143
-
144
-
145
- //#endregion
146
-
147
- //#region プロパティ
148
-
149
-
150
-
151
- public var Value: T
152
-
153
- get() = this.value;
154
-
155
- set(value) {
156
-
157
- this.value = value;
158
-
159
- }
160
-
161
-
162
-
163
- /// <summary>
164
-
165
- /// 前のノード。
166
-
167
- /// </summary>
168
-
169
- var Previous: Node
170
-
171
- public get() = this.prev;
172
-
173
- internal set(value) {
174
-
175
- this.prev = value;
176
-
177
- }
178
-
179
-
180
-
181
- /// <summary>
182
-
183
- /// 次のノード。
184
-
185
- /// </summary>
186
-
187
- var Next: Node
188
-
189
- public get() = this.next;
190
-
191
- internal set(value) {
192
-
193
- this.next = value;
194
-
195
- }
196
-
197
-
198
-
199
- //#endregion
200
-
201
- }
202
-
203
-
204
-
205
- //#endregion
206
-
207
- //#region フィールド
208
-
209
-
210
-
211
- public val dummy: Node;
212
-
213
- public var count: Int;
214
-
215
-
216
-
217
- //#endregion
218
-
219
- //#region 初期化
220
-
221
-
222
-
223
- public constructor() {
224
-
225
- this.dummy = Node(default(T), null, null);
226
-
227
- this.dummy.Next = this.dummy;
228
-
229
- this.dummy.Previous = this.dummy;
230
-
231
- this.count = 0;
232
-
233
- }
234
-
235
-
236
-
237
- //#endregion
238
-
239
- //#region プロパティ
240
-
241
-
242
-
243
- ///<summary>
244
-
245
- /// リストの先頭ノード。
246
-
247
- ///</summary>
248
-
249
- public val First: Node
250
-
251
- get() = this.dummy.Next;
252
-
253
-
254
-
255
- ///<summary>
256
-
257
- /// リストの末尾ノード。
258
-
259
- ///</summary>
260
-
261
- public val Last: Node
262
-
263
- get() = this.dummy.Previous;
264
-
265
-
266
-
267
- ///<summary>
268
-
269
- /// リストの終端（末尾よりも後ろの番兵に当たるノード）。
270
-
271
- ///</summary>
272
-
273
- public val End: Node
274
-
275
- get() = this.dummy;
276
-
277
-
278
-
279
- //#endregion
280
-
281
- //#region 挿入・削除
282
-
283
-
284
-
285
- ///<summary>
286
-
287
- /// ノード n の後ろに新しい要素を追加。
288
-
289
- ///</summary>
290
-
291
- ///<param name = "e">新しい要素</param>
292
-
293
- ///<param name = "n">要素の挿入位置</param>
294
-
295
- ///<returns>新しく挿入されたノード</returns>
296
-
297
- public fun InsertEAfterN(e: T, n: Node): Node {
298
-
299
- val m: Node = Node(e, n, n.Next);
300
-
301
- n.Next.Previous = m;
302
-
303
- n.Next = m;
304
-
305
- this.count++;
306
-
307
- return m;
308
-
309
- }
310
-
311
-
312
-
313
- ///<summary>
314
-
315
- /// ノード n の前に新しい要素を追加。
316
-
317
- ///</summary>
318
-
319
- ///<param name = "e">新しい要素</param>
320
-
321
- ///<param name = "n">要素の挿入位置</param>
322
-
323
- ///<returns>新しく挿入されたノード</returns>
324
-
325
- public fun InsertEBeforeN(e: T, n: Node): Node {
326
-
327
- val m: Node = Node(e, n.Previous, n);
328
-
329
- n.Previous.Next = m;
330
-
331
- n.Previous = m;
332
-
333
- this.count++;
334
-
335
- return m;
336
-
337
- }
338
-
339
-
340
-
341
- ///<summary>
342
-
343
- /// 先頭に新しい要素を追加。
344
-
345
- ///</summary>
346
-
347
- ///<param name = "elem">新しい要素</param>
348
-
349
- ///<returns>新しく挿入されたノード</returns>
350
-
351
- public fun InsertFirst(elem: T): Node {
352
-
353
- return this.InsertEAfterN(elem, this.dummy);
354
-
355
- }
356
-
357
-
358
-
359
- ///<summary>
360
-
361
- /// 末尾に新しい要素を追加。
362
-
363
- ///</summary>
364
-
365
- ///<param name = "elem">新しい要素</param>
366
-
367
- ///<returns>新しく挿入されたノード</returns>
368
-
369
- public fun InsertLast(elem: T): Node {
370
-
371
- return this.InsertEBeforeN(elem, this.dummy);
372
-
373
- }
374
-
375
-
376
-
377
- ///<summary>
378
-
379
- /// ノード n の自身を削除。
380
-
381
- ///</summary>
382
-
383
- ///<param name = "n">要素の削除位置</param>
384
-
385
- ///<returns>削除した要素の次のノード</returns>
386
-
387
- public fun Erase(n: Node): Node {
388
-
389
- if (n == this.dummy) {
390
-
391
- return this.dummy;
392
-
393
- }
394
-
395
- n.Previous.Next = n.Next;
396
-
397
- n.Next.Previous = n.Previous;
398
-
399
- this.count--;
400
-
401
- return n.Next;
402
-
403
- }
404
-
405
-
406
-
407
- ///<summary>
408
-
409
- /// 先頭の要素を削除。
410
-
411
- ///</summary>
412
-
413
- public fun EraseFirst(): Unit {
414
-
415
- this.Erase(this.First);
416
-
417
- }
418
-
419
-
420
-
421
- ///<summary>
422
-
423
- /// 末尾の要素を削除。
424
-
425
- ///</summary>
426
-
427
- public fun EraseLast(): Unit {
428
-
429
- this.Erase(this.Last);
430
-
431
- }
432
-
433
-
434
-
435
- //#endregion
436
-
437
- //#region IEnumerable<T>メンバ
438
-
439
-
440
-
441
- public fun <T> GetEnumerator(): IEnumerator<T> {
442
-
443
- for (var n: Node = this.First; n!= this.End; n = n.Next) {
444
-
445
- return yield(n.value);
446
-
447
- }
448
-
449
- }
450
-
451
-
452
-
453
- fun System.Collections.IEnumerable.GetEnumerator(): System.Collections.IEnumerator {
454
-
455
- return this.GetEnumerator();
456
-
457
- }
458
-
459
-
460
-
461
- //#endregion
462
-
463
-
464
-
465
- // public fun hasNext(): boolean {
466
-
467
- // return n!= this.End;
468
-
469
- // }
470
-
471
- // public fun next(): Iterator {
472
-
473
- // return n.Next;
474
-
475
- // }
476
-
477
-
478
-
479
- }
480
-
481
-
482
-
483
- ```
484
-
485
431
 
486
432
 
487
433
  ### 試したこと

1

タイトルに明記

2020/12/02 13:16

投稿

picohead
picohead

スコア8

test CHANGED
@@ -1 +1 @@
1
- Kotlinで双方向連結リストを実装したい。
1
+ Kotlinで双方向連結リストを実装したい。特にGetEnumeratorと型引数Tらへんに困ってます。
test CHANGED
File without changes