©2020-2024 ioDraw All rights reserved
<>1.链表介绍
1.存储多个元素最常用的数据结构是数组，数组有一个缺点， (大多数语言中)数组的大小是固定的，从数组的起点或中间插入或移除项成本很高，
需要移动元素(我们所学的JavaScript有来自Array类的方法可以帮我们做这些事，但背后的情况同样如此)
2.链表存储有序的元素集合，不同于数组，链表中的元素在内存中并不是连续放置的，每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成
3.链表类似于火车头，一节车厢载着乘客（数据），通过节点连接另一节车厢
* head属性指向链表的第一个节点；
* 链表中的最后一个节点指向null(或者undefined也可以)；
* 当链表中一个节点也没有的时候，head直接指向null；
<>2.链表的优点：
1.链表中的元素在内存中不必是连续的空间，可以充分利用计算机的内存，实现灵活的内存动态管理 2.链表不必在创建时就确定大小，并且大小可以无限地延伸下去。
3.链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组效率高很多。
<>3.链表的缺点：
1.链表访问任何一个位置的元素时，都需要从头开始访问（无法跳过第一个元素访问任何一个元素）
2.无法通过下标值直接访问元素，需要从头开始一个个访问，直到找到对应的元素。 3.虽然可以轻松地到达下一个节点，但是回到前一个节点是很难的。
<>4.链表中的常见操作
append（element）：向链表尾部添加一个新的项； insert（position，element）：向链表的特定位置插入一个新的项；
get（position）：获取对应位置的元素； indexOf（element）：返回元素在链表中的索引。如果链表中没有该元素就返回-1；
update（position，element）：修改某个位置的元素； removeAt（position）：从链表的特定位置移除一项；
remove（element）：从链表中移除一项； isEmpty（）：如果链表中不包含任何元素，返回trun，如果链表长度大于0则返回false；
size（）：返回链表包含的元素个数，与数组的length属性类似；
toString（）：由于链表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值；
<>5.ES5实现链表结构
function LinkList(){ // 封装节点内部类 function Node(data){ this.data = data; this.
next= null; } // 属性 this.head = null; //默认指向空; this.length = 0; //长度初始为0; //
方法,放在原型对象上共享方法，节省内存，效率高 LinkList.prototype.append = function(element){ //
1.长度为0时 let newNode = new Node(element); if(this.length === 0){ this.head =
newNode; newNode.next = null; //可以省略，因为新节点初始指向空 }else{ // 2.长度不为0，末尾添加 let
current= this.head; //head指向的后一个元素，同一个指向 while(current.next){ current = current.
next; } //此时遍历后current为链表末尾的元素 current.next = newNode; newNode.next = null;
//同理此行代码也可以不写 } // 添加完元素，需要将链表长度增加 this.length +=1; } // 指定位置插入 LinkList.
prototype.insert = function(position,element){ // 先做边界值判断 if(position < 0 ||
position> this.length-1) return false; let newNode = new Node(element); // 首部插入
if(position == 0 ){ newNode.next = this.head; //此时this.head指向链表的第一个元素 this.head
= newNode; }else{ let current = this.head; //共同链表第一个元素 let index = 0; let
previous= null; //记录插入的前一个节点 // 在节点末尾插入也在这种情况其中 while(index++ < position){
previous= current; current = current.next; } //
遍历完，此时current就到了position这个位置的节点,需插入到previous和current之间 previous.next = newNode;
newNode.next = current; } this.length +=1; return true; } // 获取对应位置的元素 LinkList.
prototype.get = function(position){ // 做一个边界值判断 if(position < 0 || position >
this.length-1) return false; let current = this.head; if(this.length == 0){
return null; }else{ let index = 0; while(index++ < position){ current = current.
next; } return current.data; } } // 查找元素在链表中的索引 LinkList.prototype.indexOf =
function(element){ if(this.length == 0){ return -1; } else{ let current = this.
head; let index = 0; while(current){ if(current.data == element){ return index;
} index +=1; current = current.next; } } return -1; } // 更新元素 LinkList.prototype
.update = function(position,element){ // 边界值判断 if(position < 0 || position >
this.length-1) return false; let current = this.head; if(this.length == 0){
return false; }else{ let index = 0; while(index++ < position){ current = current
.next; } current.data = element; } return current.data; } LinkList.prototype.
removeAt = function(position){ if(position < 0 || position > this.length -1)
return false; if(position == 0){ this.head = this.head.next; }else{ let current
= this.head; let index =0; let previous = null; while(index++ < position){
previous= current; current = current.next; } previous.next = current.next; }
this.length--; return true; } // 移除 LinkList.prototype.remove = function(element
){ // 1.获取element在链表中的位置 let position = this.indexOf(element); // 2.根据位置信息，删除节点
return this.removeAt(position); } LinkList.prototype.toString = function(){ let
current= this.head; let objString = ''; while(current){ objString +=current.data
+' '; current = current.next; } return objString; } LinkList.prototype.size =
function(){ return this.length; } LinkList.prototype.isEmpty = function(){
return this.length == 0; } }
测试：
let list = new LinkList(); list.append('aaaa'); list.append('bbb'); list.append
('ccc'); list.insert(0,'nba'); list.insert(2,'hhh'); list.insert(5,'ggg');
console.log(list); console.log(list.get(2)); console.log(list.get(0)); console.
log(list.indexOf('ccc')); console.log(list.indexOf('aaa')); console.log(list.
indexOf('aaaa')); console.log(list.indexOf('hhh')); console.log(list.update(0,
'ygy')); console.log(list.removeAt(1)); console.log(list.removeAt(0)); console.
log(list.removeAt(5)); console.log(list.remove('hhh')); console.log(list.
toString()); console.log(list.size()); console.log(list.isEmpty());
<>6.使用ES6封装
// 创建一个Node节点类 class Node{ constructor(element){ this.data = element; this.next
= null; } } // 创建链表类 class LinkList{ constructor(){ this.head = null; this.
length= 0; } // append方法向尾部添加一个新的项 append(element){ let current = this.head; let
node= new Node(element); // 判断长度为空时添加 if(this.length === 0){ this.head = node;
node.next = null; //可以不写 }else{ while(current.next){ current = current.next; }
current.next = node; node.next = null //也可以不写 } this.length +=1; } // insert()插入
insert(position,element){ // 先做一个边界值判断 if(position < 0 || position > this.length
) return false; // 创建新节点 let node = new Node(element); let current = this.head;
if(position == 0){ this.head = node; node.next = current; }else{ let index = 0;
let previous = null; while(index++ < position){ previous = current; current =
current.next; } previous.next = node; node.next = current; } this.length +=1;
return true; } }
其他方法和ES5中相同