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)). لهذا التمرين ، لاحظ أننا لا نطلب منك فقط طباعة القائمة المرتبطة في الاتجاه المعاكس أو استخدام قائمة أخرى مرتبطة لتخزين القيمة بترتيب عكسي. يجب أن يعكس برنامجك اتجاه قائمة مرتبطة منفردة. وبعبارة أخرى ، يجب أن تشير جميع المؤشرات إلى الخلف. المكافأة: حل هذه المشكلة باستخدام كل من الخوارزميات المتكررة والتكرارية.
اكتب خوارزمية للعثور على العنصر الثالث من نهاية القائمة المرتبطة. ملاحظة ، قد تميل إلى إضافة خاصية طول إلى فئة القائمة المرتبطة. خاصية الطول ليست خاصية نموذجية للقائمة المرتبطة ، وبالتالي لا تقوم بأي تعديل لفئة القائمة المرتبطة المقدمة لك.
اكتب خوارزمية للعثور على العنصر الأوسط لقائمة مرتبطة. ملاحظة ، قد تميل إلى إضافة خاصية طول إلى فئة القائمة المرتبطة. خاصية الطول ليست خاصية نموذجية للقائمة المرتبطة ، وبالتالي لا تقوم بأي تعديل لفئة القائمة المرتبطة المقدمة لك. أيضًا ، لن يجد العثور على حجم القائمة المرتبطة باستخدام وظيفة Size () وتقسيمها على النصف الوسط الصحيح للقائمة المرتبطة. لذلك ، لا تستخدم أي من هذه الأساليب.
اكتب خوارزمية للعثور على ما إذا كانت القائمة المرتبطة بها دورة (أي ، ما إذا كانت العقدة في القائمة لها قيمتها التالية تشير إلى عقدة سابقة في القائمة). لهذا التمرين ، قم بإنشاء قائمة مرتبطة مع اسم Cyclelist. تأكد من إدراج العقد في القائمة بحيث يكون لها دورة. ثم اختبر برنامجك مع وظيفة Cyclelist.
تنفيذ قائمة مرتبطة بشكل مضاعف. سيتم إدراج الوظائف الأساسية للقائمة المرتبطة بشكل مضاعف (أولاً ، أخيرًا ، قبل ، بعد ، و AT) ، وإزالتها ، والعثور عليها. اكتب وظيفة maindll ، وداخلها قم بإنشاء قائمة DLL المرتبطة بشكل مضاعف وأضف العناصر التالية: Aquaria ، Caprica ، Gemenon ، Picon ، Sagitron.
بالنظر إلى القائمة المرتبطة بشكل مضاعف أعلاه ، اكتب برنامجًا يعكس القائمة المرتبطة بشكل مضاعف. كيف يختلف هذا التنفيذ عن عكس القائمة المرتبطة منفردة؟
