6-双向链表
认识双向链表
单向链表：
- 只能从头遍历或者从尾遍历到头（一般从头到尾）。
- 也就是链表相连的过程是单向的，实现的原理是上一个链表中有一个指向一下一个的引用。
单向链表有一个比较明显的缺点：
- 我们可以轻松的到达下一个节点，但是回到前一个节点是很困难得，但是，实际开发中，经常会遇到需要回到上一个节点的情况。
- 举个例子：假设一个文本编辑用链表来存储文本，每一行用一个String对象存储在链表的一个节点中，当编辑器用户向下移动光标时，链表直接操作到下一个节点即可，但是当用于将光标向上移动呢？这个时候为了回到上一个节点，我们可能需要从first开始，依次走到想要的节点上。
双向链表：
- 既可以从头遍历到尾，又可以从尾遍历到头，也就是链表相连的过程是双向的。
- 一个节点既有向前连接的引用，也有一个向后连接的引用。
- 双向链表可以有效的解决单向链表中提到的问题。
双向链表的缺点：
- 每次在插入或删除某个节点时，需要处理四个节点的引用，而不是两个，也就是实现起来要困难一些。
- 平且相当于单向链表，必然占用内存空间更大一些。
- 但是这些缺点和我们使用起来的方便程度相比，是微不足道的。
双向链表图解：
双向链表的特点：
- 可以使用一个head和一个tail分布指向头部和尾部的节点。
- 每个节点都由三部分组成：previous指向前一个节点，item是当前元素，next指向着下一个节点。
- 双向链表的第一个节点的previous是null。
- 双向链表的最后的节点的next是null。
双向链表类的创建
// 创建双向链表的结构函数
function DoublyLinkedList() {
// 创建节点构造函数
function Node(element) {
this.element = element;
this.next = null;
this.prev = null; // 新添加的
}
// 定义属性
this.length = 0;
this.head = null;
this.tail = null // 新添加的
// 定义相关操作方法
}**
链表常见操作：
- 我们先来认识一下，链表中应该有哪些常见的操作。
- append（element）：向列表尾部添加一个新的项。
- insert（position,element）：向列表的特定位置插入一个新的项。
- get（position）：获取对应位置元素。
- indexOf（element）：返回元素在列表中的索引，如果列表中没有该元素则返回-1。
- update（position）：修改某个位置的元素。
- removeAt（position）：从列表的特定位置移除某一项。
- remove（element）：从列表中指定某个元素移除一项。
- isEmpty（）：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。
- size（）：返回链表包含的元素个数。于数组的length属性类似。
- toString（）：由于列表使用了Node类，就需要重写继承自JavaScript对象默认的tiString方法，让其只输出元素的值。
- forwardString（）：返回正向遍历的节点字符串形式。
- backwardString（）：返回反向遍历的节点字符串形式。
- append（element）：向列表尾部添加一个新的项。
append 尾部添加方法代码：
//append
DoublyLinkedList.prototype.append = function (data) {
let newNode = new Node(data);
if (this.head == null) { // 如果空表示未添加
this.head = newNode;// 这是第一个节点开始添加
this.tail = newNode;// 一个tail（尾部）始终指向这最后一个节点。
} else {
newNode.prev = this.tail;// 前面有一个节点了，新节点的previous指向当前链表结构的最后一个，此时新节点尚未添加到链表中。
this.tail.next = newNode;// 链表的尾的next指向新节点，意味着新节点添加到链表中了，
this.tail=newNode; // 重写this.tail(这个尾)，指向当前最后一个节点，也就是新添加进来的。
}
this.length += 1;
}
forwarbString 向前遍历代码 ：
//forwardString
DoublyLinkedList.prototype.forwardString = function () {
let current = this.tail;
let resultString = “”;
while (current) {
resultString += current.data;
current = current.prev;
}
return resultString;
}
backforwardString 向后遍历代码：
//backwardString
DoublyLinkedList.prototype.backwardString = function () {
let current = this.head;
let resultString = “”;
while (current) {
resultString += current.data;
current = current.next;
}
return resultString;
}
toString 从前向后遍历代码：
//toString
DoublyLinkedList.prototype.toString = function () {
return this.backwardString();
}
insert 插入数据 列如：1 2 3 4 5 在下标1处插入 1.5 原先下标的数据自动后移动 ：1 1.1 2 3 4 5 。
DoublyLinkedList.prototype.insert = function (position, data) {
if (position < 0 || position > this.length) return false;
let newNode = new Node(data);
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) {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
} else {
let current = this.head;
let index = 0;
while (index++ < position) {
current = current.next;
}
newNode.next = current;
newNode.prev = current.prev;
current.prev.next = newNode; //这一步要在当前的previous指向newNode之前，找到当前的previous.nex指向newNode。
current.prev = newNode;
}
}
this.length += 1;
return true;
}**
get（position）：获取位置上对应的元素。
DoublyLinkedList.prototype.get = function (position) {
let index = position;
if (index >= this.length) {
return null;
} else {
let current = this.head;
while (index) {
current = current.next;
index -= 1;
}
return current.data;
}
}
indexOf(element): 元素对应的下标位置。
DoublyLinkedList.prototype.indexOf = function (data) {
let current = this.head;
let index = 0;
while (current) {
if (current.data == data) {
return index
}
current = current.next;
index += 1;
}
return -1;
}
upData（position，newData）：对应下标跟新数据。
DoublyLinkedList.prototype.upData = function (position, newData) {
if (position >= this.length) return false;
let index = position
let current = this.head;
while (index) {
current = current.next;
index -= 1
}
current.data = newData;
return true;
}
removeAt(position):删除对应下标的数据
DoublyLinkedList.prototype.removeAt = function (position) {
// 1 越界判断。
if (position < 0 || position >= this.length) return null;
// 2 链表中只有一个节点
let current = this.head;
if (this.length == 1) {
this.head = null;
this.tail = null;
} else {
// 3 假设position == 0；删除第一个；
if (position == 0) {
this.head = this.head.next;
this.head.prev = null;
} else if (position == this.length - 1) {// 4 假设删除最后一个节点
current = this.tail;
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;
}
remove（element）：删除对应元素；
DoublyLinkedList.prototype.remove = function (element) {
// 调用已有方法但会元素对应下标，indexOf只可能返回 -1 （没找到），或者找到了的对应下标。
let index = this.indexOf(element);
// 调用已有方法，直接返回，removeAt已经做了越界处理。
return this.removeAt(index);
}
若有收获，就点个赞吧
0 人点赞
