- 6.1 // 数组的缺点: 1. 很多编程语言中, 数组的长度是固定的 2. 添加, 删除元素比较麻烦 3. JS 中的数组被实现成为对象, 与其他语言相比, 效率很低
- 6.2 // 定义链表
- // 链表是由一组节点组成的集合. 每个节点都使用一个对象的引用指向它的后继, 指向另一个节点的引用叫做链
- 6.3 // 我们设计的链表包含两个类, node 类用于表示节点, LinkedList 类提供了插入节点, 删除节点, 显示列表元素的方法, 以及其他一些辅助方法
- // Node 类
- function Node(ele) {
- this.ele = ele; // 用来保存节点上的数据
- this.next = null; // 保存指向下一个节点的连接, 初始化为 null
- }
- // LinkedList 类
- function LList() {
- this.head = new Node('head'); // 存储链表的头节点
- // this.find = find; // 查找节点
- // this.insert = insert; // 插入节点
- // this.remove = remove; // 删除节点
- // this.display = display;
- }
- // 插入新节点前要先 find()
- LList.prototype.find = function(item) {
- var currNode = this.head;
- while (currNode.ele != item) {
- currNode = currNode.next;
- }
- return currNode;
- }
- LList.prototype.insert = function(newElement, item) {
- // 新建插入的节点
- var newNode = new Node(newElement);
- // 寻找要插入的节点位置
- var current = this.find(item);
- // 修改新节点指向
- newNode.next = current.next;
- // 修改老节点指向
- current.next = newNode;
- }
- LList.prototype.display = function() {
- var currentNode = this.head;
- while (!(currentNode.next == null)) {
- console.log(currentNode.next.ele);
- currentNode = currentNode.next;
- }
- }
- LList.prototype.findPrevious = function (ele) {
- }
- LList.prototype.remove = function(targetEle) {
- // 根据传入节点 获取链表上的节点值
- var cur = this.find(targetEle);
- // 下一个节点值
- var nextNode = cur.next
- // 需要找到这个元素的上一个元素 上一个元素的 this.next 一定是 targetEle
- var currNode = this.head;
- while (currNode.next != cur) {
- currNode = currNode.next;
- }
- currNode.next = nextNode;
- }
- // var cities = new LList();
- // cities.insert('Conway', 'head');
- // cities.insert('Russellville', 'Conway');
- // cities.insert("Alma", "Russellville");
- // cities.remove('Conway')
- // cities.display()
来源: http://www.bubuko.com/infodetail-3336404.html