javascript ·

JavaScript实现单向链表数据结构

学习过数据结构的人都应该清楚,链表是一种动态的数据结构,这意味着我们可以从中任意添加或移除项,它会按需进行扩容。链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。下图展示了一个链表的结构:
JavaScript实现单向链表数据结构
相对于传统的数组,链表的一个好处在于,添加或移除元素的时候不需要移动其他元素。然而,链表需要使用指针,因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素,而要想访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素。

在我们现实生活中类似于链表这种数据结构的有很多,比如手表的表链,坦克的履带,火车等。想在其中插入一节需要先断开两节之间的联系,插入之后,将新插入的和之前的两个节点分别在联系起来。

创建一个链表

在原生的js中没有链表这么一个存储结构,需要我们来进行手动创建,下面我们来创建一下链表的基本骨架:

function LinkedList(){
    var Node = function(element){
        this.element = element;
        this.next = null;
    }
    var length = 0;
    var head = null;
}

在骨架中,我们需要一个Node类来作为基础节点,每一个节点都是通过new Node来实现的,length用来存储整个链表的长度,head指向链表的头。

然后我们需要实现以下链表的基本功能:

  • append(element):向列表尾部添加一个新的项
  • insert(position, element):向列表的特定位置插入一个新的项,返回最终插入的位置
  • remove(element):从列表中移除一项,移除成功返回true,如果链表中没有该元素则返回false
  • indexOf(element):返回元素在列表中的索引。如果列表中没有该元素则返回-1
  • removeAt(position):从列表的特定位置移除一项
  • isEmpty():如果链表中不包含任何元素,返回true,如果链表长度大于0则返回false
  • size():返回链表包含的元素个数。与数组的length属性类似
  • toString():由于列表项使用了Node类,就需要重写继承自JavaScript对象默认的toString方法,让其只输出元素的值

append方法

append方法实现的是向链表的末尾添加一个元素,如果链表长度为0,则直接首元素就是该添加的元素,具体实现方式如下:

this.append = function(element){
    var node = new Node(element);
    var current = null;
    if(head==null){
        //此时链接长度为空,直接插入为首元素
        head = node;
    }else{
        current = head;
        while(current.next!=null){
            //遍历查找链表,直到找到最后一个元素
            current = current.next;
        }
        current.next = node;
    }
    //更新链表长度
    length++;
}

添加时首先要判断的是链表长度是否为空,也就是head首元素是否为null,也可以判断length是否为0。我们创建的Node类中next始终null,代表的是新创建的元素为末尾元素,其next为null,如果next不为空,则说明该值不是末尾元素,这为添加末尾元素时提供了判断依据。

insert方法

向列表的特定位置插入一个新的项,返回最终插入的位置,我们来看一下实现代码:

this.insert = function(position,element){
    try{
        position = parseInt(position);
        if(isNaN(position)||position>length){
            //position为非数字或者长度大于链表长度,则position位置为末尾插入
            position = length;
        }else if(position<0){
            //如果小于0,则默认插入链表顶部
            position = 0;
        }
        var node = new Node(element);
        var current = head,index = 0,previous = null;
        if(position==0){
            node.next = current;
            head = node;
        }else{
            while(index++<position){
                previous = current;
                current = previous.next;
            }
            node.next = current;
            previous.next = node;

        }
        length++;
        return position;
    }catch(e){
        console.log(e)
    }

}

插入方法需要检测判断一下这个position是否合法,如果是非数字或者数值大于链表长度,则默认添加到链表的尾部,如果数值小于0,则默认添加到链表的头部,然后则是创建一个节点,之后遍历链表,查找到其合适位置进行插入,最后更新链表长度,并将插入位置返回。

实现效果如图所示:
JavaScript实现单向链表数据结构

removeAt方法

从链表中特定位置移除元素和插入元素一样都需要判断position是否合法,但是该方法不能默认值,只要不合法就不能进行删除操作,以防误删数据,不存在的位置直接返回false,否则返回true,具体实现代码如下:

this.removeAt(position){
    try{
        position = parseInt(position);
        if(isNaN(position)||position>length||position<0){
            return false
        }
        var current = head,index = 0,previous = null;
        if(length==0){
            return false;
        }else if(position==0){
            head = current.next;
        }else{
            while(index++<position){
                previous = current;
                current = previous.next;
            }
            previous.next = current.next;
        }
        length--;
        return true;
    }catch(e){
        console.log(e);
        return false;
    }
}

indexOf方法

indexOf方法返回元素在列表中的索引,如果列表中没有该元素则返回-1。传入的参数是元素本身,我们需要对元素本身进行查找匹配,这里的元素有可能存储的是基本数据类型,也有可能是引用数据类型,这里我们需要进行区分。我们来看一下实现代码:

this.indexOf = function(element){
    var current = head;
    var index = -1;

    while(current){
        index++;
        if(current.element instanceof Object&& JSON.stringify(current.element)==JSON.stringify(element)){
            return index
        }else if(!(current.element instanceof Object)&&current.element==element){
            return index;
        }
        current = current.next;
    }

    return index;
}

remove方法

remove方法就很简单了,我们可以借助上面的indexOf和removeAt方法来进行实现,首先通过indexOf来获取元素位置,然后通过removeAt方法来进行删除操作,下面来看示例代码:

this.remove = function(element){
    var index = this.indexOf(element);
    if(index = -1){
        return false;
    }
    return this.removeAt(index);
}

isEmpty方法

这个方法很容易实现了,只需要判断他的length即可:

this.isEmpyt = function(){
    return length==0
}

size方法

这个方法和上面那个判断类似,只需要将length返回即可:

this.size = function(){
    return length;
}

参与评论