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 Big O สำหรับแบบฝึกหัดเหล่านี้ เริ่มต้นปัญหาแต่ละครั้งโดยระบุอินพุตและเอาต์พุตตัวอย่าง 1 ตัวอย่างขึ้นไป
เขียนคลาสรายการที่เชื่อมโยงและฟังก์ชั่นหลักเหล่านี้ (InsertFirst, InsertLast, ลบ, ค้นหา) ตั้งแต่เริ่มต้น
ใช้ฟังก์ชั่นต่อไปนี้ที่ทำงานในคลาสรายการที่เชื่อมโยงของคุณ โปรดทราบว่าสิ่งเหล่านี้ควรเป็นฟังก์ชั่นฟรีแทนวิธีการของคลาสรายการที่เชื่อมโยงดังนั้นนำไปใช้นอกคลาสรายการที่เชื่อมโยง ทดสอบแต่ละฟังก์ชั่นโดยใช้รายการที่สร้างขึ้นในแบบฝึกหัด 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 จากส่วนท้ายของรายการที่เชื่อมโยง หมายเหตุคุณอาจถูกล่อลวงให้เพิ่มคุณสมบัติความยาวในคลาสรายการที่เชื่อมโยงของคุณ คุณสมบัติความยาวไม่ใช่คุณสมบัติทั่วไปของรายการที่เชื่อมโยงดังนั้นอย่าทำการปรับเปลี่ยนใด ๆ ในคลาสรายการที่เชื่อมโยงที่คุณให้ไว้
เขียนอัลกอริทึมเพื่อค้นหาองค์ประกอบกลางของรายการที่เชื่อมโยง หมายเหตุคุณอาจถูกล่อลวงให้เพิ่มคุณสมบัติความยาวในคลาสรายการที่เชื่อมโยงของคุณ คุณสมบัติความยาวไม่ใช่คุณสมบัติทั่วไปของรายการที่เชื่อมโยงดังนั้นอย่าทำการปรับเปลี่ยนใด ๆ ในคลาสรายการที่เชื่อมโยงที่คุณให้ไว้ นอกจากนี้การค้นหาขนาดของรายการที่เชื่อมโยงโดยใช้ฟังก์ชั่นขนาด () และหารด้วยครึ่งหนึ่งจะไม่พบตรงกลางที่ถูกต้องของรายการที่เชื่อมโยง ดังนั้นอย่าใช้วิธีการเหล่านี้อย่างใดอย่างหนึ่ง
เขียนอัลกอริทึมเพื่อค้นหาว่ารายการที่เชื่อมโยงมีวัฏจักร (เช่นโหนดในรายการมีค่าถัดไปชี้ไปที่โหนดก่อนหน้าในรายการ) สำหรับแบบฝึกหัดนี้ให้สร้างรายการที่เชื่อมโยงกับชื่อ CycleList ตรวจสอบให้แน่ใจว่าได้แทรกโหนดในรายการเพื่อให้มีวัฏจักร จากนั้นทดสอบโปรแกรมของคุณด้วยฟังก์ชั่นนักปั่นจักรยาน
ใช้รายการที่เชื่อมโยงเป็นสองเท่า ฟังก์ชั่นหลักของรายการที่เชื่อมโยงสองเท่าจะถูกแทรก (ครั้งแรกสุดท้ายก่อนหลังและที่) ลบและค้นหา เขียนฟังก์ชั่น maindll และภายในสร้างรายการ DLL ที่เชื่อมโยงสองเท่าและเพิ่มรายการต่อไปนี้ลงไป: Aquaria, Caprica, Gemenon, Picon, Sagitaron
ให้รายการที่เชื่อมโยงสองเท่าด้านบนเขียนโปรแกรมที่ย้อนกลับรายการที่เชื่อมโยงเป็นสองเท่า การใช้งานนี้แตกต่างจากการย้อนกลับรายการที่เชื่อมโยงกันอย่างไร
