算法由浅入深(一) #84

kekobin · 2020-07-10T07:53:38Z

JavaScript 数据结构与算法之美 (最底下那个系列文章)
图解算法
 动画算法
 写给前端的算法进阶指南，我是如何两个月零基础刷200题
 「算法与数据结构」梳理6大排序算法
 「算法与数据结构」DFS和BFS算法之美
 了不起的 IoC 与 DI
一些leecode数据结构相关js代码

复杂度分析-大O表示法

function bFun(n) {
    for(let i = 0; i < n; i++) {         // 需要执行 (n + 1) 次
        console.log("Hello, World!");      // 需要执行 n 次
    }
    return 0;       // 需要执行 1 次
}

这里时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以时间复杂度是 T(n) = O(n)

时间复杂度分析规则

1.只关注循环执行次数最多的一段代码
2.加法法则：总复杂度等于量级最大的那段代码的复杂度

function cal(n) {
   let sum_1 = 0;
   let p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
 }

时间复杂度为 T(n) = O(n^2)

3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
嵌套代码求乘积：比如递归、多重循环等。

function cal(n) {
   let ret = 0; 
   let i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i); // 重点为  f(i)
   } 
 } 
 
function f(n) {
  let sum = 0;
  let i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  } 
  return sum;
 }

T(n) = T1(n) * T2(n) = O(n*n) = O(n2) 。

4.多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加

function cal(m, n) {
  let sum_1 = 0;
  let i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  let sum_2 = 0;
  let j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

T(n) = O(m+n)

5.多个规模求乘法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相乘

function cal(m, n) {
  let sum_3 = 0;
   let i = 1;
   let j = 1;
   for (; i <= m; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
}

T(n) = O(m*n)

常用的时间复杂度分析

包括 O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n2) （平方阶）、O(n3)（立方阶）。

O(logn)（对数阶）：

let i=1;
while (i <= n)  {
   i = i * 2;
}

=>

2^1 * 2^2 ...2^x = n

这时循环结束，即只要算出x就能得到代码执行的次数。即 x = log2^n.所以时间复杂度为 T(n) = O(logn)

O(nlogn)（对数阶）：

function aFun(n){
  let i = 1;
  while (i <= n)  {
     i = i * 2;
  }
  return i
}

function cal(n) { 
   let sum = 0;
   for (let i = 1; i <= n; ++i) {
     sum = sum + aFun(n);
   }
   return sum;
 }

O(2n)（指数阶）例子：

aFunc( n ) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}

时间复杂度总结

常用的时间复杂度所耗费的时间从小到大依次是：

O(1) < O(logn) < (n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

空间复杂度分析

表示算法的存储空间与数据规模之间的增长关系。
定义：算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作：S(n) = O(f(n))，其中，n 为问题的规模，f(n) 为语句关于 n 所占存储空间的函数。

function print(n) {
 const newArr = []; // 第 2 行
 newArr.length = n; // 第 3 行
  for (let i = 0; i <n; ++i) {
    newArr[i] = i * i;
  }

  for (let j = n-1; j >= 0; --j) {
    console.log(newArr[i])
  }
}

这里的空间即数组长度n，所以S(n) = O(n).常见的空间复杂度就是 O(1)、O(n)、O(n2)

#《数据结构和算法描述》

array

splice(index, count,item1,item2...) : 任意位置删除/添加元素
1.count为0时，表示从index偏移开始，添加item1,item2...
2.count>0时，表示从index偏移开始，删除count个元素

(涉及到数组中每个元素的比较、交互等操作时，都可以用reduce)

reduce(function(total, currentValue, currentIndex, arr), initialValue)
reduce()方法接收一个函数作为累加器，数组中的每个值（从左到右）开始缩减，最终计算为一个值。
1.initialValue有值时，初始total = initialValue
2.initialValue无值时，初始total = array[0]

应用场景：
1.数组求和
2.简单数组去重

let arr = [1,2,3,4,5,2,3]
let result = arr.reduce((prev,cur)=>{
     if (!prev.includes(cur)){
        prev.push(cur)
     }
     return prev
},[])
console.log(result)

3.统计每个值，在数组中出现的次数

let arr = [1,2,3,4,5,2,3]
let result = arr.reduce((prev,cur)=>{
            if (prev[cur] != undefined) {
                prev[cur]++
            } else {
                prev[cur] = 1
            }
            return prev
},{})
console.log(result)

4.求数组中最大数

var a = [1,2,3,4,5,3,4,5,4,3,4,3,2,3,4,5,4,4,3,4,3,3,3,3,4]

var ret = a.reduce((m,n) => {
  if (m.max < n) m.max = n;
  return m;
}, {max: 0});
console.log(ret.max)

sort(fn)

线性表与非线性表

线性表（Linear List）：就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。数组、链表、队列、栈等就是线性表结构。

非线性表：数据之间并不是简单的前后关系。二叉树、堆、图就是非线性表。

数组

数组是用一组连续的内存空间来存储的。
所以数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
低效的插入和删除。
数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效，因为底层通常是要进行大量的数据搬移来保持数据的连续性。
插入与删除的时间复杂度如下：
插入：从最好 O(1) ，最坏 O(n) ，平均 O(n)
删除：从最好 O(1) ，最坏 O(n) ，平均 O(n)

栈

定义
后进者先出，先进者后出，简称后进先出（LIFO），这就是典型的栈结构。
新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。
在栈里，新元素都靠近栈顶，旧元素都接近栈底。
从栈的操作特性来看，是一种操作受限的线性表，只允许在一端插入和删除数据。
不包含任何元素的栈称为空栈。
栈也被用在编程语言的编译器和内存中保存变量、方法调用等，比如函数的调用栈。
实现
栈的方法：
push(element)：添加一个（或几个）新元素到栈顶。
pop()：移除栈顶的元素，同时返回被移除的元素。
peek()：返回栈顶的元素，不对栈做任何修改。
isEmpty()：如果栈里没有任何元素就返回 true，否则返回 false。
clear()：移除栈里的所有元素。
size()：返回栈里的元素个数。

// Stack类
function Stack() {
  this.items = [];

  // 添加新元素到栈顶
  this.push = function(element) {
    this.items.push(element);
  };
  // 移除栈顶元素，同时返回被移除的元素
  this.pop = function() {
    return this.items.pop();
  };
  // 查看栈顶元素
  this.peek = function() {
    return this.items[this.items.length - 1];
  };
  // 判断是否为空栈
  this.isEmpty = function() {
    return this.items.length === 0;
  };
  // 清空栈
  this.clear = function() {
    this.items = [];
  };
  // 查询栈的长度
  this.size = function() {
    return this.items.length;
  };
  // 打印栈里的元素
  this.print = function() {
    console.log(this.items.toString());
  };
}

队列

1.普通队列
队列是遵循 FIFO（First In First Out，先进先出）原则的一组有序的项。
队列在尾部添加新元素，并从顶部移除元素。
最新添加的元素必须排在队列的末尾。
队列只有入队 push() 和出队 pop()。

队列里面有一些声明的辅助方法：

enqueue(element)：向队列尾部添加新项。
dequeue()：移除队列的第一项，并返回被移除的元素。
front()：返回队列中第一个元素，队列不做任何变动。
isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false。
size()：返回队列包含的元素个数，与数组的 length 属性类似。
print()：打印队列中的元素。
clear()：清空整个队列。

// Queue类
function Queue() {
	this.items = [];

	// 向队列尾部添加元素
	this.enqueue = function(element) {
		this.items.push(element);
	};

	// 移除队列的第一个元素，并返回被移除的元素
	this.dequeue = function() {
		return this.items.shift();
	};

	// 返回队列的第一个元素
	this.front = function() {
		return this.items[0];
	};

	// 判断是否为空队列
	this.isEmpty = function() {
		return this.items.length === 0;
	};

	// 获取队列的长度
	this.size = function() {
		return this.items.length;
	};

	// 清空队列
	this.clear = function() {
		this.items = [];
	};

	// 打印队列里的元素
	this.print = function() {
		console.log(this.items.toString());
	};
}

2.优先队列
优先队列中元素的添加和移除是依赖优先级的。
应用：

一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。
再比如：火车，老年人、孕妇和带小孩的乘客是享有优先检票权的。

优先队列分为两类

最小优先队列
最大优先队列
最小优先队列是把优先级的值最小的元素被放置到队列的最前面（代表最高的优先级）。
比如：有四个元素："John", "Jack", "Camila", "Tom"，他们的优先级值分别为 4，3，2，1。
那么最小优先队列排序应该为："Tom"，"Camila"，"Jack"，"John"。

最大优先队列正好相反，把优先级值最大的元素放置在队列的最前面。
以上面的为例，最大优先队列排序应该为："John", "Jack", "Camila", "Tom"。

3.循环队列
循环队列，顾名思义，它长得像一个环。把它想像成一个圆的钟就对了。
关键是：确定好队空和队满的判定条件。
循环队列的一个例子就是击鼓传花游戏（Hot Potato）。在这个游戏中，孩子们围城一个圆圈，击鼓的时候把花尽快的传递给旁边的人。某一时刻击鼓停止，这时花在谁的手里，谁就退出圆圈直到游戏结束。重复这个过程，直到只剩一个孩子（胜者）。

// 实现击鼓传花
function hotPotato (nameList, num) {
  var queue = new Queue();

  for (var i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i]);
  }

  var eliminated = '';

  while (queue.size() > 1) {
    // 循环 num 次，队首出来去到队尾
    for (var i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }
    // 循环 num 次过后，移除当前队首的元素
    eliminated = queue.dequeue();
    console.log(`${eliminated} 在击鼓传花中被淘汰！`);
  }

  // 最后只剩一个元素
  return queue.dequeue();
}

// 测试
var nameList = ["John", "Jack", "Camila", "Ingrid", "Carl"];
var winner = hotPotato(nameList, 10);
console.log(`最后的胜利者是：${winner}`);

链表

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的，它是通过指针将零散的内存块串连起来的。
每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。

其中，data 中保存着数据，next 保存着下一个链表的引用。
上图中，我们说 data2 跟在 data1 后面，而不是说 data2 是链表中的第二个元素。值得注意的是，我们将链表的尾元素指向了 null 节点，表示链接结束的位置。

特点

链表是通过指针将零散的内存块串连起来的。
所以链表不支持随机访问，如果要找特定的项，只能从头开始遍历，直到找到某个项。
所以访问的时间复杂度为 O(n)。
高效的插入和删除。
链表中插入或者删除一个数据，我们并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的，只需要考虑相邻结点的指针改变。
所以，在链表中插入和删除一个数据是非常快速的，时间复杂度为 O(1)。

单链表

由于链表的起始点的确定比较麻烦，因此很多链表的实现都会在链表的最前面添加一个特殊的节点，称为头节点，表示链表的头部。

经过改造，链表就成了如下的样子：

针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以插入与删除的时间复杂度为 O(1)。
在 d2 节点后面插入 d4 节点：

删除 d4 节点：

实现
Node 类用来表示节点。
LinkedList 类提供插入节点、删除节点等一些操作。
单向链表的八种常用操作：
append(element)：尾部添加元素。
insert(position, element)：特定位置插入一个新的项。
removeAt(position)：特定位置移除一项。
remove(element)：移除一项。
indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回 -1。
isEmpty()：如果链表中不包含任何元素，返回 true，如果链表长度大于 0，返回 false。
size()：返回链表包含的元素个数，与数组的 length 属性类似。
getHead()：返回链表的第一个元素。
toString()：由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值。
print()：打印链表的所有元素。
链表的insert和remove都必须获取到previousNode和currentNode才行

// 单链表
function SinglyLinkedList() {
	// 节点
	function Node(element) {
		this.element = element; // 当前节点的元素
		this.next = null; // 下一个节点指针
	}

	var length = 0; // 链表的长度
	var head = null; // 链表的头部节点

	// 向链表尾部添加一个新的节点
	this.append = function(element) {
		var node = new Node(element);
		var currentNode = head;

		// 判断是否为空链表
		if (head === null) {
			// 是空链表，就把当前节点作为头部节点
			head = node;
		} else {
			// 从 head 开始一直找到最后一个 node
			while (currentNode.next) {
				// 后面还有 node
				currentNode = currentNode.next;
			}
			// 把当前节点的 next 指针 指向 新的节点
			currentNode.next = node;
		}
		// 链表的长度加 1
		length++;
	};

	// 向链表特定位置插入一个新节点
	this.insert = function(position, element) {
		if (position < 0 || position > length) {
			// 越界
			return false;
		} else {
			var node = new Node(element);
			var index = 0;
			var currentNode = head;
			var previousNode;

			// 在最前插入节点
			if (position === 0) {
				node.next = currentNode;
				head = node;
			} else {
				// 循环找到位置
				while (index < position) {
					index++;
					previousNode = currentNode;
					currentNode = currentNode.next;
				}
				// 把前一个节点的指针指向新节点，新节点的指针指向当前节点，保持连接性
				previousNode.next = node;
				node.next = currentNode;
			}

			length++;

			return true;
		}
	};

	// 从链表的特定位置移除一项
	this.removeAt = function(position) {
		if ((position < 0 && position >= length) || length === 0) {
			// 越界
			return false;
		} else {
			var currentNode = head;
			var index = 0;
			var previousNode;

			if (position === 0) {
				head = currentNode.next;
			} else {
				// 循环找到位置
				while (index < position) {
					index++;
					previousNode = currentNode;
					currentNode = currentNode.next;
				}
				// 把当前节点的 next 指针 指向 当前节点的 next 指针，即是 删除了当前节点
				previousNode.next = currentNode.next;
			}

			length--;

			return true;
		}
	};

	// 从链表中移除指定项
	this.remove = function(element) {
		var index = this.indexOf(element);
		return this.removeAt(index);
	};

	// 返回元素在链表的索引，如果链表中没有该元素则返回 -1
	this.indexOf = function(element) {
		var currentNode = head;
		var index = 0;

		while (currentNode) {
			if (currentNode.element === element) {
				return index;
			}

			index++;
			currentNode = currentNode.next;
		}

		return -1;
	};

	// 如果链表中不包含任何元素，返回 true，如果链表长度大于 0，返回 false
	this.isEmpty = function() {
		return length === 0;
	};

	// 返回链表包含的元素个数，与数组的 length 属性类似
	this.size = function() {
		return length;
	};

	// 获取链表头部元素
	this.getHead = function() {
		return head.element;
	};

	// 由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值
	this.toString = function() {
		var currentNode = head;
		var string = '';

		while (currentNode) {
			string += ',' + currentNode.element;
			currentNode = currentNode.next;
		}

		return string.slice(1);
	};

	// 打印链表数据
	this.print = function() {
		console.log(this.toString());
	};

	// 获取整个链表
	this.list = function() {
		console.log('head: ', head);
		return head;
	};
}

在 JavaScript 中，单链表的真实数据有点类似于对象，实际上是 Node 类生成的实例。

双向链表

单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。
而双向链表，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

单向链表与又向链表比较

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。
所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。
虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。
双向链表提供了两种迭代列表的方法：从头到尾，或者从尾到头。
我们可以访问一个特定节点的下一个或前一个元素。
在单向链表中，如果迭代链表时错过了要找的元素，就需要回到链表起点，重新开始迭代。
在双向链表中，可以从任一节点，向前或向后迭代，这是双向链表的一个优点。
所以，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

// 创建双向链表 DoublyLinkedList 类
function DoublyLinkedList() {
  function Node(element) {
    this.element = element; //当前节点的元素
    this.next = null; //下一个节点指针
    this.previous = null; //上一个节点指针
  }

  var length = 0; // 链表长度
  var head = null; // 链表头部
  var tail = null; // 链表尾部

  // 向链表尾部添加一个新的项
  this.append = function(element) {
    var node = new Node(element);
    var currentNode = tail;

    // 判断是否为空链表
    if (currentNode === null) {
      // 空链表
      head = node;
      tail = node;
    } else {
      currentNode.next = node;
      node.prev = currentNode;
      tail = node;
    }

    length++;
  };

  // 向链表特定位置插入一个新的项
  this.insert = function(position, element) {
    if (position < 0 || position > length) {
      // 越界
      return false;
    } else {
      var node = new Node(element);
      var index = 0;
      var currentNode = head;
      var previousNode;

      if (position === 0) {
        if (!head) {
          head = node;
          tail = node;
        } else {
          node.next = currentNode;
          currentNode.prev = node;
          head = node;
        }
      } else if (position === length) {
        this.append(element);
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }

        previousNode.next = node;
        node.next = currentNode;

        node.prev = previousNode;
        currentNode.prev = node;
      }

      length++;

      return true;
    }
  };

  // 从链表的特定位置移除一项
  this.removeAt = function(position) {
    if ((position < 0 && position >= length) || length === 0) {
      // 越界
      return false;
    } else {
      var currentNode = head;
      var index = 0;
      var previousNode;

      if (position === 0) {
        // 移除第一项
        if (length === 1) {
          head = null;
          tail = null;
        } else {
          head = currentNode.next;
          head.prev = null;
        }
      } else if (position === length - 1) {
        // 移除最后一项
        if (length === 1) {
          head = null;
          tail = null;
        } else {
          currentNode = tail;
          tail = currentNode.prev;
          tail.next = null;
        }
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        previousNode.next = currentNode.next;
        previousNode = currentNode.next.prev;
      }

      length--;

      return true;
    }
  };

  // 从链表中移除指定项
  this.remove = function(element) {
    var index = this.indexOf(element);
    return this.removeAt(index);
  };

  // 返回元素在链表的索引，如果链表中没有该元素则返回 -1
  this.indexOf = function(element) {
    var currentNode = head;
    var index = 0;

    while (currentNode) {
      if (currentNode.element === element) {
        return index;
      }

      index++;
      currentNode = currentNode.next;
    }

    return -1;
  };

  // 如果链表中不包含任何元素，返回 true ，如果链表长度大于 0 ，返回 false
  this.isEmpty = function() {
    return length == 0;
  };

  // 返回链表包含的元素个数，与数组的 length 属性类似
  this.size = function() {
    return length;
  };

  // 获取链表头部元素
  this.getHead = function() {
    return head.element;
  };

  // 由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值
  this.toString = function() {
    var currentNode = head;
    var string = '';

    while (currentNode) {
      string += ',' + currentNode.element;
      currentNode = currentNode.next;
    }

    return string.slice(1);
  };

  this.print = function() {
    console.log(this.toString());
  };

  // 获取整个链表
  this.list = function() {
    console.log('head: ', head);
    return head;
  };
}

链表代码实现的关键是弄清楚：前节点与后节点与边界。

循环链表

循环链表是一种特殊的单链表。
循环链表和单链表相似，节点类型都是一样。
唯一的区别是，在创建循环链表的时候，让其头节点的 next 属性指向它本身。
即：

head.next = head;

这种行为会导致链表中每个节点的 next 属性都指向链表的头节点，换句话说，也就是链表的尾节点指向了头节点，形成了一个循环链表。如下图所示：

环形链表从任意一个节点开始，都可以遍历整个链表。

// 循环链表
function CircularLinkedList() {
	// 节点
	function Node(element) {
		this.element = element; // 当前节点的元素
		this.next = null; // 下一个节点指针
	}

	var length = 0,
		head = null;

	this.append = function(element) {
		var node = new Node(element),
			current;

		if (!head) {
			head = node;
			// 头的指针指向自己
			node.next = head;
		} else {
			current = head;

			while (current.next !== head) {
				current = current.next;
			}

			current.next = node;
			// 最后一个节点指向头节点
			node.next = head;
		}

		length++;
		return true;
	};

	this.insert = function(position, element) {
		if (position > -1 && position < length) {
			var node = new Node(element),
				index = 0,
				current = head,
				previous;

			if (position === 0) {
				// 头节点指向自己
				node.next = head;
				head = node;
			} else {
				while (index++ < position) {
					previous = current;
					current = current.next;
				}
				previous.next = node;
				node.next = current;
			}
			length++;
			return true;
		} else {
			return false;
		}
	};
	this.removeAt = function(position) {
		if (position > -1 && position < length) {
			var current = head,
				previous,
				index = 0;
			if (position === 0) {
				head = current.next;
			} else {
				while (index++ < position) {
					previous = current;
					current = current.next;
				}
				previous.next = current.next;
			}
			length--;
			return current.element;
		} else {
			return false;
		}
	};
	this.remove = function(element) {
		var current = head,
			previous,
			indexCheck = 0;
		while (current && indexCheck < length) {
			if (current.element === element) {
				if (indexCheck == 0) {
					head = current.next;
					length--;
					return true;
				} else {
					previous.next = current.next;
					length--;
					return true;
				}
			} else {
				previous = current;
				current = current.next;
				indexCheck++;
			}
		}
		return false;
	};
	this.remove = function() {
		if (length === 0) {
			return false;
		}
		var current = head,
			previous,
			indexCheck = 0;
		if (length === 1) {
			head = null;
			length--;
			return current.element;
		}
		while (indexCheck++ < length) {
			previous = current;
			current = current.next;
		}
		previous.next = head;
		length--;
		return current.element;
	};
	this.indexOf = function(element) {
		var current = head,
			index = 0;
		while (current && index < length) {
			if (current.element === element) {
				return index;
			} else {
				index++;
				current = current.next;
			}
		}
		return -1;
	};
	this.isEmpty = function() {
		return length === 0;
	};
	this.size = function() {
		return length;
	};

	// 由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值
	this.toString = function() {
		var current = head,
			string = '',
			indexCheck = 0;
		while (current && indexCheck < length) {
			string += ',' + current.element;
			current = current.next;
			indexCheck++;
		}
		return string.slice(1);
	};

	// 获取链表头部元素
	this.getHead = function() {
		return head.element;
	};

	// 打印链表数据
	this.print = function() {
		console.log(this.toString());
	};

	// 获取整个链表
	this.list = function() {
		console.log('head: ', head);
		return head;
	};
}

链表总结

写链表代码是最考验逻辑思维能力的，要熟练链表，只有多写多练，没有捷径。
因为，链表代码到处都是指针的操作、边界条件的处理，稍有不慎就容易产生 Bug。
链表代码写得好坏，可以看出一个人写代码是否够细心，考虑问题是否全面，思维是否缜密。
所以，这也是很多面试官喜欢让人手写链表代码的原因。
一定要自己写代码实现一下，才有效果。

The text was updated successfully, but these errors were encountered:

kekobin changed the title ~~算法由浅入深~~ 算法由浅入深(一) Aug 28, 2020

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

算法由浅入深(一) #84

算法由浅入深(一) #84

kekobin commented Jul 10, 2020 •

edited

Loading

算法由浅入深(一) #84

算法由浅入深(一) #84

Comments

kekobin commented Jul 10, 2020 • edited Loading

复杂度分析-大O表示法

时间复杂度分析规则

常用的时间复杂度分析

O(logn)（对数阶）：

O(nlogn)（对数阶）：

O(2n)（指数阶）例子：

时间复杂度总结

空间复杂度分析

array

线性表与非线性表

数组

栈

队列

链表

特点

单链表

双向链表

单向链表与又向链表比较

循环链表

链表总结

kekobin commented Jul 10, 2020 •

edited

Loading