my canteen
登录       注册

您现在的位置是:网站首页 > 学无止境

数据结构之链表结构

王伟2020年8月18日8927人围观
简介认识队列结构 使用ES6语法对链表结构进行封装

数据结构之链表结构

一. 认识链表

链表和数组

数组:

要存储多个元素,数组(或列表)可能是最常用的数据结构。
我们之前说过, 几乎每一种编程语言都有默认实现数组结构, 这种数据结构非常方便,提供了一个便利的[]语法来访问它的元素。
但是数组也有很多缺点:
  • 数组的创建通常需要申请一段连续的内存空间(一整块的内存), 并且大小是固定的(大多数编程语言数组都是固定的), 所以当当前数组不能满足容量需求时, 需要扩容. (一般情况下是申请一个更大的数组, 比如2倍. 然后将原数组中的元素复制过去)
  • 而且在数组开头或中间位置插入数据的成本很高, 需要进行大量元素的位移.(尽管我们已经学过的JavaScript的Array类方法可以帮我们做这些事,但背后的原理依然是这样)。

链表

要存储多个元素, 另外一个选择就是使用链表.
但不同于数组, 链表中的元素在内存中不必是连续的空间.
链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针或者链接)组成.
相对于数组, 链表有一些优点:
  • 内存空间不是比是连续的. 可以充分利用计算机的内存. 实现灵活的内存动态管理.
  • 链表不必在创建时就确定大小, 并且大小可以无限的延伸下去.
  • 链表在插入和删除数据时, 时间复杂度可以达到O(1). 相对数组效率高很多.
相对于数组, 链表有一些缺点:
  • 链表访问任何一个位置的元素时, 都需要从头开始访问.(无法跳过第一个元素访问任何一个元素).
  • 无法通过下标直接访问元素, 需要从头一个个访问, 直到找到对应的问题.

什么是链表呢?

  • 其实上面我们已经简单的提过了链表的结构, 我们这里更加详细的分析一下.
  • 链表类似于火车: 有一个火车头, 火车头会连接一个节点, 节点上有乘客, 并且这个节点会连接下一个节点, 以此类推.
  • 链表的火车结构:

- 链表的数据结构:

二. 链表封装

创建链表类

封装一个链表节点
export class Node {
  constructor(ele) {
    this.ele = ele;
    this.next = null
  }
}
创建一个链表类
class LinkedList {
  constructor() {
    this.head = null
    this.length = 0
  }

链表常见操作

我们先来认识一下, 链表中应该有哪些常见的操作
  • append(element):向列表尾部添加一个新的项
  • insert(position, element):向列表的特定位置插入一个新的项。
  • remove(element):从列表中移除一项。
  • indexOf(element):返回元素在列表中的索引。如果列表中没有该元素则返回-1。
  • removeAt(position):从列表的特定位置移除一项。
  • isEmpty():如果链表中不包含任何元素,返回true,如果链表长度大于0则返回false。
  • size():返回链表包含的元素个数。与数组的length属性类似。
  • get(position):根据位置获取元素
  • update(element,position):更新元素
append方法实现
  • 首先需要做的是将element传入方法, 并根据element创建一个Node节点.
  • 场景一: 链表本身是空的, 比如这种情况下我们插入了一个15作为元素.

- 场景二: 链表中已经有元素了, 需要向最后的节点的next中添加节点.

append(ele) {
    const node = new Node(ele)
    if (!this.head) {
      this.head = node
    } else {
      let current = this.head
      while (current.next) {
        // current 指向最后节点
        current = current.next
      }
      current.next = node
    }
    this.length++
  }
insert方法实现
  • 1.检测越界问题: 越界插入失败
  • 2.找到正确的位置, 并且插入数据
  • 3.判断是否列表是否在第一个位置插入
insert(ele, position) {
     // 1.检测越界问题: 越界插入失败
    if (position < 0 || position > this.length) {
      return false
    }
    // 2.找到正确的位置, 并且插入数据
    const node = new Node(ele)
    // 3.判断是否列表是否在第一个位置插入
    if (position == 0) {
      node.next = this.head
      this.head = node
    } else {
      let index = 0;
      let current = this.head;
      let previous = null;
      while (index < position) {
        index++
        previous = current
        current = current.next
      }
      previous.next = node
      node.next = current
    }
    this.length++
    return true

  }
removeAt方法实现
  • 代码1部分, 还是越界的判断.
  • 代码2进行判断, 移除第一项和其他项的方式不同
  • 移除第一项时, 直接让head指向第二项信息就可以啦.

- 首先, 我们需要通过while循环, 找到正确的位置. - 找到正确位置后, 就可以直接将上一项的next指向current项的next, - 这样中间的项就没有引用指向它, 也就不再存在于链表后, 会面会被回收掉.

removeAt(position) {
    // 1.检测越界问题: 越界移除失败, 返回null
    if (position < 0 || position > this.length - 1) {
      return null
    }
    let current = this.head;
    let index = 0
    let previous = null;
    // 2.判断是否是移除第一项
    if (position === 0) {
      this.head = current.next
    } else {
      while (index++ < position) {
        previous = current
        current = current.next
      }
      previous.next = current.next
    }
    this.length--
    return current.ele
  }
indexof方法实现
  • 通过节点获取元素和element进行对比, 如果和传入element相同, 表示找到, 直接返回index即可.
  • 如果没有找到, index++, 并且指向下一个节点.
  • 到最后都没有找到, 说明链表中没有对应的元素, 那么返回-1即可.
indexOf(ele) {
    let current = this.head
    let index = 0
    while (current) {
      if (current.ele === ele) {
        return index
      }
      current = current.next
      index ++
    }
    return -1
  }
remove方法实现
  • 根据indexof获取位置删除元素
remove(ele) {
    let index = this.indexOf(ele)
    if (index != -1) {
      this.removeAt(index)
      return ele
    } else {
      return null
    } 
  }
get 方法
  • 代码1部分, 判断是否越界
  • 通过while循环 找到对应位置的元素
get(position) {
    //代码1部分, 判断是否越界
    if (position < 0 || position > this.length - 1) {
      return null
    } else {
      let current = this.head
      let index = 0
      while (index++ < position) {
        current = current.next
      }
      return current.ele
    }
  }
update方法
  • 根据removeAt删除元素
  • 根据insert 插入元素
update(ele,position) {
    if (position < 0 || position > this.length - 1) {
      return null
    } else {
      this.removeAt(position)
      this.insert(position,ele)
    }
  }
isEmpty方法
isEmpty() {
    if (this.length === 0) {
      return true
    }
    return false
  }
size方法
size() {
    return this.length
  }

单向链表封装完成

路漫漫其修远兮,吾将上下而求索!


文章评论

来说句话吧.... 共有评论数:0条


微信二维码 博主微信 qq二维码 博主QQ
177****8743
7*24小时电话