链表
发表于 2017-12-17 11:29:16 | 分类于 算法 |
链表的定义
链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。
每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。
比较：链表、数组
- 数组
- 大多数语言中，数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素（JavaScirpt 的 Array 类方法可以帮助我们做这些事，但背后的情况同样是这样）。
- 数组可以直接访问任何位置的元素。
- 链表
- 添加或移除元素的时候，不需要移动其他元素。
- 访问链表中间的一个元素，需要从起点（表头）开始迭代链表，直到找到所需的元素。
链表的方法
append(element)：向链表尾部添加一个新大的项。
insert(position, element)：向链表特定位置插入一个新的项。
remove(element)：从列表移除一项。
indexOf(element)：返回元素在链表中的索引。如果没有该元素，则返回-1.
removeAt(position)：从链表特定位置移除一项。
isEmpty()：如果链表不包含任何元素，返回 true。如果链表长度大于 0 则返回 false。
size()：返回链表包含的元素个数。
toString()：输出链表包含的所有元素。
链表的创建
function LinkedList ( ) {
// Node 辅助类
// 用来表示要加入列表的项
// 包含一个 element 属性，即要添加到列表的值
// 以及一个 next 属性，即指向列表中下一个节点项的指针
var Node = function ( element ) {
this.element = element ;
this.next = null ;
} ;
// length ，存储列表项的数量
var length = 0 ;
// head，存储第一个节点的引用
var head = null ;
// LinkedList 类的方法
this.append = function ( element ) {
var node = new Node ( element ) ,
current ;
if ( head === null ) {
head = node ;
}
else {
current = head ;
while ( current.next ) {
current = current.next ;
}
current.next = node ;
}
length++ ;
} ;
this.insert = function ( position, element ) {
if ( position >= 0 && position <= length ) {
var node = new Node ( element );
var current = head;
var previous;
var index = 0;
if ( position === 0) {
node.next = current;
head = node;
}
else {
while ( index < position ) {
previous = current;
current = current.next;
index++;
}
node.next = current;
previous.next = node;
}
length++;
return true;
}
else {
return fasle;
}
} ;
this.removeAt = function ( position ) {
if ( position > -1 && position < length ) {
var current = head ,
previous ,
index = 0 ;
if (position === 0 ) {
head = current.next ;
}
else {
while ( index < position ) {
previous = current ;
current = current.next;
index++;
}
// 将 previous 与 current 的下一项链接起来：跳过 current ，从而移除它
previous.next = current.next ;
}
length--;
return current.element ;
}
else {
return null ;
}
} ;
this.indexOf = function ( element ) {
var current = head;
var index = -1;
while ( current ) {
if ( element === current.element ) {
return index;
}
index++;
current = current.next;
}
return -1;
} ;
this.remove = function ( element ) {
var index = this.indexOf ( element ) ;
return this.removeAt ( index ) ;
} ;
this.isEmpty = function ( ) {
return length === 0 ;
} ;
this.size = function ( ) {
return length ;
} ;
this.getHead = function ( ) {
return head ;
} ;
this.toString = function ( ) {
var current = head ,
string = "" ;
while ( current ) {
string += current.element ;
current = current.next ;
}
return string ;
} ;
}
双向链表
普通链表，一个节点只有链向下一个节点的链接。
双向链表，链接是双向的：一个链向下一个元素，另一个链像前一个元素。
双向链表的创建
funciton DoublyLinkedList ( ) {
var Node = function ( element ) {
this.element = element ;
this.next = null ;
// 新增的，用来保存前一项的引用。
this.prev = null ;
};
var length = 0 ;
var head = null ;
// 新增的，用来保存列表最后一项的引用
var tail = null ;
this.insert = function ( position , element ) {
// 检查越界值
if ( position >= 0 && position <= length ) {
var node = new Node ( element ) ,
current = head ,
previous ,
index = 0;
if ( position === 0) { // 在第一个位置添加
if ( ！head ) { // 新增的
head = node ;
tail = node ;
}
else {
node.next = current ;
current.prev = node ; // 新增的
head = node ;
}
}
else if ( positon === length ) { //最后一项 //新增的
current = tail ;
current.next = node ;
node.prev = current ;
tail = node ;
}
else {
while ( index < position ) {
previous = current ;
current = current.next ;
index++;
}
node.next = current ;
previous.next = node ;
current.prev = node ; // 新增的
node.prev = previous ; // 新增的
}
length++ ; // 更新列表长度
return ture ;
}
else {
return false ;
}
};
this.removeAt = function ( position ) {
//检查越界值
if ( position > -1 && position < length ) {
var current = head ,
previous ,
index = 0 ;
// 移除第一项
if( positon === 0 ) {
head = curent.next ;
// 如果只有一项，更新 tail
if ( length === 1 ) {
tail = null ;
}
else {
head.prev = null ;
}
}
else if ( position === length - 1 ) { // 最后一项
current = tail ;
tail =current.prev ;
tail.next = null ;
}
else {
while ( index < position ) {
previous = current ;
current = current.next ;
index++;
}
// 将 previous 与 current 的下一项链接起来，跳过 current
previous.next = current,next ;
current.next.prev = previous ;
}
length-- ;
return current.element ;
}
else {
return null ;
}
} ;
}
循环链表
循环链表与链表之间的唯一区别在于，循环链表最后一个元素指向下一个元素的指针（ tail.next ），是指向第一个元素（head），而不是引用 null。