JavaScript中链接列表的完整指南

作者 : IT 大叔 本文共4039个字,预计阅读时间需要11分钟 发布时间: 2020-09-14

链表是一种顺序结构,其由被连接到彼此以线性顺序的项目的序列构成。

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中链接列表的完整指南

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论