您现在的位置是：首页 > 前端

当前栏目

JavaScript：封装单向链表10种常见的操作方法

JavaScript 封装链表 10 常见操作方法单向

2023-09-27 14:22:47 时间

链表的优势
1.要存储多个元素的时候，除了数组还可以选择链表。
2.与之数组不同的是，链表中的元素在内存中不必是连续的空间。
3.链表中的每个元素由一个存储元素本身的节点和一个指向下一个节点的引用(指针或者连接)组成。

相比于数组，链表有一些优点：
1.内存空间不用是连续的，这样可以充分利用计算机的内存，实现灵活的内存动态管理。
2.链表不用在创建的时候就确定大小，并且大小可以无限的延伸下去。
3.链表在插入和删除元素时，时间复杂度可以达到O(1)，相对于数组的时间复杂度来说效率更高。

单项链表常见的操作方法

1.append方法

LinkedList.prototype.append = function(data) {
  // 创建一个新节点
  var newNode = new Node(data)

  // 判断是否添加的是第一个节点
  if(this.length == 0){
    // 是第一个节点
    // var newNode = new Node(data)
    this.head = newNode
  } else {
    // 不是第一个节点-->找到最后一个节点
    // var newNode = new Node(data)
    var current = this.head
    while(current.next) {
      current = current.next
    }

  // 最后节点的next指向新的节点
  current.next = newNode
}

// length+1
this.length += 1

2.toString方法

LinkedList.prototype.toString = function() {
  // 定义变量
  var current = this.head
  var listString = ""

  // 循环获取链表所有的节点
  while(current) {
	listString += current.data + " "
	current = current.next
  }
  return listString
}

3.insert方法

LinkedList.prototype.insert = function(position,data) {
  // 对position进行越界判断
  if(position<0 || position>this.length){
	return false
  }
  // 根据data创建newNode
  var newNode = new Node(data)

  // 判断插入的位置是否是第一个
  if(position == 0) {
	newNode.next = this.head
	this.head = newNode
  } else {
	// 插入中间和最后通用的插入方法
	var index = 0
	var current = this.head
	var previous = null
	while(index++ < position) {
	  previous = current
	  current = current.next
    }
    newNode.next = current
    previous.next = newNode
  }
  // length+1
  this.length += 1
  return true
}

4.get方法

LinkedList.prototype.get = function(position) {
  // 越界判断
  if(position<0 || position>=this.length){
	return null
  }
  // 获取对应的data
  var current = this.head
  var index = 0
  while(index++ < position) {
	current = current.next
  }
  return current.data
}

5.indexOf方法

LinkedList.prototype.indexOf = function(data) {
  // 定义变量
  var current = this.head
  var index = 0

  // 开始查找遍历
  while(current) {
	if(current.data == data) {
	  return index
	}
	current = current.next
	index += 1
  }
  // 找到链表最后未找到该元素，返回-1
  return -1
}

6.update方法

LinkedList.prototype.update = function(position,newData) {
  // 越界判断
  if(position<0 || position>=this.length) {
	return false
  }

  // 查找正确的节点
  var current = this.head
  var index = 0
  while(index++ < position) {
	current = current.next
  }

  // 将position位置的node修改为新的值newData
  current.data = newData
  return true
}

7.removeAt方法

LinkedList.prototype.removeAt = function(position) {
  // 越界判断
  if(position<0 || position>=this.length) {
	return false
  }

  // 判断删除的是否第一个节点
  var current = this.head
  if(position == 0) {
	this.head = this.head.next
  } else {
	var index = 0
	// var current = this.head
	var previous = null
	while(index++ < position) {
	  previous = current
	  current = current.next
	}
	// 前一个节点的next指向current即可
	previous.next = current.next
  }
  // 删除完元素后链表长度需要进行length-1
  this.length -= 1
  // 表示删除成功
  // return true
  return current.data
 }

8.remove方法

LinkedList.prototype.remove = function(data) {
  // 获取data在链表中的位置
  var position = this.indexOf(data)

  // 根据位置信息删除所在的节点
  return this.removeAt(position)
}

9.isEmpty方法

LinkedList.prototype.isEmpty = function() {
  return this.length == 0
}

10.size方法

LinkedList.prototype.size = function() {
  return this.length
}

完整笔记代码

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>单向链表的封装</title>
</head>
<body>
  <script>
    // 封装链表的类
    function LinkedList() {
      // 内部的类：节点类
      function Node(data) {
        this.data = data
        this.next = null
      }

      // 属性
      this.head = null
      this.length = 0

      // 1.append方法
      LinkedList.prototype.append = function(data) {
        // 创建一个新节点
        var newNode = new Node(data)

        // 判断是否添加的是第一个节点
        if(this.length == 0){
          // 是第一个节点
          // var newNode = new Node(data)
          this.head = newNode
        } else {
          // 不是第一个节点-->找到最后一个节点
          // var newNode = new Node(data)
          var current = this.head
          while(current.next) {
            current = current.next
          }

          // 最后节点的next指向新的节点
          current.next = newNode
        }

        // length+1
        this.length += 1

        // 2.toString方法
        LinkedList.prototype.toString = function() {
          // 定义变量
          var current = this.head
          var listString = ""

          // 循环获取链表所有的节点
          while(current) {
            listString += current.data + " "
            current = current.next
          }
          return listString
        }

        // 3.insert方法
        LinkedList.prototype.insert = function(position,data) {
          // 对position进行越界判断
          if(position<0 || position>this.length){
            return false
          }
          // 根据data创建newNode
          var newNode = new Node(data)

          // 判断插入的位置是否是第一个
          if(position == 0) {
            newNode.next = this.head
            this.head = newNode
          } else {
            // 插入中间和最后通用的插入方法
            var index = 0
            var current = this.head
            var previous = null
            while(index++ < position) {
              previous = current
              current = current.next
            }
            newNode.next = current
            previous.next = newNode
          }
          // length+1
          this.length += 1
          return true
        }

        // 4.get方法
        LinkedList.prototype.get = function(position) {
          // 越界判断
          if(position<0 || position>=this.length){
            return null
          }
          // 获取对应的data
          var current = this.head
          var index = 0
          while(index++ < position) {
            current = current.next
          }
          return current.data
        }

        // 5.indexOf方法
        LinkedList.prototype.indexOf = function(data) {
          // 定义变量
          var current = this.head
          var index = 0

          // 开始查找遍历
          while(current) {
            if(current.data == data) {
              return index
            }
            current = current.next
            index += 1
          }
          // 找到链表最后未找到该元素，返回-1
          return -1
        }

        // 6.update方法
        LinkedList.prototype.update = function(position,newData) {
          // 越界判断
          if(position<0 || position>=this.length) {
            return false
          }

          // 查找正确的节点
          var current = this.head
          var index = 0
          while(index++ < position) {
            current = current.next
          }

          // 将position位置的node修改为新的值newData
          current.data = newData
          return true
        }

        // 7.removeAt方法
        LinkedList.prototype.removeAt = function(position) {
          // 越界判断
          if(position<0 || position>=this.length) {
            return false
          }

          // 判断删除的是否第一个节点
          var current = this.head
          if(position == 0) {
            this.head = this.head.next
          } else {
            var index = 0
            // var current = this.head
            var previous = null
            while(index++ < position) {
              previous = current
              current = current.next
            }
            // 前一个节点的next指向current即可
            previous.next = current.next
          }
          // 删除完元素后链表长度需要进行length-1
          this.length -= 1
          // 表示删除成功
          // return true
          return current.data
        }

        // 8.remove方法
        LinkedList.prototype.remove = function(data) {
          // 获取data在链表中的位置
          var position = this.indexOf(data)

          // 根据位置信息删除所在的节点
          return this.removeAt(position)
        }

        // 9.isEmpty方法
        LinkedList.prototype.isEmpty = function() {
          return this.length == 0
        }

        // 10.size方法
        LinkedList.prototype.size = function() {
          return this.length
        }
      }
    }
    // 测试代码
    // 创建LinkedList
    var list = new LinkedList()

    // 测试append方法
    list.append("xiaonaihu")
    list.append("hyw")
    list.append("lingxiaohu")
    alert(list)

    // 测试insert方法
    list.insert(0,"aaa")
    list.insert(3,"ccc")
    list.insert(5,"yyy")
    alert(list)

    // 测试get方法
    alert(list.get(0))
    alert(list.get(3))
    alert(list.get(5))

    // 测试indexOf方法
    alert(list.indexOf("aaa"))
    alert(list.indexOf("ccc"))
    alert(list.indexOf("yyy"))

    // 测试update方法
    list.update(0,"mmm")
    list.update(3,"nnn")
    alert(list)

    // 测试removeAt方法
    list.removeAt(0)
    alert(list)
    list.removeAt(3)
    alert(list)

    // 测试remove方法
    list.remove("nnn")
    alert(list)
    list.remove("xiaonaihu")
    alert(list)

    // 测试isEmpty方法
    alert(list.isEmpty())

    // 测试size方法
    alert(list.size())
  </script>
</body>
</html>

测试结果自己测试代码即可显示运行效果！

猜你喜欢

FPGA工程师面试试题集锦51~60
linux命令手册
hadoop杂记-为什么会有Map-reduce v2 (Yarn)
使用Springboot+MybatisPlus+Echarts+Mysql从0-1完成中国地图可视化动态展示
《图数据库》——2.2　NoSQL数据库也缺少联系
PostgreSQL触发器使用实践——数据审计(转载)
快速排序及优化
分类算法：决策树（C4.5）(转)
华为快应用-修改IDE的主题颜色
《测试反模式：有效规避常见的92种测试陷阱》——1.8　陷阱描述
ESP_12S模块-SmartConfig配网
你真的了解回归测试吗？
文件系统基本概念——高速缓冲 buffer.c学习笔记
Win8.1系统下如何删除多余的WiFi无线网络连接

相关主题

桶排序JavaScript
JavaScript事件流
学习JavaScript
javascript事件
Javascript之return
JavaScript预编译
JavaScript 计时
Javascript-DOM

zl程序教程

当前栏目

JavaScript：封装单向链表10种常见的操作方法

相关文章