什么是链表?
链表和数组一样，可以用来储存元素
链表
链表的优点
1.链表的内存空间不是连续的，可以充分利用计算机的内存，实现内存动态管理
2.链表在创建时不用指定大小
3.链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组来说，效率要高很多
链表的缺点
1.链表要任何元素，都必须重头开始遍历，无法直接通过下标值取出元素
链表和数组的选择
如果是经常要取出数据，应该使用数组
如果是要频繁插入数据，应该使用链表
单向链表的常见操作
append(element)：向链表尾部添加新的元素
insert(position，element)：向链表的指定位置添加元素
get(position)：获取元素的位置
indexOf(element)：返回元素的下标值，没有则返回 -1
updata(position)：修改某个位置的元素
removeAt(position)：移除指定位置的元素
remove(element)：移除指定的元素
isEmpty()：查看链表长度，返回布尔值
size()：返回链表的长度
toString()：按字符串输出链表的值
链表的封装
//封装链表类
function LinkedList() {
function Node(data) {
this.data = data
this.next = null
}
//属性
this.head = null
this.length = 0
//append方法
LinkedList.prototype.append = function (data) {
//创建新节点
var newNode = new Node(data)
//判断是否添加的是第一节点
if (this.length == 0) {
this.head = newNode
} else {
var current = this.head
while (current.next) {
current = current.next
}
current.next = newNode
}
this.length += 1
}
//insert方法
LinkedList.prototype.insert = function (position, data) {
//判断下标是否越界
if (position < 0 || position > this.length) {
return false
}
//创建newNode
var newNode = new Node(data)
//判断插入的位置是否为第一个
if (position == 0) {
newNode.next = this.head
this.head = newNode
} else {
var index = 0
var current = this.head
var previous = null
while (index++ < position) {
previous = current
current = current.next
}
newNode.next = current
previous.next = newNode
}
this.length += 1
}
//get方法
LinkedList.prototype.get = function (position) {
//越界判断
if (position < 0 || position >= this.length) {
return null
}
//获取data
var current = this.head
var index = 0
while (index++ < position) {
current = current.next
}
return current.data
}
//indexOf方法
LinkedList.prototype.indexOf = function (data) {
var current = this.head
var index = 0
while (current) {
if (current.data == data) {
return index
}
current = current.next
index += 1
}
//没有找到
return -1
}
//updata方法
LinkedList.prototype.updata = function (position, newData) {
//越界判断
if (position < 0 || position >= this.length) {
return false
}
//查找节点
var current = this.head
var index = 0
while (index++ < position) {
current = current.next
}
//修改data
current.data = newData
return true
}
//removeAt方法
LinkedList.prototype.removeAt = function (position) {
//越界判断
if (position < 0 || position >= this.length) {
return false
}
//查看是否为第一个节点
var current = this.head
if (position == 0) {
this.head = this.head.next
} else {
var index = 0
var previous = null
while (index++ < position) {
previous = current
current = current.next
}
position.next = current.next
}
this.length -= 1
return current.data
}
//remove方法
LinkedList.prototype.remove = function (data) {
//获取位置
var position = this.indexOf(data)
//删除节点
return this.removeAt(position)
}
//isEmpty方法
LinkedList.prototype.isEmpty = function () {
return this.length == 0
}
//size方法
LinkedList.prototype.size = function () {
return this.length
}
//toString方法
LinkedList.prototype.toString = function () {
//定义变量,获取第一个节点
var current = this.head
var str = ""
//循环获取节点
while (current) {
str += current.data + " "
current = current.next
}
return str
}
}
END
