双向链表和普通链表的区别是，普通链表中一个节点只有一个next指针指向下一个节点，双向链表有2个指针，一个指向下一个节点，一个指向前面一个节点。
双向链表的结构图
双向链表的代码实现：
function DoubleLinkedList() {
var Node = function(element) {
this.element = element;
this.next = null;
this.prev = null;
}
var head = null,
tail = null,
length = 0;
this.append = function(element) {
const node = new Node(element);
if(length === 0) {
head = node;
tail = node;
}else {
tail.next = node;
node.prev = tail;
tail = node;
}
length++;
return true;
}
this.insert = function(position, element) {
if(position>=0 && position <=length) {
var current = head,
previous,
index = 0;
const node = new Node(element);
if(position === 0) {
if(!head) {
head = node;
tail = node;
} else {
node.next = current;
current.prev = node;
head = current;
}
} else if(position === length) {
current = tail;
node.prev = current;
current.next = node;
tail = node;
}else {
while(index++ < position) {
previous = current;
current = current.next;
}
node.prev = previous;
previous.next = node;
node.next = current;
current.prev = node;
}
length++;
return true;
}else {
return false;
}
}
this.removeAt = function(position) {
if(position>=0 && position < length) {
var current = head,
previous,
index = 0;
if(position === 0) {
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;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
}else {
return null;
}
}
this.remove = function(element) {
const position = this.indexOf(element);
return this.removeAt(position);
}
this.indexOf = function(element) {
var current = head,
previous,
index = 0;
while(current) {
if(element === current.element) {
return index;
}
index++;
current = current.next;
}
}
this.isEmpty = function() {
return length === 0
}
this.size = function() {
return this.length
}
this.getHead = function() {
return head;
}
this.getTail = function() {
return tail;
}
this.toString = function() {
var current = head,
string = '';
while(current) {
string += String(current.element);
current = current.next;
}
return string;
}
}
var list = new DoubleLinkedList();
list.append('aa');
list.append('bb');
console.log(list.toString()); // aabb
list.insert(1, 'cc')
list.insert(1, 'dd')
console.log(list.toString()); // aaddccbb
list.removeAt(1);
console.log(list.toString()); // aaccbb
console.log(list.indexOf('cc')); // 1
网友评论