JavaScript中链接列表的完整指南
甲链表是一种顺序结构,其由被连接到彼此以线性顺序的项目的序列构成。
class Node {
constructor(element)
{
this.element = element;
this.next = null
}
}
在这里,使用存储两个参数的构造函数创建了一个节点:
- 元素:值
- next:下一个节点的位置
下一个节点的位置在开头存储为空值。
现在让我们在LinkedList
课堂上 实现
// LinkedList class
class LinkedList {
constructor()
{
this.head = null;
this.size = 0;
}
// Main Functions
// add(element)
// insertAt(element, location)
// removeFrom(location)
// removeElement(element)
// Helper Functions
// indexOf(element)
// isEmpty()
// sizeOfList()
// printList()
}
上面的程序显示了构造函数和要实现的方法列表。该类包含两个属性:
- head:存储列表的第一个节点
- size:存储列表的大小
主要功能
加(元素)
// adds an element at the end of list
add(element) {
// creates a new node
var node = new Node(element);
// to store current node
var current;
// if list is Empty add the element and make it head
if (this.head == null)
this.head = node;
else {
current = this.head;
// iterate to the end of the list
while (current.next) {
current = current.next;
}
// add node
current.next = node;
}
this.size++;
}
我们的方法是,首先,如果列表为空,则在开头添加元素,否则我们将元素连续推入下一个节点,然后在末尾添加元素。current
用于在每次迭代后遍历列表,我们将其更新next
为当前节点的。如果next为null(列表的最后一个元素在next中包含null),则将元素添加到列表。
insertAt(element,index)
// insert element at the position 'index' of the list
insertAt(element, index) {
if (index > 0 && index > this.size)
return false;
else {
// creates a new node
var node = new Node(element);
var current, previous;
current = this.head;
// add the element to the first index
if (index == 0) {
node.next = this.head;
this.head = node;
} else {
current = this.head;
var it = 0;
// iterate over the list to find the position to insert
while (it < index) {
it++;
previous = current;
current = current.next;
}
// adding an element
node.next = current;
previous.next = node;
}
this.size++;
}
}
我们的方法是,如果索引为零,则在列表的开头添加一个元素,使其为head;如果索引为列表的最后一个位置,则将元素添加到列表的末尾;否则,如果索引为在0或大小– 1之间,我们迭代到索引并在该索引处添加一个元素
上一个保存当前节点的上一个
removeFrom(index)
// removes an element from the 'index'th location
removeFrom(index) {
if (index > 0 && index > this.size)
return -1;
else {
var current, previous, it = 0;
current = this.head;
previous = current;
// deleting first element
if (index == 0) {
this.head = current.next;
} else {
// iterate over the list to the position to remove an element
while (it < index) {
it++;
previous = current;
current = current.next;
}
// remove the element
previous.next = current.next;
}
this.size--;
// return the remove element
return current.element;
}
}
在这里我们的做法是,如果指数为0,那么我们将头卸下,使列表的下一个节点的头,如果索引大小- 1,那么我们从列表中删除最后一个元素,使以前的最后一个元素,最后如果介于0到size – 1之间,我们使用上一个和当前node删除元素。
removeElement(element)
// removes a given element from the list
removeElement(element) {
var current = this.head;
var previous = null;
// iterate over the list
while (current != null) {
// comparing element with current element
// if found
// then remove the element
// and return true
if (current.element == = element) {
if (previous == null) {
this.head = current.next;
} else {
previous.next = current.next;
}
this.size--;
return current.element;
}
previous = current;
current = current.next;
}
return -1;
}
该函数与removeFrom(index)几乎相同,只是在这里,我们正在搜索元素并将其删除。
辅助功能
indexOf(element)
// finds the index of element
indexOf(element) {
var count = 0;
var current = this.head;
// iterae over the list
while (current != null) {
// compare each element of the list with given element
if (current.element == element)
return count;
count++;
current = current.next;
}
// not found
return -1;
}
在此方法中,我们遍历列表以查找元素的索引。如果列表中不存在它,则返回-1。
是空的()
// checks the list for empty
isEmpty() {
return this.size == 0;
}
在此方法中,我们检查LinkedList类的size属性,如果其值为零,则列表为空。
sizeOfList()
// gives the size of the list
sizeOfList() {
console.log(this.size);
}
仅显示LinkedList类的size属性。
printList()
// prints the list items
printList() {
var current = this.head;
var str = "";
while (current) {
str += current.element + " ";
curr = current.next;
}
console.log(str);
}
在这种方法中,我们遍历整个列表,并串联每个节点的元素并打印出来。
实作
现在,我们将使用与上述不同的功能。
// creating an object for the Linkedlist class
var list = new LinkedList();
// testing isEmpty on an empty list
console.log(list.isEmpty());
// returns true
// adding element to the list
list.add(10);
list.printList();
// prints 10
console.log(list.sizeOfList());
// returns 1
// adding more elements to the list
list.add(20);
list.add(30);
list.add(40);
list.add(50);
list.printList();
// returns 10 20 30 40 50
// prints 50 from the list
list.removeElement(50);
list.printList();
// prints 10 20 30 40
console.log("Index of 40 " + list.indexOf(40));
// returns 3
list.insertAt(60, 2);
// insert 60 at second position
list.printList();
// list contains 10 20 60 30 40
console.log("Is List Empty ? " + list.isEmpty());
// returns false
console.log(list.removeFrom(3));
// remove 3rd element from the list
list.printList();
// prints 10 20 60 40
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » JavaScript中链接列表的完整指南
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » JavaScript中链接列表的完整指南
常见问题FAQ
- 没有金币/金币不足 怎么办?
- 本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
- 所有资源普通会员都能下载吗?
- 本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。