储存多个元素,数组是最常用的。无论何种语言,都实现了数组。但是大多数语言中,数组的长度是固定的。数组修改操作的成本非常高。
=> 链表分类
限于篇幅,此处只讨论单链表中的无头链表。
链表储存有序的元素集合,但不同于数组,链表元素的内存不是连续放置的。每个元素包括:
相对于传统的数组,链表的好处在于添加或移动元素时,无需修改其他元素。
现实中,定向越野就是一种链表。去指定的地点寻找下一个线索(指针)。寻找终点,意味着必须遍历中间所有节点。另外还有猴子捞月。
创建链表需要明确更多的规则。
class LinkList{
constructor(){
this.Node=function(element){
this.element=element;
this.next=null;
}
this.length=0;//链表的长度
this.head=null;//链表的头部
}
// ..
}
一个单链表中,一个元素Node包括以下信息:
//调用时:
var Node=this.Node;
var node=new Node();
在这里声明一个内部的类 Node
。
创建一个链表,需要满足以下功能:
如果是空链表
非空链表
// 追加元素
append(element){
let Node=this.Node;
let node=new Node(element);
let current=null;
if(this.head==null){
this.head=node;
}else{
// 指针从头部开始,一直根据索引值遍历
current=this.head;
while (current.next) {
current=current.next;
}
// 赋值
current.next=node;
}
this.length++;
}
如果是空链表
如果是非空链表
//任意位置插入元素
insert(position,element){
if(position>-1&&position<this.length){
let Node=this.Node;
let node=new Node(element);
let current=this.head;
let previous=null;
let index=0;
// 第一个位置添加
if(position==0){
node.next=this.head;
this.head=node;
}else{
while (index++<position) {
previous=current
current=current.next;
}
node.next=current;
previous.next=node;
}
this.length++;
return true
}else{
return false
}
}
非空链表:
空链表
// 移除
removeAt(position){
// 当位置在链表索引范围内,移除方能成立
if(position>-1&&position<this.length){
// 需要两个节点,方能实现操作
let current=this.head;
let previous=null;
let index=0;
if(position==0){
// 移除第一项,把头部之后的节点赋值给头部。即可!
this.head=current.next;
}else{
// 定位元素位置不断递进,直至找到position时终止。
while (index++<position) {
previous=current
current=current.next;
}
// 将previous和current的下一项链接起来,跳过current,从而实现移除。
previous.next=current.next;
}
this.length--;
return current.element;
}
}
// 返回元素在链表中的位置,-1为找不到
indexOf(element){
let current=this.head;
let index=0;//应从0开始,原书有误。
while (current) {
if(element==current.element){
return index
}
index++;
current=current.next;
}
return -1
}
//根据元素删除元素
remove(element){
let index=this.indexOf(element);
return this.removeAt(index);
}
// 返回长度
size(){
return this.length==0;
}
// 返回长度
size(){
return this.length;
}
//吧linkList转换为一个字符串
toString(){
let current=this.head;
let string='';
while (current) {
string+=current.element+(current.next?'->':'');
current=current.next;
}
return string;
}
// 获取头部
getHead(){
return this.head;
}
// 获取尾节点
getTail(){
let current=this.head;
while (current.next) {
current=current.next;
}
return current.element;
}
那么,来测试一下吧。
// 测试用例
let a=new LinkList();
a.append('djtao')
a.append('djt')
a.append('taotao')
console.log(a.toString())
a.insert(1,'dangjingtao')
console.log(a.toString())
a.removeAt(2)
console.log(a.toString())
a.remove('dangjingtao')
console.log(a.indexOf('taotao'))
console.log(a.toString())
输出结果
之前的栈和队列,都是基于数组实现的。
这个还是比较简单的:
// 用链表实现stack
class Stack{
constructor(){
this.linkList=new LinkList();
}
push(item){
this.linkList.append(item);
}
pop(){
let size=this.linkList.size();
return this.linkList.removeAt(size-1)
}
top(){
return this.linkList.getTail();
}
print(){
console.log(this.linkList.toString());
}
size(){
return this.linkList.size();
}
isEmpty(){
return this.linkList.size()==0;
}
}
// 测试用例
var a=new Stack();
a.push('djt')
a.push('djtao')
a.push('dangjingtao')
a.print()
a.pop();
a.print();
a.pop();
a.print()
a.pop();
a.print()
a.pop();
a.print()
console.log(a.isEmpty())
// 基于链表实现queue
class Queue{
constructor(){
this.linkList=new LinkList();
}
enQueue(item){
this.linkList.append(item)
}
deQueue(){
this.linkList.removeAt(0)
}
// 。。。
}
如果一个人号称”精通数据结构“,那大概意思是能做以下这些题。
在上下文环境中,使用递归 recursion
和迭代 iteration
两种方式实现函数
var Node=function(element){
this.element=element;
this.next=null;
}
var node1=new Node(1);
var node2=new Node(2);
var node3=new Node(3);
var node4=new Node(4);
var node5=new Node(5);
node1.next=node2;
node2.next=node3;
node3.next=node4;
node4.next=node5;
function print(node){
var current=node;
var str='';
while (current) {
str+=current.element.toString()+(current.next!==null?'->':'');
current=current.next;
}
console.log(str)
}
递归的思路是(甩锅):
// 递归
var recursion=function(node,previous){
let next=node.next;
// 尾部
if(!next){
node.next=previous;
return node;
}else{
// 互换
// 头部
if(!previous){
previous=node;
node.next=null;
}else{
node.next=previous;
}
return recursion(next,node)
}
}
print(recursion(node1))//5->4->3->2->1
迭代的思路:
见注释
// 迭代
var iteration=function(node){
let current=node;//当前要反转的节点
let previous=null;//前一个节点,也用于储存返回值
while (current) {
let next=current.next;//获取下一个节点
current.next=previous;//获取完之后把储存位置给previous
previous=current;//previous叫出去之后,开始后滑
current=next;//current后滑
}
return previous;
}
print(iteration(node1))
【小结】拿到前后节点,只考虑单个节点的情况。