DSA LinkedList
1.0.0
Daftar kelas simpul
class ListNode {
constructor(data) {
this.data = data
this.next = null
}
}
Kelas Daftar Tertaut
class LinkedList {
constructor(head = null) {
this.head = head
}
}
Buat daftar tertaut
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}`;
}
Dalam latihan ini, Anda akan berlatih membuat daftar yang ditautkan, menerapkan intinya, dan beberapa operasi tambahan. Anda juga akan menggunakan daftar tertaut Anda untuk menyelesaikan pertanyaan wawancara. Jangan lupa untuk menilai O besar untuk masing -masing latihan ini. Mulailah setiap masalah dengan menyatakan 1 atau lebih input dan output sampel.
Tulis kelas daftar tertaut dan fungsi -fungsi inti ini (InsertFirst, InsertLast, Hapus, Temukan) dari awal.
Menerapkan fungsi -fungsi berikut yang beroperasi di kelas daftar tertaut Anda. Perhatikan bahwa ini harus menjadi fungsi gratis alih -alih metode kelas daftar tertaut, jadi terapkan di luar kelas daftar tertaut. Uji setiap fungsi menggunakan daftar yang dibuat dalam Latihan 1.
Menganalisis fungsi berikut (tanpa menjalankannya dalam IDE) untuk menentukan masalah apa yang ingin dipecahkan. Apa kompleksitas waktu dari algoritma ini?
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;
}
}
Tulis algoritma untuk membalikkan daftar tertaut. Kompleksitas waktu algoritma Anda harus linier (O (n)). Untuk latihan ini, perhatikan kami tidak meminta Anda hanya untuk mencetak daftar tertaut secara terbalik atau menggunakan daftar tertaut lain untuk menyimpan nilai dalam urutan terbalik. Program Anda harus membalikkan arah daftar terkait tunggal yang diberikan. Dengan kata lain, semua pointer harus menunjuk ke belakang. Bonus: Selesaikan masalah ini menggunakan algoritma rekursif dan iteratif.
Tulis algoritma untuk menemukan elemen ke -3 dari akhir daftar tertaut. Catatan Anda mungkin tergoda untuk menambahkan properti panjang ke kelas daftar tertaut Anda. Properti panjang bukanlah properti khas dari daftar tertaut, oleh karena itu jangan membuat modifikasi apa pun pada kelas daftar tertaut yang diberikan kepada Anda.
Tulis algoritma untuk menemukan elemen tengah dari daftar tertaut. Catatan Anda mungkin tergoda untuk menambahkan properti panjang ke kelas daftar tertaut Anda. Properti panjang bukanlah properti khas dari daftar tertaut, oleh karena itu jangan membuat modifikasi apa pun pada kelas daftar tertaut yang diberikan kepada Anda. Juga, menemukan ukuran daftar yang ditautkan menggunakan fungsi size () dan membaginya dengan setengahnya tidak akan menemukan bagian tengah yang benar dari daftar yang ditautkan. Jadi, jangan gunakan salah satu dari pendekatan ini.
Tulis algoritma untuk menemukan apakah daftar yang ditautkan memiliki siklus (yaitu, apakah simpul dalam daftar memiliki nilai berikutnya yang menunjuk ke simpul sebelumnya dalam daftar). Untuk latihan ini, buat daftar tertaut dengan nama siklus. Pastikan untuk memasukkan node dalam daftar sehingga memiliki siklus. Kemudian uji program Anda dengan fungsi siklus.
Menerapkan daftar yang ditautkan ganda. Fungsi utama dari daftar yang ditautkan ganda akan dimasukkan (pertama, terakhir, sebelum, setelah, dan pada), menghapus, dan menemukan. Tulis fungsi Maindll, dan di dalamnya buat daftar DLL yang ditautkan ganda dan tambahkan item berikut ke dalamnya: Aquaria, Caprica, Gemenon, Picon, Sagittaron.
Mengingat daftar yang ditautkan ganda di atas, tulis program yang membalikkan daftar ditautkan ganda. Bagaimana implementasi ini berbeda dari membalikkan daftar yang ditautkan secara tunggal?
