一、链表

线性表：0个或者是多个数据元素有限序列

物理的存储结构：

1. 顺序存储：用一段连续的存储单元依次存储线性表的数据元素。
2. 链式存储：内存地址可以是连续的，也可以是不连续的。把数据元素存放在任意的存储单元里，指针来存放数据元素的地址

JS数组不是真正意义上的数组，JS的数组并不是存在一段连续的内存中 

 数组：在大多数的语言中，虽然数组查询很快，但是数组的大小是固定，从数组的起点或者是中间插入或者移除元素的，成本其实很高，因为需要移动元素，尤其当内存不足重新申请更大内存时，数据拷贝的代价很大。

所以 。。链表来了

链表中的元素在内存中不必是连续的空间

链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针或者链接)组成

结论：

• 插入删除：链表的性能好：链表没有大小限制，支持动态扩容，但是因为链表的每个结点都需要存储前驱/后驱结点的指针，内存消耗会翻倍。
• 查询修改：数组性能好

// 结点类
class Node {
	constructor(element) {
		this.element = element;
		this.next = null;
	}
}
// 链表
class LinkList {
	constructor() {
		// 头部
		this.head = null;
		// 链表长度
		this.length = 0;
	}
	// 1、链表尾部追加元素
	append(element) {
		// 创建结点
		let node = new Node(element);
		// 如果说链表为空
		if (this.length === 0) {
			this.head = node;
		} else {
			// 通过head找到后面的结点
			let current = this.head;
			// 遍历
			while (current.next) {
				current = current.next;
			}
			// while 执行完毕以后，current变成最后一个节点
			current.next = node;
		}
		// length增加
		this.length += 1;
	}
	// 2、获取链表头部
	getHead() {
		return this.head;
	}
	// 3、toString方法
	toString() {
		let current = this.head;
		console.log(current)
		let linkString = '';
		while (current) {
			linkString += ',' + current.element.element;
			current = current.next;
		}
		// 从第一个位置开始
		return linkString.slice(1);
	}
	// 在任意位置插入元素
	insert(element, position) {
		// 位置不能是负数
		if(position < 0 || position > this.length)  {
			return false
		}
		let index = 0;
		let current = this.head;
		// 上一个结点
		let provious = null;
		// 创建元素
		let node = new Node(element);
		// 判断插入的是不是第一个
		if (position === 0) {
			node.next = this.head;
			this.head = node;
		} else {
			while (index < position) {
				provious = current;
				current = current.next;
				index++;
			}
			node.next = current;
			provious.next = node;
		}
		// 长度加一
		this.length += 1;
	}
	// get获取对应位置的元素
	get(position) {
		// 越界判断
		if (position < 0 || position > this.length) {
			return null
		}
		// 获取对应的结点
		let current = this.head;
		let index = 0;
		while (index < position) {
			current = current.next;
			index++;
		}
		return current.element
	}
	// 根据元素位置删除结点
	removeAt(position){
		// 越界判断
		if (position < 0 || position > this.length) {
			return null
		}
		// 定义一个变量，保存信息
		let index = 0;
		let current = this.head;
		let provious = null;
		// 判断是否是第一个结点
		if(position === 0){
			this.head  =  this.head.next;
		}else{
			while(index<position){
				provious =  current;
				current = current.next;
				index++;
			}
			provious.next = current.next;
		}
		// 长度减一
		this.length--;
		// 返回移除元素
		return current.element;
	}
}
// [1,5,4,4] ->,1,5,4,4->[',','object']
const n = new Node('我是小白855');
const ll = new  LinkList();

ll.append(n)
console.log(ll.toString())

二、JS原型链

JS是基于对象设计和开发出来的语言 ;

面向对象有三大特点：（封装、继承于多态）;

“基于对象”是使用对象，但是我们无法利用现有的对象模板去产生新的对象类型，继而去产生一个新的对象，也就是说"基于对象"是没有继承的特点。但是面向对象对象实现了继承和多态，基于现象是没有实现这些的 .

oop面向对象的支持两种继承方式：接口继承、实现继承

ECMAscript 是无法去实现去接口继承的，JS只支持实现继承。实现继承主要依靠原型链去实现

prototype和 __proto__

1. 所有的引用类型（数组、函数、对象）可以自由的扩展属性（null除外）
2. 所有的引用类型都有一个 --proto--属性（隐式原型，它其实就是一个普通的对象）
3. 所有的函数都有一个prototype 属性（显式原型，它也是一个普通的对象）
4. 所有的引用类型，它的--proto--属性指向它的构造函数的prototype属性
5. 当视图得到一个对象的属性时，如果这个对象的本身不存在这个属性，那么就会去它的--proto--属性中寻找（去它的构造函数的prototype属性）中寻找

function Person(name,age){
	this.name = name;
	this.age = age;
	this.text = function(){
		console.log(`name:${this.name},age:${this.age}`)
	}
}
// 通过原型添加方法，原型给所有对象添加属性或者方法
Person.prototype.show = function(){
	console.log('原型链里的方法')
}
/*
Person是一个普通函数，它作用是构造对象
1、通过工厂方式去构造，里面方法存在问题，容易导致全局作用域污染，数据不安全且容易被覆盖
通过工厂方式：(例子：this.text)去构造对象的时候会浪费资源
2、原型链的方法：prototype
*/ 
var xiaobai = new Person('小白'，26)
var xiaoxiaobai = new Person('小小白'，16)
console.log(xiaobai.text === xiaoxiaobai.text); //false
console.log(xiaobai.show === xiaoxiaobai.show) //true

再看下面这个Person函数：

function Person(name,age){
	this.name = name;
	this.age = age;
}
Object.prototype.show = function(){
	console.log('原型链里的方法')
}
var xiaobai = new Person('小白'，26)
xiaobai.show()

xiaobai的构造函数是Person，所有的引用类型它的__proto__属性指向它的构造函数prototype属性； Person.prototype.是一个普通的对象，它的构造函数是Object，相当于：

var Person = new Object();

Person.name = '小白';

Person.age='26';

当调用这个对象本身并不存在的属性或者是方法时，它会一层层地往上找，一直找到null为止，null表示空的对象 { } 

原型链的继承

function Person(name,age){
	this.name = name;
	this.age = age;
    this.show = function(){
	    console.log('原型链里的方法')
    }
}
function Xiaobai(){}
// xiaobai通过Xiaobai()继承Person中show方法
Xiaobai.prototype = new Person('小白'，26)
var xiaobai = new Xiaobai()
xiaobai.show()

原型链机制：利用原型让一个引用类型继承另外一个引用类型的属性和方法