連結リストメニュー【双方向リスト実装編 step 1 〜 全8問】
【双方向リスト実装編全9問のまとめ】
reader.on('close', () => {
const max_size = 1024;
const end_ptr = 1023;
let start_ptr = 0;
let empty_min_idx = 1; // 空要素のindex
const Value = new Array(max_size);
const Next_Ptr = new Array(max_size);
const Prev_Ptr = new Array(max_size);
[Value[start_ptr], Value[end_ptr]] = [-1, -1];
[Next_Ptr[start_ptr], Next_Ptr[end_ptr]] = [end_ptr, -1];
[Prev_Ptr[start_ptr], Prev_Ptr[end_ptr]] = [-1, start_ptr];
function push_back(val) { // step 1
const new_ptr = empty_min_idx; // Value[empty_min_idx] = a;
Value[new_ptr] = val;
Next_Ptr[Prev_Ptr[end_ptr]] = new_ptr;
Next_Ptr[new_ptr] = end_ptr; // 配列 Next_Ptr を変更
Prev_Ptr[new_ptr] = Prev_Ptr[end_ptr]; // 配列 Prev_Ptr を変更
Prev_Ptr[end_ptr] = new_ptr; // 配列 Prev_Ptr を変更
empty_min_idx++;
}
function push_front(val) { // step 2
const new_ptr = empty_min_idx;
Value[new_ptr] = val;
Next_Ptr[new_ptr] = Next_Ptr[start_ptr];
Next_Ptr[start_ptr] = new_ptr;
Prev_Ptr[Next_Ptr[new_ptr]] = new_ptr;
Prev_Ptr[new_ptr] = start_ptr;
empty_min_idx++;
}
function Remove_from_end() { // step 3
const back_ptr = Prev_Ptr[end_ptr];
if (back_ptr !== start_ptr) {
Next_Ptr[Prev_Ptr[back_ptr]] = end_ptr;
Prev_Ptr[end_ptr] = Prev_Ptr[back_ptr];
}
}
function Remove_from_front() { // step 4
if (Next_Ptr[start_ptr] != end_ptr) {
const back_ptr = Next_Ptr[start_ptr];
Next_Ptr[start_ptr] = Next_Ptr[back_ptr];
Prev_Ptr[Next_Ptr[back_ptr]] = start_ptr;
}
}
// 位置 pos に値 val を挿入する
function insert(pos, val) { // step 5
pos--;
const new_ptr = empty_min_idx; // Value に val を保存する場所
Value[new_ptr] = val; // Value に val を追加
let current_ptr = start_ptr; // 現在のノード
for (let i = 0; i < pos; i++) {
// pos がリストのサイズより大きい場合
if (current_ptr === end_ptr) {
break;
}
current_ptr = Next_Ptr[current_ptr];
}
// 挿入したい箇所の直前までたどり着いた場合
if (current_ptr != end_ptr) {
Next_Ptr[new_ptr] = Next_Ptr[current_ptr];
Prev_Ptr[Next_Ptr[new_ptr]] = new_ptr;
Prev_Ptr[new_ptr] = current_ptr;
Next_Ptr[ current_ptr] = new_ptr;
}
empty_min_idx++;
}
function Remove_from_pos(pos) { // step 6
let current_ptr = start_ptr;
for (let i = 0; i <= pos - 1; i++) {
// pos がリストのサイズより大きい場合
if ( current_ptr === end_ptr) {
break;
}
// 削除したい箇所の直前までたどり着いた場合
if (i === pos - 1) {
Next_Ptr[Next_Ptr[Next_Ptr[current_ptr]]] = current_ptr;
Next_Ptr[ current_ptr] = Next_Ptr[Next_Ptr[current_ptr]];
break;
}
current_ptr = Next_Ptr[current_ptr];
}
}
function Remove_from_pos_to_pos(left, right) {
let left_ptr = start_ptr; // 削除したい区間の直前のインデックス
for (i = 0; i < left - 1; i++) {
// left がリストのサイズより大きい場合
if (left_ptr === end_ptr) {
break;
}
left_ptr = Next_Ptr[left_ptr];
}
let right_ptr = start_ptr; // 削除したい区間の直後のインデックス
// 削除したい区間の直後まで移動する
for (let i = 0; i < right; i++) {
// right_ptr は end_ptr でも良いが、end_ptr の次のノードにはならない
if (i < right && right_ptr === end_ptr) {
right_ptr = -1;
break;
}
right_ptr = Next_Ptr[right_ptr];
}
if (left_ptr !== end_ptr && right_ptr !== -1) {
Next_Ptr[left_ptr] = right_ptr;
Prev_Ptr[right_ptr] = left_ptr;
}
}
function erase(pos) {
let current_ptr = start_ptr;
for (let i = 0; i <= pos; i++) {
// pos がリストのサイズより大きい場合
if (current_ptr === end_ptr) {
break;
}
// 削除したい箇所の直前までたどり着いた場合
if (i === pos) {
Prev_Ptr[Next_Ptr[Next_Ptr[current_ptr]]] = current_ptr;
Next_Ptr[current_ptr] = Next_Ptr[Next_Ptr[current_ptr]];
break;
}
current_ptr = Next_Ptr[current_ptr];
}
}
function display() {
let current_ptr = start_ptr;
while (current_ptr !== end_ptr) {
if (current_ptr !== start_ptr) {
console.log(Value[current_ptr]);
}
current_ptr = Next_Ptr[current_ptr];
}
}
/* step 1
const N = Number(lines[0]);
for (let i = 1; i <= N; i++) {
const n = Number(lines[i]);
push_back(n);
}
*/
/* step 2
const N = Number(lines[0]);
for (let i = 1; i <= N; i++) {
const n = Number(lines[i]);
push_front(n);
}
*/
/* step 3
const [N, K] = lines[0].split(' ').map(Number);
for (let i = 1; i <= N; i++) {
const n = Number(lines[i]);
push_back(n);
}
for (let i = 0; i < K; i++) {
Remove_from_end();
}
*/
/* step 4
const [N, K] = lines[0].split(' ').map(Number);
for (let i = 1; i <= N; i++) {
const n = Number(lines[i]);
push_back(n);
}
for (let i = 0; i < K; i++) {
Remove_from_front();
}
*/
/* step 5
const [N, P, X] = lines[0].split(' ').map(Number);
for (let i = 1; i <= N; i++) {
const n = Number(lines[i]);
push_back(n);
}
insert(P, X);
*/
/* step 6
const [N, P] = lines[0].split(' ').map(Number);
for (let i = 1; i <= N; i++) {
const n = Number(lines[i]);
push_back(n);
}
Remove_from_pos(P);
*/
/* step 7
const [N, L, R] = lines[0].split(' ').map(Number);
for (let i = 1; i <= N; i++) {
const n = Number(lines[i]);
push_back(n);
}
Remove_from_pos_to_pos(L, R );
*/
/* 完成
const [N, Q] = lines[0].split(' ').map(Number);
for (let i = 1; i <= N; i++) {
const n = Number(lines[i]);
push_back(n);
}
for (let i = N + 1; i <= N + Q; i++) {
const q = lines[i].split(' ').map(Number);
// console.log(q);
switch (q[0]) {
case 1:
insert(q[1], q[2]);
break;
case 2:
erase(q[1] - 1);
break;
}
}
*/
// console.log(Value);
// console.log(Next_Ptr);
// console.log(Prev_Ptr);
display();
});
ポインタと値を 区別して 出力値を制御…!!?? 解説の動画も公開されています。
【step 1 〜 完成 の function 】
reader.on('close', () => {
const max_size = 1024;
const end_ptr = 1023;
let start_ptr = 0;
let empty_min_idx = 1; // 空要素のindex
const Value = new Array(max_size);
const Next_Ptr = new Array(max_size);
const Prev_Ptr = new Array(max_size);
[Value[start_ptr], Value[end_ptr]] = [-1, -1];
[Next_Ptr[start_ptr], Next_Ptr[end_ptr]] = [end_ptr, -1];
[Prev_Ptr[start_ptr], Prev_Ptr[end_ptr]] = [-1, start_ptr];
function push_back(val) {
const new_ptr = empty_min_idx; //Value[empty_min_idx] = a;
Value[new_ptr] = val;
Next_Ptr[Prev_Ptr[end_ptr]] = new_ptr;
Next_Ptr[new_ptr] = end_ptr; // 配列 Next_Ptr を変更
Prev_Ptr[new_ptr] = Prev_Ptr[end_ptr]; // 配列 Prev_Ptr を変更
Prev_Ptr[end_ptr] = new_ptr; // 配列 Prev_Ptr を変更
empty_min_idx++;
}
function push_front(val) { // step 2
const new_ptr = empty_min_idx;
Value[new_ptr] = val;
Next_Ptr[new_ptr] = Next_Ptr[start_ptr];
Next_Ptr[start_ptr] = new_ptr;
Prev_Ptr[Next_Ptr[new_ptr]] = new_ptr;
Prev_Ptr[new_ptr] = start_ptr;
empty_min_idx++;
}
function Remove_from_end() { // step 3
const back_ptr = Prev_Ptr[end_ptr];
if (back_ptr !== start_ptr) {
Next_Ptr[Prev_Ptr[back_ptr]] = end_ptr;
Prev_Ptr[end_ptr] = Prev_Ptr[back_ptr];
}
}
function Remove_from_front() { // 先頭の要素を表示しない
if (Next_Ptr[start_ptr] != end_ptr) {
const back_ptr = Next_Ptr[start_ptr];
Next_Ptr[start_ptr] = Next_Ptr[back_ptr];
Prev_Ptr[Next_Ptr[back_ptr]] = start_ptr;
}
}
function insert(pos, val) {
pos--;
const new_ptr = empty_min_idx; // Value に val を保存する場所
Value[new_ptr] = val; // Value に val を追加
let current_ptr = start_ptr; // 現在のノード
for (let i = 0; i < pos; i++) {
if ( current_ptr === end_ptr) {
break;
}
current_ptr = Next_Ptr[ current_ptr];
}
if ( current_ptr != end_ptr) {
Next_Ptr[new_ptr] = Next_Ptr[ current_ptr];
Prev_Ptr[Next_Ptr[new_ptr]] = new_ptr;
Prev_Ptr[new_ptr] = current_ptr;
Next_Ptr[ current_ptr] = new_ptr;
}
empty_min_idx++;
}
function Remove_from_pos(pos) { // step 6
let current_ptr = start_ptr;
for (let i = 0; i <= pos - 1; i++) {
if ( current_ptr === end_ptr) {
break;
}
if (i === pos - 1) {
Prev_Ptr[Next_Ptr[Next_Ptr[ current_ptr]]] = current_ptr;
Next_Ptr[ current_ptr] = Next_Ptr[Next_Ptr[ current_ptr]];
break;
}
current_ptr = Next_Ptr[ current_ptr];
}
}
function Remove_from_pos_to_pos(left, right) {
let left_ptr = start_ptr; // 削除したい区間の直前のインデックス
for (i = 0; i < left - 1; i++) {
// left がリストのサイズより大きい場合
if (left_ptr === end_ptr) {
break;
}
left_ptr = Next_Ptr[left_ptr];
}
let right_ptr = start_ptr; // 削除したい区間の直後のインデックス
// 削除したい区間の直後まで移動する
for (let i = 0; i < right; i++) {
// right_ptr は end_ptr でも良いが、end_ptr の次のノードにはならない
if (i < right && right_ptr === end_ptr) {
right_ptr = -1;
break;
}
right_ptr = Next_Ptr[right_ptr];
}
if (left_ptr !== end_ptr && right_ptr !== -1) {
Next_Ptr[left_ptr] = right_ptr;
Prev_Ptr[right_ptr] = left_ptr;
}
}
function erase(pos) {
let current_ptr = start_ptr;
for (let i = 0; i <= pos; i++) {
if ( current_ptr === end_ptr) {
break;
}
if (i === pos) {
Prev_Ptr[Next_Ptr[Next_Ptr[ current_ptr]]] = current_ptr;
Next_Ptr[ current_ptr] = Next_Ptr[Next_Ptr[ current_ptr]];
break;
}
current_ptr = Next_Ptr[ current_ptr];
}
}
function display() {
let current_ptr = start_ptr;
while ( current_ptr !== end_ptr) {
if ( current_ptr !== start_ptr) {
console.log(Value[ current_ptr]);
}
current_ptr = Next_Ptr[ current_ptr];
}
}
});各問 の function のみ抜き出しました。アルゴリズムの問題なので 使いまわせるかも…。
コメント