-
什么是链表
链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。 链表中的基本数据以节点来表示，每个节点由元素+指针构成，元素是存储数据的存储单元，指针就是连接每个节点的地址数据
-
单链表
/**
* 链表节点
*/
class Node
{
constructor(ele)
{
this.node=ele;
this.next=null;
}
}
/**
* 链表
*/
class LinkedList{
constructor(){
this.head=null;
this.tail=null;
this._length=0;
}
/**
* 链表优势就是 添加复杂度低O(1),数组 O(n)
*
* 添加
* @param {*} ele
*/
append(ele){
//执行 链
// var node={node:'xx' ,next:null} var head=node; var tail=node
// head === tail //true
// var newNode={node:'yy',next:null}
// tail.next=newNode; // 执行结果 tail===head={node:'xx',next:{node:'yy',next:null}}
// tail=newNode // 执行结果 head.next===tail===newNode
// 多次 append 后 head....next===tail===newNode
let node=new Node(ele);
if(this._length===0)
{
this.head=node;
this.tail=node;//记录最后一个节点
}
else{
this.tail.next=node;
//此时 再让 （head） last [node][next] === tail
this.tail=node;
}
this._length++;
}
/**
* 插入链表
* @param {*} ele
* @param {*} position
*/
insert(ele,position){
if(typeof position !=='number' || position!==position)
{
throw new TypeError('position type error');
}
let node=new Node(ele);
//空链表 直接插入即可
if(position===0)
{
node.next=this.head;
this.head=node;
}
else{
let i=0,cur=this.head,prev=null;
//查找到需要插入位置的两个节点
while(i<position)
{
prev=cur;
cur=cur.next;
i++;
}
//找到需要插入位置的两个链表节点
//node1 =》 node2 修改为 node1 =》nodeNew=》node2
prev.next=node;
node.next=cur;
}
this._length++;
return true;
}
/**
* 获取链表指定位置的
* @param {*} position
*/
getByPosition(position){
//判断传参是否合法
if(!this.isCheckPosition(position)) return null;
let i=0,cur=this.head;
while(i<position)
{
cur=cur.next;
i++;
}
return cur;
}
/**
* 更新
* @param {*} position
* @param {*} value
*/
update(position,value){
let res=this.getByPosition(position);
if(res){
res.node=value;
return true;
}
return false;
}
/**
* 判断链表中是否包含某个元素
* @param {*} value
*/
indexOf(value){
if(this._length==0)
{
return -1;
}
let cur=this.head,i=0;
//查找
while(cur)
{
if(cur.node===value){
return i;
}
else{
cur=cur.next;
i++;
}
}
return -1;
}
/**
* 移除
* @param {*} position
*/
remove(position){
if(!this.isCheckPosition(position)) return false;
let i=0,cur=this.head,prev=null;
while(i<position)
{
prev=cur;
cur=cur.next;
i++;
}
//找出需要删除的节点 让他的前一个节点的next 指向自己的next
// node1[next=node2] =》 node2[next=node3]
// prev=node1 cur.next=node3
//node1[next=node3]
prev.next=cur.next;
return true;
}
/**
*
* @param {*} position
*/
isCheckPosition(position){
//判断传参是否合法
if(typeof position !=='number' || position!==position)
{
throw new TypeError('position type error');
}
if(position.length>this._length)
{
return false;
}
return true;
}
}
var link=new LinkedList();
link.append(1);
link.append(2);
link.append(3);
link.append(4);
-
双向链表
function Node2(value){
this.node=value;
this.prev=null;
this.next=null;
}
// var node1=new Node2(1);
// var node2=new Node2(2);
// var node3=new Node2(3);
// var head=node1,tail=node1;
// node2.prev=this.tail;
// tail.next=node2;
// tail=node2;
// node3.prev=this.tail;
// tail.next=node3;
// tail=node3;
class DoublyLinkedList{
constructor(){
this.head=null;
this.tail=null;//指向 head的尾结点
this._length=0;
}
/**
* 新增
* @param {*} ele
*/
append(ele){
var node=new Node2(ele);
if(this.head===null)
{
this.head=node;
this.tail=node;
}
else{
// 新节点的 prev 指向 尾结点
node.prev=this.tail;
// 尾结点指向 新节点
this.tail.next=node;
//更新尾
this.tail=node;
}
this._length++;
}
/**
*
* @param {*} ele
* @param {*} position
*/
insert(ele,position){
if(this._length===position)
{
return this.append(ele);
}
let node=new Node2(ele),cur=this.head,i=0,prevNode=null;
while(i<position)
{
prevNode=cur;
cur=cur.next;
i++;
}
//新节点 prev 指向 插入位置的前面节点
node.prev=prevNode;
// 插入位置的前面节点 next 指向新节点
prevNode.next=node;
//新节点 next 指向插入位置的后面节点
node.next=cur;
//插入位置后面的节点 prev 指向 新node
cur.prev=node;
this._length++;
return true;
}
}
var doublyLinkedList=new DoublyLinkedList();
doublyLinkedList.append(1);
doublyLinkedList.append(2);
doublyLinkedList.append(3);
doublyLinkedList.append(4);
doublyLinkedList.append(6); //新增
doublyLinkedList.insert(5,4); //插入节点
运行结果
image.png
