I. チェーンテーブルの基本概念
- 複数要素のリスト
- 要素は不連続に格納され、次のポインターでリンクされます。
リンクされたテーブルはノードの集まりです。各ノードは、オブジェクトへの参照を使用して後継ノードを指定します。別のノードへの参照をチェーンと呼びます。例えば
連鎖表の定義
ほとんどの場合、ヘッダー・ノードはリスト全体を表すのに使われます。
function ListNode(val) {
this.val = val;
this.next = null;
}
次に、チェーン・テーブルの操作
ノードを追加
チェーン・テーブルにノードを追加し、チェーン・テーブルの末尾までトラバースし、末尾のノードに新しいノードを追加します。
コードの実装
function append(element) {
let node = new ListNode(element);
let p = head;
if (!head) {
head = node; // チェーン・テーブルが空の場合、ヘッド・ポインターは新しい要素を指す。
} else {
while (p.next) {
p = p.next;
}
p.next = node;
}
}
上記の結果は
単一のリンクされたテーブルをトラバースし、ノードの値が発見される値に等しいかどうかを判断し、等しい場合はtrueを返し、そうでない場合は、リンクされたテーブル全体のトラバースが見つかりませんでしたまで、次のノードをトラバースし続け、その後falseを返します。
コードの実装
function search(element) {
let p = head;
if (!p) return false; // チェーン・テーブルが空の場合は、直接falseを返す。
while (p) {
if (p.val === element) return true;
p = p.next;
}
return false;
}
ある位置に挿入
ノードを初期化し、位置の1つ前のノードにトラバースし、そのノードの後にノードを挿入します。
コードの実装
function insert(position, element) {
let node = new ListNode(element);
if (position >= 0 && position <= length) {
let prev = head, curr = head, index = 0;
if (position === 0) {
node.next = head;
head = node;
} else {
while (index < position) {
prev = curr;
curr = curr.next;
index++;
}
prev.next = node;
node.next = curr;
}
length++;
} else {
return null;
}
}
上記の結果は次のようになります。
単一リンクテーブルを繰り返し、削除するノードを見つけ、削除します。
コードの実装
function remove(element) {
let p = head, prev = head;
if (!head) return;
while (p) {
if (p.val === element) {
p = p.next;
prev.next = p;
} else {
prev = p;
p = p.next;
}
}
}
III.連鎖表に関する問題
となり、2つの数値の和は
Leetcode 問題2 2つの数値の足し算
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
一方、これら2つの数値を足し合わせると、その和を表す新しい連鎖表が返される。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
入力： (2> 4 -> 3) + (5 -> 6 -> 4)
出力： 7> 0 -> 8
となる：= 807
問題解決のアイデア
- 垂直加算の実装をシミュレート
- 四捨五入がある場合は、四捨五入も加算する必要があることに注意してください。
コード表示
var addTwoNumbers = function(l1, l2) {
let l3 = new ListNode(0); // 結果を格納する新しいチェーン・テーブルを定義する。
let p1 = l1;
let p2 = l2;
let p3 = l3;
let carry = 0; // の丸めを表す。
while (p1 || p2) {
// p1またはp2がnullでない場合、ループし続ける。
let val1 = p1 ? p1.val : 0;
let val2 = p2 ? p2.val : 0;
let sum = val1 + val2 + carry;
carry = Math.floor(sum / 10);
p3.next = new ListNode(sum % 10);
if (p1) p1 = p1.next;
if (p2) p2 = p2.next;
p3 = p3.next;
}
if (carry) {
p3.next = new ListNode(carry);
}
return l3.next;
};
リング・チェーン・テーブル
leetcodeの質問141 リング・チェーン・テーブル
連鎖したテーブルが与えられたとき、その中にリングがあるかどうかを判断する。
与えられたチェーン・テーブルのリングを表すには、チェーン・テーブルの中でチェーンの端が接続されている位置を表す整数posが使われる。 posが-1の場合、与えられたチェーンテーブルにはリングがない。
入力：head= [3,2,0,-4], pos = 1
出力：真
説明：チェーン・テーブルにはリングがあり、そのテールは2番目のノードに接続されている。
問題解決のアイデア
- 2つのポインターを定義
- つのポインターは2歩、1つのポインターは1歩。2つのポインタが再び出会うと
コード表示
var hasCycle = function(head) {
let p1 = head, p2 = head;
while (p1 && p2 && p2.next) {
p1 = p1.next;
p2 = p2.next.next;
if (p1 === p2) {
return true;
}
}
return false;
};
フロントエンドと連鎖リスト
- プロトタイプ・チェーンの本質は、リンクされたテーブルです。
- プロトタイプ・チェーンは __proto___ 属性を介して個々のプロトタイプ・オブジェクトを接続します。
プロトタイプ・チェーンはどのように見えますか？
- オブジェクトの場合： obj -> Object.prototype -> null
プロトタイプ・チェイニングの知識
- Aはプロトタイプチェーンに沿ってB.prototypeを見つけることができる場合、A instanceof Bは真でなければなりません。
- もしAオブジェクトにx属性が見つからなければ、x属性はプロトタイプ・チェインで探されます。
- 以下に返される値を検索します。
const instanceof = (A, B) => {
let p = A;
while (p) {
if (p === B.prototype) {
return true;
}
p = p.__proto__;
}
return false;
};
- が返す値を探します。
var foo = {}, F = function(){};
Object.prototype.a = "value a";
Function.prototype.b = "value b";
console.log(foo.a);
console.log(foo.b);
console.log(F.a);
console.log(F.b);
