AOJの問題ベースで書いた。

問題


双方向連結リストを実装するという問題。

AOJ: ALDS1_3_C

所感など


所感など

  • 実際に書いてみると計算量への理解が進む
    • 挿入, 最初と最後の要素の削除は O(1)
    • 特定の要素の削除は O(N)
  • いろいろ書き足していくと汚くなってしまったので、挿入・削除都度で要素数をカウントして保持しておくような実装も組み合わせればシンプルにできたと思う
  • getterとsetter書くのめんどい
  • privateを表現する_書くのめんどくさいし、見辛いので次回から止めようかと思った
  • やっぱり静的型付き言語でやりたい
    • けど開発環境回りとかがめんどくさい

コード


以下、提出したコード。

コード部のライセンスはAOJの利用規約に準拠します

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
// https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/3/ALDS1_3_C
class Node {
constructor(data) {
this._data = data;
this._prev = null;
this._next = null;
}

getData() {
return this._data;
}

getPrev() {
return this._prev;
}

setPrev(node) {
this._prev = node;
}

getNext() {
return this._next;
}

setNext(node) {
this._next = node;
}
}

class DoubleLinkedList {
constructor() {
this._head = null;
this._tail = null;
}

// O(1)
insert(node) {
if (this._head !== null) {
this._head.setPrev(node);
node.setNext(this._head);
} else {
this._tail = node;
}
this._head = node;
}

// O(N)
//値が一致する最初の要素を消す
delete(node) {
if (this._head === null) {
return;
}

let current = this._head;
while(current !== null) {
if (current.getData() === node.getData()) {
const prev = current.getPrev();
const next = current.getNext();
if (prev !== null) {
prev.setNext(next);
}
if (next !== null) {
next.setPrev(prev);
}
if (this._head === current) {
this._head = next;
}
if (this._tail === current) {
this._tail = prev;
}
break;
}
current = current.getNext();
}
}

// O(1)
deleteFirst() {
if (this._head === null) {
return;
}

const next = this._head.getNext();
if (next !== null) {
next.setPrev(null);
this._head = next;
} else {
this._head = null;
}
}

// O(1)
deleteLast() {
if (this._tail === null) {
return;
}

const prev = this._tail.getPrev();
if (prev !== null) {
prev.setNext(null);
this._tail = prev;
} else {
if (this._head === this._tail) {
this._head = null;
}
this._tail = null;
}
}

getValues() {
if (this._head === null) {
return [];
}

let current = this._head;
let values = [];
while(current !== null) {
values.push(current.getData());
current = current.getNext();
}
return values;
}
}

実行と実行結果(以下は提出したコードと異なる)

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
const doubleLinkedList = new DoubleLinkedList();

doubleLinkedList.insert(new Node("5"));
console.log(doubleLinkedList.getValues());

doubleLinkedList.insert(new Node("2"));
console.log(doubleLinkedList.getValues());

doubleLinkedList.insert(new Node("3"));
console.log(doubleLinkedList.getValues());

doubleLinkedList.insert(new Node("1"));
console.log(doubleLinkedList.getValues());

doubleLinkedList.delete(new Node("3"));
console.log(doubleLinkedList.getValues());

doubleLinkedList.insert(new Node("6"));
console.log(doubleLinkedList.getValues());

doubleLinkedList.delete(new Node("5"));
console.log(doubleLinkedList.getValues());

doubleLinkedList.deleteFirst();
console.log(doubleLinkedList.getValues());

doubleLinkedList.deleteLast();
console.log(doubleLinkedList.getValues());


------------

[ '5' ]
[ '2', '5' ]
[ '3', '2', '5' ]
[ '1', '3', '2', '5' ]
[ '1', '2', '5' ]
[ '6', '1', '2', '5' ]
[ '6', '1', '2' ]
[ '1', '2' ]
[ '1' ]

OWARI。NERU。