JavaScript数据结构及算法---链表

前言

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成。 相较于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。在数组中，我们可以直接访问任何位置的任何元素，而想要访问链表中间的元素，需要从起点开始迭代直到迭代链表找到所需的元素。

链表的数据结构

接下来，我们来分析链表的数据结构，在开始前，我们要实现两个辅助方法defaultEquals和节点类Node。以下是代码实现：

Node类

class Node{
          
   
    constructor(element){
          
   
        this.element = element
        this.next = undefined
    }
}

defaultEquals方法

export function defaultEquals(a, b){
          
   
    return a == b;
}

接下来是最重要的LinkedList类

export default class LinkedList {
          
   
    constructor(equalsFn = defaultEquals){
          
   
        this.count = 0;
        this.head = undefined;
        this.equalsFn = equalsFn;
    }
}

接下来就是实现LinkedList类的方法了。 push(element) ： 向链表添加一个新元素。 insert(element，position): 向链表的指定位置插入一个新元素。 getElementAt（index）：返回链表中特定位置的元素。如果链表中不存在这样的元素则返回undefined。 remove（element）：从列表中移除一个元素。 indexOf （element）：返回元素在链表中的索引。如果链表中没有则返回-1。 removeAt（position）：从链表的指定位置移除一个元素。 isEmpty（）：如果链表中不包含任何元素，返回true,如果链表长度大于0则返回false。 size（）：返回链表包含的元素个数，与数组的length属性相似。 toString（）： 返回表示的元素个数。 下面，我们来实现push和removeAt两个方法。

push方法 向链表尾部添加元素

分析： 向链表中添加元素会出现两种情况： （1）向空链表中添加元素时，此时的head指针指向undefined或null。我们要做的事是让head元素指向node元素。下一个node元素会自动成为undefined。 （2）向一个不为空的链表尾部添加元素，首先我们要找到最后一个元素，通过循环遍历当前节点的下一个节点是否是undefined或null来找最后一个元素。

push(element){
          
   
        const node = new Node(element)
        let current ;
        if ( this.head == null){
          
   
            this.head = node ;
        }else{
          
   
            current = this.head ;
            while(current.next != null){
          
   
                current = current.next;
            }
            current.next = node;
        }
        this.count ++;
    }

removeAt方法 从链表中移除元素

分析： 从链表中移除元素也分两种情况 （1）移除链表第一个元素，要做的事让head指向链表的第二个元素 （2）移除链表的元素不是第一个，我们就需要遍历链表找到元素并移除。

removeAt(index){
          
   
        if( index >= 0 && index < this.count){
          
   
            let current = this.head

            if(index == 0){
          
   
                this.head = current.next
            }else{
          
   
                let previous
                for(let i = 0; i < index; i ++){
          
   
                    previous = current
                    current = current.next
                }
                previous.next = current.next
            }
            this.count --
            return current.element
        }

        return undefined
    }

总结

今天，我们初步了解了链表的基本数据结构，熟悉链表的基本结构对于我们学习前端中的数据结构有较大的帮助。小伙伴们，走过路过，留下你们的赞吧~