js数据结构---链表
Opened this issue · 0 comments
aermin commented
链表
概念：链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个 元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。
与数组的区别：相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。数组缺点：（在大多数语言中）数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素（尽管我们已经学过的JavaScript的array类方法可以帮 我们做这些事，但背后的情况同样是这样）。
然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到 所需的元素。
创建链表
function LinkedList() {
let Node = function(element){
this.element = element;
this.next = null;
};
let length = 0;
let head = null;
this.append = function(element){
let node = new Node(element),
current;
//向链表尾部追加元素
if (head === null){ // 列表中第一个节点 (场景1：列表为空，添加的是第一个元素)
head = node;
} else {
current = head; //（场景2：列表不为空，向其追加元素。）
while(current.next){ //循环列表，直到找到最后一项
current = current.next;
}
current.next = node;//找到最后一项，将其next赋为node，建立链接
}
length++; //更新列表的长度
};
//在任意位置插入元素
this.insert = function(position, element){
if (position >= 0 && position <= length){ //检查越界值
let node = new Node(element),
current = head,
previous,
index = 0;
if (position === 0){ //在第一个位置添加(场景1：需要在列表的起点添加一个元素，也就是第一个位置。)
node.next = current;
head = node;
} else { //(场景2：在列表中间或尾部添加一个元素)
while (index++ < position){ //不断地循环，直到找到要插入的位置
previous = current;
current = current.next;
}
node.next = current; //插入元素
previous.next = node;
}
length++; //更新列表的长度
return true;
} else {
return false;
}
};
//从链表中移除元素
this.removeAt = function(position){
if (position > -1 && position < length){//检查越界值
let current = head,
previous,
index = 0;
if (position === 0){ //移除第一项
head = current.next;
} else {
while (index++ < position){ //不断地循环，直到找到要移除目标的位置
previous = current;
current = current.next;
}
previous.next = current.next; //将previous与current的下一项链接起来：跳过current，从而移除它
}
length--; //更新列表的长度
return current.element;
} else {
return null;
}
};
this.remove = function(element){
let index = this.indexOf(element);
return this.removeAt(index);
};
this.indexOf = function(element){ //indexOf方法接收一个元素的值，如果在列表中找到 它，就返回元素的位置，否则返回-1。
let current = head,
index = 0;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
};
this.isEmpty = function() {
return length === 0;
};
this.size = function() {
return length;
};
this.getHead = function(){
return head;
};
this.toString = function(){ //toString方法会把LinkedList对象转换成一个字符串
let current = head,
string = '';
while (current) {
string += current.element + (current.next ? ', ' : '');
current = current.next;
}
return string;
};
this.print = function(){
console.log(this.toString());
};
}双向链表
双向链表和普通链表的区别：在链表中， 一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素， 另一个链向前一个元素。双向链表提供了两种迭代列表的方法：从头到尾，或者反过来。我们也可以访问一个特定节 点的下一个或前一个元素。在单向链表中，如果迭代列表时错过了要找的元素，就需要回到列表 起点，重新开始迭代。这是双向链表的一个优点。
function DoublyLinkedList() {
let Node = function(element){
this.element = element;
this.next = null;
this.prev = null; //新增的
};
let length = 0;
let head = null;
let tail = null; //新增的 用来保存对列表最后一 项的引用的tail属性
this.append = function(element){
let node = new Node(element),
current;
if (head === null){ //在第一个位置添加
head = node;
tail = node; //NEW
} else {
//attach to the tail node //NEW
tail.next = node;
node.prev = tail;
tail = node;
}
length++; //update size of list
};
this.insert = function(position, element){
if (position >= 0 && position <= length){ //检查越界值
let 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 (position === length) { //最后一项 //新增的
current = tail; //current变量将引用最后一个元素
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position){ //迭代 列表，直到到达要找的位置
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node; //新增的
node.prev = previous; //新增的
}
length++; //更新列表的长度
return true;
} else {
return false;
}
};
this.removeAt = function(position){
if (position > -1 && position < length){//检查越界值
let current = head,
previous,
index = 0;
if (position === 0){ //移除第一项
head = current.next; // {1}
//如果只有一项，更新tail //新增的
if (length === 1){
tail = null;
} else {
head.prev = null;
}
} else if (position === length-1){ //最后一项 //新增的
current = tail; // {4}
tail = current.prev;
tail.next = null;
} else {
while (index++ < position){ // 迭代列表，直到到达要找的 位置
previous = current;
current = current.next;
}
//将previous与current的下一项链接起来——跳过current
previous.next = current.next;
current.next.prev = previous; //新增的
}
length--; //更新列表的长度
return current.element;
} else {
return null;
}
};
this.remove = function(element){
let index = this.indexOf(element);
return this.removeAt(index);
};
this.indexOf = function(element){
let current = head,
index = -1;
if (element == current.element){
return 0;
}
index++;
while(current.next){
if (element == current.element){
return index;
}
current = current.next;
index++;
}
if (element == current.element){
return index;
}
return -1;
};
this.isEmpty = function() {
return length === 0;
};
this. size = function() {
return length;
};
this.toString = function(){
let current = head,
s = current ? current.element : '';
while(current && current.next){
current = current.next;
s += ', ' + current.element;
}
return s;
};
this.inverseToString = function() {
let current = tail,
s = current ? current.element : '';
while(current && current.prev){
current = current.prev;
s += ', ' + current.element;
}
return s;
};
this.print = function(){
console.log(this.toString());
};
this.printInverse = function(){
console.log(this.inverseToString());
};
this.getHead = function(){
return head;
};
this.getTail = function(){
return tail;
}
}