DSA LinkedList
1.0.0
リストノードクラスをリストします
class ListNode {
constructor(data) {
this.data = data
this.next = null
}
}
リンクリストクラス
class LinkedList {
constructor(head = null) {
this.head = head
}
}
リンクリストを作成します
let node1 = new ListNode(2)
let node2 = new ListNode(5)
node1.next = node2
let list = new LinkedList(node1)
console.log(list.head.next.data) //returns 5
size() {
let count = 0;
let node = this.head;
while (node) {
count++;
node = node.next
}
return count;
}
const ListFunctions = {
display: (linkedList) => {
items = [];
if (linkedList.head === null) {
return "The list is empty";
} else {
let currNode = linkedList.head;
while (currNode.next !== null) {
items.push(currNode.data);
currNode = currNode.next;
}
items.push(currNode.data);
}
return `Linked List Items: ${items.join("->")}`;
}
isEmpty: (linkedList) => {
if (linkedList.head === null) {
return `This list is empty`;
}
return `There are items in this list`;
}
find(item) {
let currNode = this.head;
if (!this.head) {
return null;
}
while (currNode.data !== item) {
if (currNode.next === null) {
return null;
} else {
currNode = currNode.next;
}
}
return currNode;
}
}
clear() {
this.head = null;
}
remove(item) {
if (!this.head) {
return null;
}
if (this.head.data === item) {
this.head = this.head.next;
return;
}
let currNode = this.head;
let previousNode = this.head;
while (currNode !== null && currNode.data !== item) {
previousNode = currNode;
currNode = currNode.next;
}
if (currNode === null) {
return;
}
previousNode.next = currNode.next;
}
insertFirst(item) {
this.head = new _Node(item, this.head);
}
insertLast(item) {
if (this.head === null) {
this.insertFirst(item);
} else {
let tempNode = this.head;
while (tempNode.next !== null) {
tempNode = tempNode.next;
}
tempNode.next = new _Node(item, null);
}
}
insertBefore(item, key) {
if (!this.head) {
return;
}
if (this.head.data === key) {
this.insertFirst(item);
return;
}
let currNode = this.head;
let previousNode = this.head;
while (currNode !== null && currNode.data !== key) {
previousNode = currNode;
currNode = currNode.next;
}
if (currNode === null) {
console.log(`key value not found`);
return;
}
previousNode.next = new _Node(item, currNode);
}
insertAfter(item, key) {
if (!this.head) {
return;
}
if (this.head.data === key) {
this.insertFirst(item);
return;
}
let currNode = this.head;
let nextNode = this.head;
while (currNode !== null && currNode.data !== key) {
currNode = nextNode;
nextNode = nextNode.next;
}
if (currNode === null) {
console.log(`key value not found`);
return;
}
currNode.next = new _Node(item, nextNode);
}
getLast() {
let lastNode = this.head;
if (lastNode) {
while (lastNode.next) {
lastNode = lastNode.next
}
}
return lastNode
}
getFirst() {
return this.head;
}
findPrevious: (linkedList, key) => {
if (linkedList.head === null) {
return null;
}
let prevNode;
let currNode = linkedList.head;
while (currNode.data !== key) {
prevNode = currNode;
currNode = currNode.next;
}
return `The previous node is ${prevNode.data}`;
}
これらのドリルでは、リンクリストの作成、コアの実装、およびいくつかの補足操作を練習します。また、リンクリストを使用してインタビューの質問を解決します。これらのエクササイズのそれぞれについて大きなOを評価することを忘れないでください。 1つ以上のサンプル入力と出力を記載して、各問題を開始します。
リンクされたリストクラスとこれらのコア関数（挿入、挿入ラスト、削除、検索）をゼロから書き込みます。
リンクリストクラスで動作する次の機能を実装します。これらは、リンクリストクラスのメソッドの代わりに自由関数である必要があるため、リンクリストクラスの外側に実装することに注意してください。演習1で作成されたリストを使用して各関数をテストします。
次の関数を分析し（IDEで実行することなく）、解決しようとしている問題を判断します。このアルゴリズムの時間の複雑さはどのくらいですか？
function WhatDoesThisProgramDo(lst) {
let current = lst.head;
while (current !== null) {
let newNode = current;
while (newNode.next !== null) {
if (newNode.next.value === current.value) {
newNode.next = newNode.next.next;
}
else {
newNode = newNode.next;
}
}
current = current.next;
}
}
アルゴリズムを記述して、リンクリストを逆にします。アルゴリズムの時間の複雑さは線形（O（n））でなければなりません。この演習では、リンクされたリストを逆に印刷するだけではないか、別のリンクリストを使用して値を逆順に保存するように依頼していないことに注意してください。プログラムは、特定のリンクされたリストの方向を逆にする必要があります。言い換えれば、すべてのポインターは後方に指さす必要があります。ボーナス：再帰アルゴリズムと反復アルゴリズムの両方を使用して、この問題を解決します。
アルゴリズムを記述して、リンクリストの最後から3番目の要素を見つけます。注Lenked Listクラスに長さのプロパティを追加するように誘惑される場合があります。長さのプロパティは、リンクリストの典型的なプロパティではないため、提供されるリンクリストクラスを変更しないでください。
アルゴリズムを記述して、リンクリストの中央要素を見つけます。注Lenked Listクラスに長さのプロパティを追加するように誘惑される場合があります。長さのプロパティは、リンクリストの典型的なプロパティではないため、提供されるリンクリストクラスを変更しないでください。また、size（）関数を使用してリンクされたリストのサイズを見つけて半分に除算しても、リンクリストの正しい中央は見つかりません。したがって、これらのアプローチのいずれかを使用しないでください。
アルゴリズムを記述して、リンクリストにサイクルがあるかどうかを確認します（つまり、リスト内のノードに次の値がリストの以前のノードを指しているかどうか）。この演習では、サイクレリストという名前のリンクリストを作成します。リストにノードを挿入して、サイクルを持つようにしてください。次に、サイクレリスト機能でプログラムをテストします。
二重リンクリストを実装します。二重リンクリストの主要な機能は、挿入（最初、最後、前、後、、at）、削除、および検索です。関数maindllを作成し、その中に二重リンクリストDLLを作成し、Aquaria、Caprica、Gemenon、Picon、Sagittaronの次のアイテムを追加します。
上記の二重リンクリストを考えると、二重リンクリストを逆にするプログラムを作成します。この実装は、単独でリンクされたリストを逆にすることとどう違うのですか？
