数据结构-链表

链表

• 多个元素组成的列表
• 元素存储不连续，用next指针连在一起

数组VS链表

• 数组:增删非首尾元素时往往需要移动元素
• 链表:增珊非首尾元素，不需要移动元素，只需要更改next指向即可

JS中的链表

//用JS创建链表
let a = {val:'a'};//a就是链表或者称为链表的头部
let b = {val:'b'};
let c = {val:'c'};
let d = {val:'d'};
a.next = b;
b.next = c;
c.next = d
//遍历链表
let point = a;
while(p){
  console.log(p.val)
  p = p.next
}
//插入
const e = {val:'e'};
c.next = e;
e.next = d;
//删除
c.next = d;

删除链表中的节点（未知链表，已知被删节点）

//用JS创建链表
let a = {val:'a'};//a就是链表或者称为链表的头部
let b = {val:'b'};
let c = {val:'c'};
let d = {val:'d'};
a.next = b;
b.next = c;
c.next = d
//遍历链表
let point = a;
while(p){
  console.log(p.val)
  p = p.next
}
//插入
const e = {val:'e'};
c.next = e;
e.next = d;
//删除
c.next = d;

反转链表

//用JS创建链表
let a = {val:'a'};//a就是链表或者称为链表的头部
let b = {val:'b'};
let c = {val:'c'};
let d = {val:'d'};
a.next = b;
b.next = c;
c.next = d
function reverse(head){
  let p1 = head;
  let p2 = null;
  while(p1){
    const temp = p1.next;
    p1.next = p2;
    p2 = p1;
    p1 = temp;
  }
  return p2
}
let res = reverse(a);
while(res){
  console.log(res);
  res =res.next
}

两数相加

//用JS创建链表
let a = {val:7};//a就是链表或者称为链表的头部
let b = {val:4};
let c = {val:9};
let a1 = {val:4};
let b1 = {val:3};
let c1 = {val:2};
a.next = b;
b.next = c;
a1.next = b1;
b1.next = c1;
function add(head1,head2){
  let p1 = head1;
  let p2 = head2;
  let p3 = {val:0}
  let carrot = 0;
  while(p1 || p2){
    let val1 = p1.val? p1.val : 0;
    let val2 = p2.val? p2.val : 0;  
    carrot = Math.floor((val1+val2)/10);
    let val = (val1+val2)%10+carrot;
    p3.val = val;
    p3.next={val:''};
    p3 = p3.next;
    p1 = p1.next;
    p2 = p2.next;
  }
  return p3
}

原型链

本质是链表

原型链的节点是各种原型对象，比如Function.prototype,Object.prototype…

如果A沿着原型链能找到B.prototype那么A instanceof B就是true

如果在A对象上没有找到x属性会沿着原型链找x属性

  let obj = {};
  Object.prototype.x = 'x';
  console.log(obj.x); //x
  let func = function(){}
  console.log(func.x);

遍历原型链(手写 instanceof)

  const instanceOf = function(A,B){
    let p = A;
    while(p){
      if(p === B.prototype){
        return true
      }
      p = p.__proto__;
    }
    return false
  }
  instanceOf([],Array) //true
  instanceOf([],Object) //true

面试题

let foo = {},F = function(){};
Object.prototype.a =  'value a';
Function.prototype.b =  'value b';
console.log(foo.a);//value a
console.log(foo.b);//undefined
console.log(F.a);//value a
console.log(F.b);//value b

指针遍历json

const json = {
  a:{b:{c:1}},
  d:{e:2}
}
const path = ['d','e'];
let p = json;
path.forEach((k)=>{
  p = p[k];
  console.log(p)
})