©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>1.双向链表
双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的，一个链向下一个元素，另一个链向前一个元素
<>2.双向链表的优缺点
每次在插入或删除某个节点时，都需要处理四个引用，而不是两个，实现起来会困难些 相对于单向链表，所占内存空间更大一些；
但是，相对于双向链表的便利性而言，这些缺点微不足道。
<>3.双向链表的常见操作：
append（element）：向链表尾部添加一个新的项； inset（position，element）：向链表的特定位置插入一个新的项；
get（element）：获取对应位置的元素； indexOf（element）：返回元素在链表中的索引，如果链表中没有元素就返回-1；
update（position，element）：修改某个位置的元素； removeAt（position）：从链表的特定位置移除一项；
isEmpty（）：如果链表中不包含任何元素，返回trun，如果链表长度大于0则返回false；
size（）：返回链表包含的元素个数，与数组的length属性类似；
toString（）：由于链表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值；
forwardString（）：返回正向遍历节点字符串形式； backwordString（）：返回反向遍历的节点的字符串形式；
getHead():返回链表首个元素 getTail():返回链表最后一个元素
function DoubleLinklist(){ // 封装内部类，节点类 function Node(data){ this.data = data;
this.prev = null; this.next = null; } // 属性 this.head = null; this.tail = null;
this.length = 0; //方法 DoubleLinklist.prototype.append = function (element){ let
newNode= new Node(element); if(this.length == 0){ this.head = newNode; this.tail
= newNode; }else{ // 添加的不是一个节点 this.tail.next = newNode; newNode.prev = this.
tail; this.tail = newNode; } this.length++; } DoubleLinklist.prototype.
forwardString = function (){ let current = this.tail; let objString = ''; //
向前遍历 while(current){ objString += current.data + ' '; current = current.prev; }
return objString; } DoubleLinklist.prototype.backwardString = function(){ let
current= this.head; let objString = ''; while(current){ objString += current.
data+ ' '; current = current.next; } return objString; } DoubleLinklist.
prototype.toString = function(){ return this.backwardString(); } // 插入操作
DoubleLinklist.prototype.insert = function (position,element){ // 边界值判断 if(
position< 0 || position > this.length-1 ) return false; let newNode = new Node(
element); // 原链表为空插入的newNode是第一个节点 if(this.length == 0){ this.head = newNode;
this.tail = newNode; }else{ // 原链表不为空 if(position == 0){ this.head.prev =
newNode; newNode.next = this.head; this.head = newNode; } else if(position ==
this.length){ this.append(element); } else{ let current = this.head; let
previous= null; let index = 0; while(index++ < position){ previous = current;
current= current.next; } previous.next = newNode; newNode.prev = previous;
newNode.next = current; current.prev = newNode; } } this.length += 1; }
DoubleLinklist.prototype.get = function(position){ //边界值分析 if(position < 0 ||
position> this.length-1) return false; // 2.获取元素 if((this.length / 2) > position
){ // 此时从头开始遍历 let current = this.head; let index = 0; while(index++ < position)
{ current = current.next; } return current.data; }else{ // 从后遍历更快 let current =
this.tail; let index = this.length-1; while(index-- > position){ current =
current.prev; } return current.data; } } DoubleLinklist.prototype.indexOf =
function(element){ if(this.length == 0) return -1; let current = this.head; let
index= 0; while(current){ if(current.data == element){ return index; } index++;
current= current.next; } return -1; } // 更新 DoubleLinklist.prototype.update =
function(position,element){ // 边界值分析 if(position < 0 || position > this.length-1
) return false; let current = null; let index = 0; // 从头部开始遍历 if(position < this
.length / 2){ current = this.head; index = 0; while(index++ < position){ current
= current.next; } }else{ //从尾部开始遍历 current = this.tail; index = this.length - 1;
while(index-- > position){ current = current.prev; } } current.data = element;
return current.data; //返回修改成功的数据或者true } // 移除元素 DoubleLinklist.prototype.
removeAt = function(position){ // 边界值分析 if(position < 0 || position > this.
length-1) return false; let current = this.head; if(this.length == 1){ this.head
= null; this.tail = null; }else{ if(position == 0){ //首个元素 this.head.next.prev =
null; this.head = this.head.next; } else if(position == this.length-1){ //尾部元素
this.tail.prev.next = null; this.tail = this.tail.prev; } else{ //中间的元素 let
index= 0; while(index++ < position){ current = current.next; } current.prev.next
= current.next; current.next.prev = current.prev; } } this.length -= 1; return
current.data; //返回被删除节点的数据 } DoubleLinklist.prototype.remove = function(element)
{ // 1.根据element获取下标 let index = this.indexOf(element); // 2.根据index删除对应位置的节点
return this.removeAt(index); } DoubleLinklist.prototype.isEmpty = function(){
return this.length == 0; } DoubleLinklist.prototype.size = function(){ return
this.length; } // 获取链表第一个元素 DoubleLinklist.prototype.getHead = function(){
return this.head.data; } DoubleLinklist.prototype.getTail = function(){ return
this.tail.data; } }
测试代码：
let douList = new DoubleLinklist(); douList.append('aaaa'); douList.append(
'bbbb'); douList.append('cccc'); douList.insert(0,'FBI'); douList.insert(2,'BBC'
); douList.insert(5,'GGG'); console.log(douList); console.log(douList.
forwardString()); console.log(douList.backwardString()); console.log(douList.get
(2)); console.log(douList.get(4)); console.log(douList.indexOf('cccc')); console
.log(douList.update(1,'Amy')); console.log(douList.update(0,'jack')); console.
log(douList.update(4,'theshy')); console.log(douList.backwardString()); console.
log(douList.removeAt(0)); console.log(douList.removeAt(1)); console.log(douList.
backwardString()); console.log(douList.remove('Amy')); console.log(douList.
backwardString()); console.log(douList.size()); console.log(douList.getHead());
console.log(douList.getTail());