客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
前言： 要存储多个元素，数组是最常用的数据结构，但是数组也有很多缺点：
所以要存储多个元素，另一个选择就是链表，不同于数组的是，链表中的元素在内存中不必是连续的空间。链表的每个元素有一个存储元素本身的节点和指向下一个元素的引用。
相对于数组，链表有一些缺点：
一、什么是单链表那么到底什么是单链表呢？ 它就类似于火车，火车头规连接一个节点，节点上有乘客，并且这个节点会连接到下一个节点，依次类推，如下所示： 我们的链表结构就是： 了解了直观上的链表，我们再来对单链表进行代码的封装。 二、单链表的封装首先，我们封装一个 如下所示：
function LinkedList(){
this.length = 0;
this.head = null;
//内部的类
function Node(data){
this.data = data;
this.next = null;
}
}
三、单链表的常用操作然后在里面添加单链表常用的操作。主要有：
接下来们就来一个一个实现。 1、append(element)方法-----向列表尾部添加一个项因为向链表尾部添加数据可能有两种情况：
所以我们就需要进行判断，如果链表为空，直接将头结点的指针指向新节点。
LinkedList.prototype.append = function(data){
var newNode = new Node(data);
// 判断链表是否为空
// 1.为空
if(this.length === 0){
this.head = newNode;
}else{
//不为空
var current = this.head;
if(current.next){
current = current.next;
}
current.next = newNode;
}
this.length += 1;
}
2、toString方法-----输出元素的值这个比较简单，主要是获取每一个元素，因为获取链表的任何元素都必须从第一个节点开始，所以我们可以从头结点开始，循环遍历每一个节点，并且取出其中的
LinkedList.prototype.toString = function(){
var current = this.head;
var ListStr = '';
while(current){
ListStr += current.data + ' ';
current = current.next;
}
return ListStr;
}
验证：创建几个新的节点，并打印
var list = new LinkedList();
list.append('a');
list.append('b');
list.append('c');
list.append('d');
list.append('e');
alert(list);
打印结果为： 3、insert方法-----向列表的特定位置插入一个项实现在任意位置插入数据的方法，首先判断插入的位置是否越界，然后在不越界的情况下分两种情况，如果插入到第一个位置，则表示新添加的节点是头，则需要将原来的头结点作为新节点的next,再让head指向新节点。如果插入到其他位置，则需要通过循环先找到节点位置，并在循环的过程中保存上一个节点和下一个节点，找到正确的位置后，将新节点的 代码如下：
LinkedList.prototype.insert = function(position,data){
if(position<0 || position >this.length){
return false;
}
var newNode = new Node(data);
var index = 0;
if(position == 0){
newNode.next = this.head;
this.head = newNode;
}else{
while(index++ < position){
var current = this.head;
var previous = null;
previous = current;
current = current.next;
}
newNode.next = current;
previous.next = newNode;
}
this.length += 1;
return true;
}
验证：在第1个位置插入xl,在第2个位置插入wh
list.insert(1,'xl')
list.insert(2,'wh')
alert(list)
4、get方法-----获取对应位置的元素这个方法相对简单，先对
LinkedList.prototype.get = function(position,data){
var current = this.head;
var index = 0;
if(position < 0 || position >= this.length){
return null;
}else{
while(index<position){
current = current.next;
index++;
}
return current.data;
}
}
验证：获取第三个位置的元素： alert( list.get(3)); 5、indexOf()方法-----返回元素在列表中的索引首先判断查找的元素的位置是否存在，如果不存在，返回-1。如果存在的话分两种情况，如果返回的元素在第一个位置，则直接返回第一个位置的索引。如果返回元素在其他位置，则需要通过循环先找到节点位置，这个过程中，索引需要跟着遍历的次数自加，找到正确元素的位置后，打印索引即为目标位置。
LinkedList.prototype.indexOf = function(data){
var index = 0;
var current = this.head;
while(current){
if(current.data == data){
return index;
}
else{
current = current.next;
index++;
}
}
return -1;
}
}
验证：获取c的索引：
alert(list.indexOf('c'));
6、update方法-----修改某个位置的元素这个方法和get方法很像，向后遍历，当
LinkedList.prototype.update = function(position,ele){
if(position<0 || position>=this.length){
return false;
}else{
var index = 0;
var current = this.head;
while(index++ <position){
current = current.next;
}
current.data = ele;
return true;
}
}
验证：修该第0个位置的元素为：bear
list.update(0,'bear')
alert(list)
7、removeAt方法-----从列表的指定位置移除一项首先判断删除项的位置是否越界，然后在不越界的情况下，给定两个临时节点
LinkedList.prototype.removeAt = function(position,data){
var current = this.head;
var previous = null;
var index = 0;
if(position<0 || position>=this.length){
return false;
}else{
while(index++ <position){
previous = currrent;
current = current.next;
}
previous.next = current.next;
this.length -= 1;
return true;
}
}
}
验证：移除第三个位置的元素：
list.removeAt(3)
alert(list)
8、remove方法-----从列表中移除一项先判断所要删除的元素是否在链表中，如果不在，返回
LinkedList.prototype.remove = function(ele){
var current = this.head;
var previous = null;
var index = 0;
while(current.data !== ele){
previous = current;
current = current.next;
index++;
}
previous.next = current.next;
}
验证：删除值为xl的元素：
list.remove('xl')
alert(list)
9、isEmpty方法-----判断链表是否为空根据
LinkedList.prototype.isEmpty = function(){
return this.length == 0;
}
验证： alert(list.isEmpty()) 9、size方法-----返回链表包含的元素个数直接返回元素的
LinkedList.prototype.size = function(){
return this.length;
}
验证： alert(list.size()) 到此这篇关于JavaScript实现单链表过程解析的文章就介绍到这了,更多相关JavaScript实现单链表内容请搜索极客世界以前的文章或继续浏览下面的相关文章希望大家以后多多支持极客世界！ |
请发表评论