最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • 数据结构(链表)

    正文概述 掘金(浅梦G浮生)   2021-02-20   670

    一、什么是链表

    链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。可以参考火车,由一节一节车厢链接起来。   相对于传统的数组,链表的一个好处在于,添加或移除元素的时候不需要移动其他元素。然而,链表需要使用指针,因此实现链表是需要额外注意。在数组中我们可以直接访问任何位置的任何元素,而要想访问链表中间的一个元素,则需要从起点(表头)开始迭代链表直到找到所需的元素。

    数据结构(链表)

    二、创建链表

    • 1、LinkedList类的骨架
    import { defaultEquals } from '../util'; // 判断两个元素是否相等
    import { Node } from '../util'; // 创建元素节点
    class LinkedList {
     // 可以自定义传入比较元素相等的方法,如果没有使用defaultEquals
     constructor(equalsFn = defaultEquals) {
         this.count = 0; // 存储链表数量
         this.head = undefined; // 第一个元素
         his.equalsFn = equalsFn; // 判断两个元素是否相等
     }
     push(element) {} // 向链表尾部添加一个新元素
     insert(element,position) {} // 向链表特定位置插入一个新元素
     getElementAt(index) {} // 返回链表特定位置的元素
     remove(element) {} // 从链表中移除一个元素
     indexOf() {} // 返回元素在链表中的索引,没有则返回-1
     removeAt(position) {} // 从链表特定位置移除一个元素
     isEmpty() {} // 判断链表是否为空
     size() {} // 返回链表包含的元素个数
     toString() {} // 返回整个链表的字符串
    }
    
    
    • 2、defaultEquals和Node
    export function defaultEquals(a, b) {
     return a === b
    }
    export class Node {
     constructor(element) {
       this.element = element;
       this.next = undefined;
     }
    }
    
    

    三、实现链表的每一个方法

    • 1、push尾部添加元素
      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;
          }
          // 将next赋值为新元素,建立链接
          current.next = node;
        }
        this.count ++;
      }
    
    
    • 2、insert任意处添加元素
      insert(element, index) {
        if (index >= 0 && index <= this.count) {
          const node = new Node(element);
          if (index === 0) { // 在第一个位置添加
            const current = this.head;
            node.next = current;
            this.head = node;
          } else {
            const previous = this.getElementAt(index - 1);
            const current = previous.next;
            node.next = current;
            previous.next = node;
          }
          this.count ++;
          return true;
        }
        return false;
      }
    
    
    • 3、getElementAt查找元素位置
      getElementAt(index) {
        if (index >= 0 && index < this.count) {
          let node = this.head;
          for (let i = 0; i < index && node != null; i++) {
            node = node.next;
          }
          return node;
        }
        return undefined;
      }
    
    
    
    • 4、removeAt从指定位置移除元素
      // 从链表中移除元素,并返回移除项
      removeAt(index) {
        // 检查越界值
        if (index >= 0 && index < this.count) {
          let current = this.head;
          // 移除第一项
          if (index === 0) {
            this.head = current.next;
          } else {
            const previous = this.getElementAt(index - 1);
            current = previous.next;
            previous.next = current.next;
          }
          this.count--;
          return current.element;
        }
        return undefined;
      }
    
    • 5、indexOf
    // 查找元素位置
      indexOf(element) {
        let current = this.head;
        for (let i = 0; i < this.count && current != null; i++) {
          if (this.equalsFn(element, current.element)) {
            return i;
          }
          current = current.next;
        }
        return -1;
      }
    
    • 6、remove删除指定元素
      // 从链表中移除元素
    remove(element) {
      const index = this.getElementAt(element);
      return this.removeAt(index);
    }
    
    • 7、isEmpty判断链表是否为空
    isEmpty() {
      return this.size() === 0;
    }
    
    
    • 8、toString 将链表转化为字符串
    toString() {
      if (this.head == null) {
        return '';
      }
      let objString = `${this.head.element}`;
      let current = this.head.next;
      for (let i = 1; i < this.size() && current != null; i ++) {
        objString = `${objString},${current.element}`;
        current = current.next;
      }
      return objString;
    }
    
    
    • 9、size返回链表长度
    size() {
      return this.count;
    }
    
    const list = new LinkedList();
    list.push(12);
    list.push(11);
    list.push(13);
    list.push(14);
    list.insert(3, 3);
    list.removeAt(2);
    console.log(list);
    
    

    起源地下载网 » 数据结构(链表)

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元