JavaScript数据结构之链表
|字数总计:2.9k|阅读时长:10分钟|阅读量:
前言
❤️笔芯❤️~
链表
链表数据结构,向链表添加元素,从链表移除元素,使用LinkedList类,双向链表,循环链表。
链表存储有序的元素集合,但链表中的元素在内存中并不是连续放置的,每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(指针或链接)组成。
示例:
链表的好处:添加或移除元素的时候不需要移动其他元素
访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素
链表:生活中的寻宝游戏例子。
创建链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| function LinkedList() { let Node = function(element) { // LinkedList数据结构还需要一个Node辅助类 this.element = element; this.next = null; }; // Node类表示要加入列表的项 // 它包含一个element属性,即要添加到列表的值,以及一个next属性,即指向列表中下一个节点项的指针 let length = 0; // LinkedList类也有存储列表项的数量的length属性 let head = null; // 需要存储第一个节点的引用,这个引用存储在一个为head的变量中 // append(element),向列表尾部添加一个新的项 this.append = function(element){}; // insert(position,element),向列表的特定位置插入一个新的项 this.insert = function(position, element){}; // removeAt(position),从列表的特定位置移除一项 this.removeAt = function(position){}; // remove(element),从列表中移除一项 this.remove = function(element){}; // indexOf(element),返回元素在列表中的索引,如果列表中没有该元素则返回-1 this.indexOf = function(element){}; // 如果链表中不包含任何元素,返回true,如果链表长度大于0则返回false this.isEmpty = function(){}; // 返回链表包含的元素个数 this.size = function(){}; this.getHead = function(){}; // 由于列表项使用了Node类,就需要重写继承来自JavaScript对象默认的toString方法,让其只输出元素的值 this.toString = function(){}; this.print = function(){}; }
|
向链表尾部追加元素
场景:
- 列表为空,添加第一个元素
- 列表不为空,向其追加元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| this.append = function(element){ // 需要把element作为值传入,创建Node项 let node = new Node(element), // current; if(head === null) { // 列表中第一个节点 // 在向列表添加第一个元素 // 下一个node元素将会自动成为null head = node; }else{ // 要向列表的尾部添加一个元素,首先需要找到最后一个元素 current = head; // 循环列表,直到找到最后一项 while(current.next){ // 需要一个指向列表中current项的变量 current = current.next } // 找到最后一项,将其next赋为node,建立链接 current.next = node } length++; // 更新列表的长度 };
|
1 2 3
| let list = new LinkedList(); list.append(1); list.append(2);
|
从链表中移除元素
场景:1,移除第一个元素;2,移除第一个以外的任一元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| // 从特定位置移除一个元素
// 根据元素的值移除元素
this.removeAt = function(position) { // 检查越界值 if(position > -1 && position < length) { // 该方法要得到需要移除的元素的位置,就需要验证这个位置是有效的 let current = head, // 将用current变量创建一个对列表中第一个元素的引用 previous, // index = 0; // // 移除第一项 if(position === 0) { // 从列表中移除第一个元素 让head指向列表的第二个元素 // 把head赋为current.next,就会移除第一个元素 head = current.next; } else { while (index++ < position) { // 需要依靠一个细节来迭代列表,直到到达目标位置 previous = current; // 对当前元素的前一个元 素的引用 current = current.next; // current变量总是为对所循环列表的当前元素的引用 } // 将previous与current的下一项链接起来,跳过current,从而移除它 previous.next = current.next; // 要从列表中移除当前元素,要做的就是将previous.next和current.next链接起来 } length--; // return current.element; }else{ return null; // 如果不是有效的位置,就返回null } }
|
在任意位置插入元素
使用insert
方法,可以在任意位置插入一个元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| this.insert = function(position, element){ //检查越界值 if (position >= 0 && position <= length){ //需要检查越界值 let node = new Node(element), current = head, // current变量是对列表中第一个元素的引用 previous, index = 0; if (position === 0){ //在第一个位置添加 node.next = current; //把node.next的值设为current head = node; // 把head的引用改为node // head和node.next都指向了current } else { // 在列表中间或尾部添加一个元素 while (index++ < position){ //需要循环访问列表,找到目标位置 previous = current; current = current.next; } node.next = current; //当跳出循环时,current变量将是对想要插入新元素的位置之后一个元素的引用 // previous.next指向node previous.next = node; //previous将是对想要插入新元素的位置之前一个元素的引用 } length++; //更新列表的长度 return true; } else { return false; //返回false值,表示没有添加项到列表中 } };
|
previous
将是对列表最后一项的引用
current
将是null
node.next
将指向current
,而previous.next
将指向node
- 需要把
node.next
的值指向current
。然后把previous.next
的值设为node
toString
方法会把LinkedList
对象转换成一个字符串
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| this.toString = function(){ // 会把current变量当作索引 let current = head, //需要有一个起点 string = ''; //还需要初始化用于拼接元素值的变量 while (current) { //循环访问列表中的每个元素 string += current.element + (current.next ? 'n' : ''); //得到了元素的内容,将其拼接到字符串中 current = current.next; //继续迭代下一个元素 } return string; //返回列表内容的字符串 };
|
indexOf
方法接收一个元素的值,如果在列表中找到它,就返回元素的位置,否则返回-1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| this.indexOf = function(element){ let current = head, //是current,它的初始值是head // 需要一个index变量来计算位置数 index = -1; // 循环访问元素 while (current) { if (element === current.element) { return index; //检查当前元素是否是我们要找的。如果是,就返回它的位置 } index++; //如果不是,就继续计数 current = current.next; //检查列表中下一个节点 } // 如果列表为空,或是到达列表的尾部 // current = current.next将是null return -1; };
|
其他的方法:
1 2 3 4
| this.remove = function(element){ let index = this.indexOf(element); return this.removeAt(index); };
|
1 2 3
| this.isEmpty = function() { return length === 0; };
|
1 2 3
| this.size = function() { return length; };
|
1 2 3
| this.getHead = function(){ return head; };
|
双向链表
- 在双向链表中,链接是双向的
- 一个链向下一个元素,另一个链向前一个元素
1 2 3 4 5 6 7 8 9 10 11 12
| function DoublyLinkedList() {
let Node = function(element){ this.element = element; this.next = null; this.prev = null; //新增的 一个新指针 }; let length = 0; let head = null; let tail = null; //新增的 //这里是方法 }
|
在任意位置插入新元素
- 控制
next和prev
(previous
,前一个)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| this.insert = function(position, element){
//检查越界值 if (position >= 0 && position <= length){ let node = new Node(element), current = head, previous, index = 0; // 在列表的第一个位置(列表的起点)插入一个新元素1 if (position === 0){ //在第一个位置添加 if (!head){ //新增的 // 只需要把head和tail都指向这个新节点 head = node; tail = node; } else { node.next = current; // current.prev指针将由指向null变为指向新元素 current.prev = node; //新增的 head = node; } } else if (position === length) { //最后一项 //新增的 current = tail; // 控制着指向最后一个元素的指针(tail) // current变量将引用最后一个元素 current.next = node; //current.next指针(指向null)将指向node node.prev = current; //node.prev将引用current tail = node; // 更新tail // 它将由指向current变为指向node } else { // 在列表中间插入一个新元素 while (index++ < position){ //直到到达要找的位置 previous = current; current = current.next; } node.next = current; //node.next将指向current previous.next = node; // previous.next将指向node current.prev = node; //新增的current.prev将指向node node.prev = previous; //新增的node.prev将指向previous } length++; //更新列表的长度 return true; } else { return false; } };
|
从任意位置移除元素
示例:
从双向链表移除第一个元素的过程:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| this.removeAt = function(position){
//检查越界值 if (position > -1 && position < length){ // current变量是对列表中第一个元素的引用 let current = head, previous, index = 0; //移除第一项 if (position === 0){ // 改变 head 的引用 head = current.next; //将其从 current 改为下一个元素 //如果只有一项,更新tail //新增的 if (length === 1){ //检查要移除的元素是否是第一个元素,如果是,只需要把tail也设为null tail = null; } else { head.prev = null; //把head.prev的引用改为null } } else if (position === length-1){ //最后一项 //新增的 // 从最后一个位置移除元素 current = tail; //把tail的引用赋给current变量 tail = current.prev; tail.next = null; } else { // 从列表中间移除一个元素 while (index++ < position){ //需要迭代列表,直到到达要找的位置 // current变量所引用的就是要移除的元素 // 更新previous.next和current.next.prev的引用 // previous.next将指向current.next previous = current; // current.next.prev将指向previous current = current.next; } //将previous与current的下一项链接起来——跳过current previous.next = current.next; // {6} current.next.prev = previous; //新增的 } length--; return current.element; } else { return null; } };
|
从最后一个位置移除元素
从列表中间移除一个元素
从头部、从中间和从尾部移除一个元素
循环链表
循环链表和链表之间唯一的区别在于:最后一个元素指向下一个元素的指针(tail.next
)不是引用null
,而是指向第一个元素(head
)
双向循环链表有指向head元素的tail.next
,和指向tail元素的head.prev
。
总结:
JavaScript数据结构之链表
回看笔者往期高赞文章,也许能收获更多喔!
❤️关注+点赞+收藏+评论+转发❤️,原创不易,鼓励笔者创作更好的文章