阅读 11

数据结构-链表

前言

我们前面栈和队列实质上使用数组这种结构实现的,在存储上数组元素的物理地址都是连续,而多个的数组存贮因为地址不连续就会造成多个内存片段冗余,有很多空白的内存空间被浪费,为避免资源浪费,链表应运而生。

链表特性

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。一般的链表节点包括表内容、指向下个节点的指针。如下图:

链表实现思路

链表的实现: 包括节点的定义(借助辅助类:节点内容和一个节点的指向)、各个节点如何串连起来(在上个节点里保存下个节点的指向信息)、然后实现基本的添加,删除功能即可。注意表尾下个节点指向为空。

代码实现

var LinkedList = function(){
    // 表头
    var head = null;
    // 表长度
    var length = 0;

    // 节点定义
    var Node = function(element, next){
        this.element = element;
        this.next = null;
    }

    // 尾部添加
    this.append = function(element){
        // 创建新节点
        var node = new Node(element);
        // 当链表头为空,说明链表为空,则将新元素赋值给表头
        if(head == null){
            head = node;
        }else{
            var current = head;
            while(current.next){
                current = current.next;
            }
            /** while 循环结束,current已经是最后一项了 */
            current.next = node;
        }
        length++;
    }

    // 获取表头
    this.getHead = function(){
        return head;
    }

    // 插入
    this.insert = function(position, element){
        // 不越界
        if(position>-1 && position<length){
            var node = new Node(element);
            if(position === 0){
                // 替换头部
                let current = head;
                head = node;
                head.next = current;
            }else{
                let index = 0;
                let current = head;
                let previous = null;
                while(current.next && index != position){
                    previous = current;
                    current = current.next;
                    index++;
                }
                // 在previous与current间插入node
                previous.next = node;
                node.next = current;
            }
            length++;
        }
    }

    // 按位置删除
    this.removeAt = function(position){
        if(position>-1 && position<length){
            // 删除第一个
            if(position === 0){
                let current = head;
                // 第二个节点覆盖一个
                head = current.next;
            }else{
                let current = head;
                let previous = null;
                let index = 0;
                while(current.next && index != position){
                    previous = current;
                    current = current.next;
                    index++;
                }
                previous.next = current.next;
            }
            length--;
            // 返回删除元素
            return current;
        }
        return null;
    }

    // 查找元素索引
    this.indexOf = function(element){
      let current = head;
      let index = 0;
      while(current){
          if(current.element == element){
              return index;
          }
          current = current.next;
          index++;
      }
      // 找不到返回-1
      return -1;
    }

    // 移除元素
    this.remove = function(element){
        return this.removeAt(this.indexOf(element))
    }

     // 是否为空
    this.isEmpty = function(){
        return length === 0;
    }
    // 长度
    this.size = function(){
        return length;
    }
}

复制代码

链表是一种比较特殊的数据结构,链式结构也导致了元素移除是一件比较容易的实情(改变链接的指向),不像线性结构那样得移动大量的元素。同时不必将元素保存在连续的地址上,避免了碎片化造成不必要的空间浪费。

关注下面的标签,发现更多相似文章
评论