JavaScript 在链表中搜索元素
链表是一种线性数据结构,每个元素(也称为节点)包含一个数据值和指向链表中下一个节点的引用。链表上的一个常见操作是搜索特定的元素。这涉及遍历链表,将每个节点的数据值与目标元素进行比较,直到找到匹配的元素为止。
以下是我们在本文中要使用的链表示例−
10 -> 20 -> 30 -> 40 -> null
在这个链表中,每个节点包含一个值,箭头表示序列中的下一个节点。链表从头节点开始,该节点包含值10,以尾节点结束,该节点包含值40并指向null。我们将使用这个链表来演示如何使用JavaScript在链表中搜索元素。
让我们看下面的示例−
Linked list: 10 -> 20 -> 30 -> 40 -> null
Input: 40
Output: Element found at index 3
Input: 10
Output: Element found at index 0
Input: null
Output: Element not found
现在让我们讨论在JavaScript中创建链表的算法。
步骤
步骤1 - 定义一个Node类,有两个属性:value和next。value属性代表节点中存储的数据,next属性是链表中下一个节点的引用。
步骤2 - 定义一个LinkedList类,有三个属性:head、tail和length。head属性代表链表中的第一个节点,tail属性代表链表中的最后一个节点,length属性代表链表中的节点数。
步骤3 - 在LinkedList类中定义一个名为add的方法,以一个value值作为参数。add方法应该创建一个具有给定value值的新节点,并将其添加到链表的末尾。
步骤4 - 在LinkedList类中定义一个名为remove的方法,以一个value值作为参数。remove方法应该删除链表中与给定value值相匹配的第一个节点。
步骤5 - 在LinkedList类中定义一个名为search的方法,以一个value值作为参数。search方法应该返回链表中与给定value值相匹配的第一个节点,如果找不到节点,则返回null。
步骤6 - 在LinkedList类中定义一个名为reverse的方法,用于反转链表中节点的顺序。
示例:使用JavaScript实现上述算法
下面的程序定义了一个Node类和一个LinkedList类。Node类使用给定的数据值和对列表中下一个节点的引用创建一个新的节点。LinkedList类创建一个新的链表,头节点初始指向null,大小属性设置为0。add方法在链表的末尾添加一个新节点。search方法遍历链表并返回元素的索引(如果找到),否则返回一个说明该元素未找到的消息。最后,程序创建一个新的链表,添加元素,并搜索特定元素。
// Define the Node class for a singly linked list
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Define the LinkedList class
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// Add an element to the linked list
add(element) {
const node = new Node(element);
// If the linked list is empty, set the new node as the head
if (this.head === null) {
this.head = node;
} else {
// Traverse to the end of the linked list and add the new node
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = node;
}
this.size++;
}
// Search for an element in the linked list
search(element) {
let current = this.head;
let index = 0;
// Traverse through the linked list until the element is found
while (current !== null) {
if (current.data === element) {
return `Element found at index ${index}`;
}
current = current.next;
index++;
}
return "Element not found";
}
}
// Create a new linked list
const ll = new LinkedList();
// Add elements to the linked list
ll.add(10);
ll.add(20);
ll.add(30);
ll.add(40);
ll.add(50);
// Search for an element in the linked list
const result = ll.search(30);
console.log(result);
结论
使用JavaScript在链表中搜索元素的程序涉及创建一个“LinkedList”类,该类定义了向列表中添加元素和搜索列表中元素的方法。该程序使用while循环遍历链表,并将每个节点中的数据元素与要搜索的元素进行比较。如果找到元素,程序将返回节点的索引,如果未找到元素,程序将返回“未找到元素”。