目录
1、双向链表的定义
双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接；而在双向链表中，链表是双向的：一个链向下一个元素，另一个链向前一个元素。
?
2、双向链表结构的实现
2.1、双向链表常见方法和操作
append(element)向链表尾部追加一个新元素。
insert(position, element)向链表的指定位置插入一个新元素。
getElement(position)获取指定位置的元素。
indexOf(element)返回元素在链表中的索引。如果链表中没有该元素就返回 -1。
update(position, element)修改指定位置上的元素。
removeAt(position)从链表中的删除指定位置的元素。
remove(element)从链表删除指定的元素。
isEmpty()如果链表中不包含任何元素，返回trun，如果链表长度大于 0 则返回false。
size()返回链表包含的元素个数，与数组的length属性类似。
toString()由于链表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的toString方法，让其只输出元素的值。
forwardString()返回正向遍历节点字符串形式。
backwordString()返回反向遍历的节点的字符串形式。
2.2、双向链表的代码实现
class Node {//双向链表中的每个节点
constructor(data) {
this.pre = null;//节点指向前一个节点的指针
this.data = data;//节点携带的数据
this.next = null;//节点指向后一个节点的指针
}
}
class Dlinklist {
constructor() {
this.head = null;//链表头节点的指针
this.tail = null;//链表最后一个节点的指针
this.length = 0;//链表的长度
}
append(data) {
let newnode = new Node(data);
if (this.length == 0) {
this.head = newnode;
this.tail = newnode;
newnode.pre = this.head;
this.length++;
} else {
// 这里我用到循环来找到最后一个节点，其实this.tail已经记录了最后的一个节点，所以可以直接使用
let flag = this.head;
while (flag.next) {
flag = flag.next;
}
flag.next = newnode;
newnode.pre = flag;
this.tail = newnode;
this.length++;
}
}
insert(position, data) {//我设定的第一个节点序号为1，实际上应该为0比较符合实际
let newnode = new Node(data);
if (position <= 0 || position > this.length) {
return false;//如果插入的位置不符合实际就返回false
} else if (position == 1) {
// 如果插入头节点分为两种情况，一种是有节点，一种是没有节点
if (this.head == null) {
this.head = newnode;
this.tail = newnode;
this.length++;
} else {
this.head.pre = newnode;
newnode.next = this.head;
this.head = newnode;
newnode.pre = this.head;
this.length++;
};
} else {//我这里没有考虑直接插入末尾，写的时候忽略了这一点，等找个时间补上，其实逻辑上是差不多的
let previous = null;//记录前一个节点
let current = this.head;//当前的节点
let flag = 1;
while (flag < position) {
previous = current;
current = current.next;
flag++;
}
previous.next = newnode;
newnode.pre = previous;
newnode.next = current;
current.pre = newnode;
this.length++;
}
}
get(position) {
if (position < 0 || position > this.length) {
return false;
} else {
let flag = 1;
let current = this.head;
while (flag < position) {
current = current.next;
flag++;
}
return current;
}
}
indexOf(data) {
let previous = null;
let current = this.head;
let flag = 1;
while (current) {
previous = current;
current = current.next;
if (previous.data == data) {
return flag;
}
flag++;
}
return false;
}
updata(position, data) {
let previous = null;
let current = this.head;
let flag = 1;
while (flag < position) {
previous = current;
current = current.next;
flag++;
}
current.data = data;
}
removeAt(position) {
if (position < 0 || position > this.length) {
return false;
} else if (position == 1) {
this.head = this.head.next;
this.head.pre = this.head;
this.length--;
} else {
let previous = null;
let current = this.head;
let flag = 1;
while (flag < position) {
previous = current;
current = current.next;
flag++;
}
previous.next = current.next;
if (current.next != null) {
current.next.pre = previous;
} else {
this.tail = previous;
}
this.length--;
}
}
remove(data) {
let previous = null;
let current = this.head;
while (current) {
previous = current;
current = current.next;
if (previous.data == data) {
if (this.head.data == data) {
this.head = previous.next;
this.head.pre = this.head;
this.length--;
} else {
previous.pre.next = previous.next;
if (previous.next != null) {
previous.next.pre = previous.pre;
} else {
this.tail = previous.next;
}
this.length--;
}
break;
}
}
return false;
}
isEmpty() {
return this.length === 0;
}
size() {
return this.length;
}
toString() {
let previous = null;
let current = this.head;
let flag = 0;
let str = '';
while (flag < this.length) {
previous = current;
current = current.next;
str += previous.data + '';
flag++;
}
return str;
}
backKwordString() {
let current = this.head;
while (current.next) {
current = current.next;
}
let previous = current;
let str = '';
while (current.pre) {
previous = current;
current = current.pre;
str += previous.data;
if (previous == this.head) {
break;
}
}
return str;
}
}3、总结
记录学习，当个笔记