链表
- append(element): 向列表尾部添加一个新的项
- insert(position,element)：向列表的特定位置插入一个新的项
- remove(element): 从列表中移除一项
- indexOf(element): 返回元素在列表中的索引.如果列表中没有该元素则返回-1.
- removeAt(position):从列表的特定位置移除一项
- isEmpty(): 如果链表中不包含任何元素,返回true,如果链表长度大于0则返回false
- size(): 返回链表包含的元素个数。与数组的length属性类似
- toString(): 由于列表项使用了Node类,就需要重写继承自JavaScript对象默认的toString()方法,让其只输出元素的值
链表实现append,getHead
likedList.js
var LikedList = function() {
//链表头
var head = null;
// 链表长度
var length = 0;
// 节点
var Node = function(el) {
this.el = el;
this.next = null;
}
//链表尾添加元素
this.append = function(el) {
var node = new Node(el) // 1 2
if (head == null) {
head = node; //head =1
} else {
var current = head; //current=1
while (current.next) { //null
current = current.next;
}
//while循环执行完之后，current已经是链表的最后一项了
current.next = node //current.next = node = 2
}
length++
}
this.getHead = function() {
return head;
}
}
实例化
链表插入 insert
likedList.js
var LikedList = function() {
//链表头
var head = null;
// 链表长度
var length = 0;
// 节点
var Node = function(el) {
this.el = el;
this.next = null;
}
//链表尾添加元素
this.append = function(el) {
var node = new Node(el) // 1 2
if (head == null) {
head = node; //head =1
} else {
var current = head; //current=1
while (current.next) { //null
current = current.next;
}
//while循环执行完之后，current已经是链表的最后一项了
current.next = node //current.next = node = 2
}
length++
}
//链表某一个位置添加元素
this.insert = function(position, el) {
//越界
if (position > -1 && position < length) {
var node = new Node(el);
if (position == 0) {
var current = head;
head = node;
head.next = current;
} else {
var index = 0;
var current = head;
var previous = null;
while (index < position) {
previous = current;
current = current.next;
index++
}
previous.next = node;
node.next = current;
}
length++
}
}
this.getHead = function() {
return head;
}
}
实例化
remove removeAt
likedList.js
var LikedList = function() {
//链表头
var head = null;
// 链表长度
var length = 0;
// 节点
var Node = function(el) {
this.el = el;
this.next = null;
}
this.removeAt = function(position) {
if (position > -1 && position < length) {
if (position == 0) {
var current = head;
head = current.next;
} else {
var current = head;
var previous = null;
var index = 0;
while (index < position) {
previous = current
current = current.next;
index++
}
previous.next = current.next;
}
length--
return current
}
return null
}
this.indexOf = function(el) {
var current = head;
var index = 0;
while (current) {
if (current.el == el) {
return index
}
current = current.next
index++
}
return -1
}
this.remove = function(el) {
return this.removeAt(this.indexOf(el))
}
}
实例化
链表所有功能
likedList.js
var LikedList = function() {
//链表头
var head = null;
// 链表长度
var length = 0;
// 节点
var Node = function(el) {
this.el = el;
this.next = null;
}
//链表尾添加元素
this.append = function(el) {
var node = new Node(el) // 1 2
if (head == null) {
head = node; //head =1
} else {
var current = head; //current=1
while (current.next) { //null
current = current.next;
}
//while循环执行完之后，current已经是链表的最后一项了
current.next = node //current.next = node = 2
}
length++
}
//链表某一个位置添加元素
this.insert = function(position, el) {
//越界
if (position > -1 && position < length) {
var node = new Node(el);
if (position == 0) {
var current = head;
head = node;
head.next = current;
} else {
var index = 0;
var current = head;
var previous = null;
while (index < position) {
previous = current;
current = current.next;
index++
}
previous.next = node;
node.next = current;
}
length++
}
}
//删除指定位置的元素
this.removeAt = function(position) {
if (position > -1 && position < length) {
if (position == 0) {
var current = head;
head = current.next;
} else {
var current = head;
var previous = null;
var index = 0;
while (index < position) {
previous = current
current = current.next;
index++
}
previous.next = current.next;
}
length--
return current
}
return null
}
//查找链表元素下标
this.indexOf = function(el) {
var current = head;
var index = 0;
while (current) {
if (current.el == el) {
return index
}
current = current.next
index++
}
return -1
}
//删除指定元素
this.remove = function(el) {
return this.removeAt(this.indexOf(el))
}
// 是否为空
this.isEmpty = function() {
return length == 0;
}
//链表长度
this.size = function() {
return length
}
//链表头
this.getHead = function() {
return head;
}
}
