LinkedList在Javascript中的实现-yiteyi-C++库

在本文中，我们将实现链表 Javascript中的数据结构。LinkedList是一种动态数据结构，我们可以轻松添加或删除元素，甚至可以根据需要进行扩展。与数组一样，链表按顺序存储元素，但不像数组那样连续存储元素。现在，我们来看一个链表节点的示例：

null

Javascript

                           // User defined class node                         
                           class Node {                         
                                                     // constructor                         
                                                     constructor(element)                         
                                                     {                         
                                                     this                                        .element = element;                         
                                                     this                                        .next =                                        null                         
                                                     }                         
                           }                         

在上面的代码中，我们定义了一个类节点有两个属性：要素和 下一个 . 要素保存节点的数据时 下一个 保存指向下一个节点的指针，该节点初始化为空值。现在，让我们看看链表类的一个实现：

Javascript

                           // linkedlist class                         
                           class LinkedList {                         
                                                     constructor()                         
                                                     {                         
                                                     this                                        .head =                                        null                                        ;                         
                                                     this                                        .size = 0;                         
                                                     }                         
            
                                                     // functions to be implemented                         
                                                     // add(element)                         
                                                     // insertAt(element, location)                         
                                                     // removeFrom(location)                         
                                                     // removeElement(element)                         
            
                                                     // Helper Methods                         
                                                     // isEmpty                         
                                                     // size_Of_List                         
                                                     // PrintList                         
                           }                         

上面的例子显示了一个链表类，它有一个构造函数和一系列要实现的方法。链表类有两个属性：即。头和大小，在哪里头存储列表的第一个节点，以及大小指示列表中的节点数。让我们实现以下每个功能：

1.添加（元素） –它会在列表末尾添加一个元素。

Javascript

                           // 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++;                         
                           }                         

为了在列表末尾添加一个元素，我们考虑如下：

如果列表为空，则添加一个元素，它将为head
如果列表不是空的，则迭代到列表末尾，并在列表末尾添加一个元素

2.插入（元素、索引） –它插入一个要素至少指数在列表中。

Javascript

                           // insert element at the position index                         
                           // of the list                         
                           insertAt(element, index)                         
                           {                         
                                                     if                                        (index < 0 || index >                                        this                                        .size)                         
                                                     return                                        console.log(                                        "Please enter a valid index."                                        );                         
                                                     else                                        {                         
                                                     // creates a new node                         
                                                     var                                        node =                                        new                                        Node(element);                         
                                                     var                                        curr, prev;                         
            
                                                     curr =                                        this                                        .head;                         
            
                                                     // add the element to the                         
                                                     // first index                         
                                                     if                                        (index == 0) {                         
                                                     node.next =                                        this                                        .head;                         
                                                     this                                        .head = node;                         
                                                     }                                        else                                        {                         
                                                     curr =                                        this                                        .head;                         
                                                     var                                        it = 0;                         
            
                                                     // iterate over the list to find                         
                                                     // the position to insert                         
                                                     while                                        (it < index) {                         
                                                     it++;                         
                                                     prev = curr;                         
                                                     curr = curr.next;                         
                                                     }                         
            
                                                     // adding an element                         
                                                     node.next = curr;                         
                                                     prev.next = node;                         
                                                     }                         
                                                     this                                        .size++;                         
                                                     }                         
                           }                         

为了在列表的给定索引中添加元素，我们考虑如下三个条件：

如果索引为零，我们在列表的前面添加一个元素，使其成为标题
如果索引是列表的最后一个位置，我们将元素附加到列表的末尾
如果索引在0或size–1之间，我们迭代到该索引，并在该索引处添加一个元素

3.删除（索引） –它从指定的列表中删除并返回一个元素指数

Javascript

                           // removes an element from the                         
                           // specified location                         
                           removeFrom(index)                         
                           {                         
                                                     if                                        (index < 0 || index >=                                        this                                        .size)                         
                                                     return                                        console.log(                                        "Please Enter a valid index"                                        );                         
                                                     else                                        {                         
                                                     var                                        curr, prev, it = 0;                         
                                                     curr =                                        this                                        .head;                         
                                                     prev = curr;                         
            
                                                     // deleting first element                         
                                                     if                                        (index === 0) {                         
                                                     this                                        .head = curr.next;                         
                                                     }                                        else                                        {                         
                                                     // iterate over the list to the                         
                                                     // position to removce an element                         
                                                     while                                        (it < index) {                         
                                                     it++;                         
                                                     prev = curr;                         
                                                     curr = curr.next;                         
                                                     }                         
            
                                                     // remove the element                         
                                                     prev.next = curr.next;                         
                                                     }                         
                                                     this                                        .size--;                         
            
                                                     // return the remove element                         
                                                     return                                        curr.element;                         
                                                     }                         
                           }                         

为了从列表中删除一个元素，我们考虑三个条件：

如果索引为0，那么我们移除头部并使下一个节点成为列表的头部
如果索引是size–1，那么我们从列表中删除最后一个元素，并使prev成为最后一个元素
如果在0到size–1之间，我们使用prev和当前节点删除元素

4.移除元素（元素） –这种方法可以消除要素从名单上。它返回已删除的元素，如果找不到，则返回-1。

Javascript

                           // removes a given element from the                         
                           // list                         
                           removeElement(element)                         
                           {                         
                                                     var                                        current =                                        this                                        .head;                         
                                                     var                                        prev =                                        null                                        ;                         
            
                                                     // iterate over the list                         
                                                     while                                        (current !=                                        null                                        ) {                         
                                                     // comparing element with current                         
                                                     // element if found then remove the                         
                                                     // and return true                         
                                                     if                                        (current.element === element) {                         
                                                     if                                        (prev ==                                        null                                        ) {                         
                                                     this                                        .head = current.next;                         
                                                     }                                        else                                        {                         
                                                     prev.next = current.next;                         
                                                     }                         
                                                     this                                        .size--;                         
                                                     return                                        current.element;                         
                                                     }                         
                                                     prev = current;                         
                                                     current = current.next;                         
                                                     }                         
                                                     return                                        -1;                         
                           }                         

上述方法只是对 移除（索引） ，而不是从指定位置将其删除

帮助方法

让我们声明一些在使用LinkedList时有用的助手方法。

1.索引（元素） –如果元素在列表中，则返回给定元素的索引。

Javascript

                           // finds the index of element                         
                           indexOf(element)                         
                           {                         
                                                     var                                        count = 0;                         
                                                     var                                        current =                                        this                                        .head;                         
            
                                                     // iterate 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。

2.我空虚 –如果列表为空，则返回true。

Javascript

                           // checks the list for empty                         
                           isEmpty()                         
                           {                         
                                                     return                                        this                                        .size == 0;                         
                           }                         

在这种方法中，我们检查大小财产链表类，如果为零，则列表为空。

3.列表的大小（） –它返回列表的大小

Javascript

                           // gives the size of the list                         
                           size_of_list()                         
                           {                         
                                                     console.log(                                        this                                        .size);                         
                           }                         

3.打印列表（） –它打印列表的内容。

Javascript

                           // prints the list items                         
                           printList()                         
                           {                         
                                                     var                                        curr =                                        this                                        .head;                         
                                                     var                                        str =                                        ""                                        ;                         
                                                     while                                        (curr) {                         
                                                     str += curr.element +                                        " "                                        ;                         
                                                     curr = curr.next;                         
                                                     }                         
                                                     console.log(str);                         
                           }                         

在这个方法中，我们迭代整个列表，连接每个节点的元素并打印它。

注：可以在中声明不同的helper方法链表按要求上课。

实施

现在，让我们使用LinkedList类及其上面描述的不同方法。

Javascript

                           // creating an object for the                         
                           // Linkedlist class                         
                           var                                        ll =                                        new                                        LinkedList();                         
            
                           // testing isEmpty on an empty list                         
                           // returns true                         
                           console.log(ll.isEmpty());                         
            
                           // adding element to the list                         
                           ll.add(10);                         
            
                           // prints 10                         
                           ll.printList();                         
            
                           // returns 1                         
                           console.log(ll.size_of_list());                         
            
                           // adding more elements to the list                         
                           ll.add(20);                         
                           ll.add(30);                         
                           ll.add(40);                         
                           ll.add(50);                         
            
                           // returns 10 20 30 40 50                         
                           ll.printList();                         
            
                           // prints 50 from the list                         
                           console.log(                                        "is element removed ?"                                        + ll.removeElement(50));                         
            
                           // prints 10 20 30 40                         
                           ll.printList();                         
            
                           // returns 3                         
                           console.log(                                        "Index of 40 "                                        + ll.indexOf(40));                         
            
                           // insert 60 at second position                         
                           // ll contains 10 20 60 30 40                         
                           ll.insertAt(60, 2);                         
            
                           ll.printList();                         
            
                           // returns false                         
                           console.log(                                        "is List Empty ? "                                        + ll.isEmpty());                         
            
                           // remove 3rd element from the list                         
                           console.log(ll.removeFrom(3));                         
            
                           // prints 10 20 60 40                         
                           ll.printList();                         

完整代码：

Javascript

                         class Node {                       
                                                 // constructor                       
                                                 constructor(element) {                       
                                                 this                                     .element = element;                       
                                                 this                                     .next =                                     null                       
                                                 }                       
                         }                       
                         // linkedlist class                       
                         class LinkedList {                       
                                                 constructor() {                       
                                                 this                                     .head =                                     null                                     ;                       
                                                 this                                     .size = 0;                       
                                                 }                       
           
                                                 // 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++;                       
                                                 }                       
           
                                                 // insert element at the position index                       
                                                 // of the list                       
                                                 insertAt(element, index) {                       
                                                 if                                     (index < 0 || index >                                     this                                     .size)                       
                                                 return                                     console.log(                                     "Please enter a valid index."                                     );                       
                                                 else                                     {                       
                                                 // creates a new node                       
                                                 var                                     node =                                     new                                     Node(element);                       
                                                 var                                     curr, prev;                       
           
                                                 curr =                                     this                                     .head;                       
           
                                                 // add the element to the                       
                                                 // first index                       
                                                 if                                     (index == 0) {                       
                                                 node.next =                                     this                                     .head;                       
                                                 this                                     .head = node;                       
                                                 }                                     else                                     {                       
                                                 curr =                                     this                                     .head;                       
                                                 var                                     it = 0;                       
           
                                                 // iterate over the list to find                       
                                                 // the position to insert                       
                                                 while                                     (it < index) {                       
                                                 it++;                       
                                                 prev = curr;                       
                                                 curr = curr.next;                       
                                                 }                       
           
                                                 // adding an element                       
                                                 node.next = curr;                       
                                                 prev.next = node;                       
                                                 }                       
                                                 this                                     .size++;                       
                                                 }                       
                                                 }                       
           
                                                 // removes an element from the                       
                                                 // specified location                       
                                                 removeFrom(index) {                       
                                                 if                                     (index < 0 || index >=                                     this                                     .size)                       
                                                 return                                     console.log(                                     "Please Enter a valid index"                                     );                       
                                                 else                                     {                       
                                                 var                                     curr, prev, it = 0;                       
                                                 curr =                                     this                                     .head;                       
                                                 prev = curr;                       
           
                                                 // deleting first element                       
                                                 if                                     (index === 0) {                       
                                                 this                                     .head = curr.next;                       
                                                 }                                     else                                     {                       
                                                 // iterate over the list to the                       
                                                 // position to removce an element                       
                                                 while                                     (it < index) {                       
                                                 it++;                       
                                                 prev = curr;                       
                                                 curr = curr.next;                       
                                                 }                       
           
                                                 // remove the element                       
                                                 prev.next = curr.next;                       
                                                 }                       
                                                 this                                     .size--;                       
           
                                                 // return the remove element                       
                                                 return                                     curr.element;                       
                                                 }                       
                                                 }                       
           
                                                 // removes a given element from the                       
                                                 // list                       
                                                 removeElement(element) {                       
                                                 var                                     current =                                     this                                     .head;                       
                                                 var                                     prev =                                     null                                     ;                       
           
                                                 // iterate over the list                       
                                                 while                                     (current !=                                     null                                     ) {                       
                                                 // comparing element with current                       
                                                 // element if found then remove the                       
                                                 // and return true                       
                                                 if                                     (current.element === element) {                       
                                                 if                                     (prev ==                                     null                                     ) {                       
                                                 this                                     .head = current.next;                       
                                                 }                                     else                                     {                       
                                                 prev.next = current.next;                       
                                                 }                       
                                                 this                                     .size--;                       
                                                 return                                     current.element;                       
                                                 }                       
                                                 prev = current;                       
                                                 current = current.next;                       
                                                 }                       
                                                 return                                     -1;                       
                                                 }                       
           
           
                                                 // finds the index of element                       
                                                 indexOf(element) {                       
                                                 var                                     count = 0;                       
                                                 var                                     current =                                     this                                     .head;                       
           
                                                 // iterate 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;                       
                                                 }                       
           
                                                 // checks the list for empty                       
                                                 isEmpty() {                       
                                                 return                                     this                                     .size == 0;                       
                                                 }                       
           
                                                 // gives the size of the list                       
                                                 size_of_list() {                       
                                                 console.log(                                     this                                     .size);                       
                                                 }                       
           
           
                                                 // prints the list items                       
                                                 printList() {                       
                                                 var                                     curr =                                     this                                     .head;                       
                                                 var                                     str =                                     ""                                     ;                       
                                                 while                                     (curr) {                       
                                                 str += curr.element +                                     " "                                     ;                       
                                                 curr = curr.next;                       
                                                 }                       
                                                 console.log(str);                       
                                                 }                       
           
                         }                       
           
                         // creating an object for the                       
                         // Linkedlist class                       
                         var                                     ll =                                     new                                     LinkedList();                       
           
                         // testing isEmpty on an empty list                       
                         // returns true                       
                         console.log(ll.isEmpty());                       
           
                         // adding element to the list                       
                         ll.add(10);                       
           
                         // prints 10                       
                         ll.printList();                       
           
                         // returns 1                       
                         console.log(ll.size_of_list());                       
           
                         // adding more elements to the list                       
                         ll.add(20);                       
                         ll.add(30);                       
                         ll.add(40);                       
                         ll.add(50);                       
           
                         // returns 10 20 30 40 50                       
                         ll.printList();                       
           
                         // prints 50 from the list                       
                         console.log(                                     "is element removed ?"                                     + ll.removeElement(50));                       
           
                         // prints 10 20 30 40                       
                         ll.printList();                       
           
                         // returns 3                       
                         console.log(                                     "Index of 40 "                                     + ll.indexOf(40));                       
           
                         // insert 60 at second position                       
                         // ll contains 10 20 60 30 40                       
                         ll.insertAt(60, 2);                       
           
                         ll.printList();                       
           
                         // returns false                       
                         console.log(                                     "is List Empty ? "                                     + ll.isEmpty());                       
           
                         // remove 3rd element from the list                       
                         console.log(ll.removeFrom(3));                       
           
                         // prints 10 20 60 40                       
                         ll.printList();                       

输出：

 true 10 1 undefined 10 20 30 40 50 is element removed ?50 10 20 30 40 Index of 40 3 10 20 60 30 40 is List Empty ? false 30 10 20 60 40

JavaScript最为人所知的是网页开发，但它也用于各种非浏览器环境。通过以下步骤，您可以从头开始学习JavaScript JavaScript教程和 JavaScript示例 .

本文由 苏米特·戈什 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

Javascript