本文共 4766 字，大约阅读时间需要 15 分钟。

双向链表的优势与实现

单向链表的局限性

在单向链表中，虽然可以轻松从头到尾遍历，但回到前一个节点却非常困难。这使得单向链表难以支持复杂的操作，如插入删除等。

双向链表的优势

双向链表通过引入前驱和后驱指针，既可以从头到尾遍历，也能从尾到头遍历。这种双向连接方式有效解决了单向链表的局限性。

双向链表的特点

双向链表的每个节点包含三个部分：前驱指针（prev）、节点数据（item）和后驱指针（next）。链表的首节点的前驱指针为null，末节点的后驱指针为null。

双向链表的实现

function DoublyLinkedList() {    // 内部类：节点类    function Node(data) {        this.data = data;        this.prev = null;        this.next = null;    }    // 属性    this.head = null;    this.tail = null;    this.length = 0;}

双向链表的基本操作

DoublyLinkedList.prototype.append = function(data) {    var newNode = new Node(data);    if (this.length === 0) {        this.head = newNode;    } else {        var current = this.head;        while (current.next) {            current = current.next;        }        current.next = newNode;    }    this.length += 1;};

2. 链表转换成字符串：forwardString方法和backwardString方法

// forwardString方法DoublyLinkedList.prototype.forwardString = function() {    var current = this.head;    var resultString = '';    while (current) {        resultString += current.data + '';        current = current.prev;    }    return resultString;};// backwardString方法DoublyLinkedList.prototype.backwardString = function() {    var current = this.head;    var resultString = '';    while (current) {        resultString += current.data + '';        current = current.next;    }    return resultString;};

双向链表的高级操作

3. 插入方法：按位置插入节点

DoublyLinkedList.prototype.insert = function(position, data) {    // 越界判断    if (position < 0 || position > this.length) return false;    var newNode = new Node(data);    if (this.length === 0) {        this.head = newNode;        this.tail = newNode;    } else {        if (position === 0) {            newNode.next = this.head;            this.head.prev = newNode;            this.head = newNode;        } else if (position === this.length) {            this.tail.next = newNode;            newNode.prev = this.tail;            this.tail = newNode;        } else {            var current = this.head;            var index = 0;            while (index++ < position) {                current = current.next;            }            newNode.next = current;            newNode.prev = current.prev;            current.prev.next = newNode;            current.prev = newNode;        }    }    this.length += 1;    return true;};

2. 获取方法：获取指定位置的数据

// 方法1（普通方法）DoublyLinkedList.prototype.get = function(position) {    if (position < 0 || position >= this.length) return false;    var current = this.head;    var index = 0;    while (index++ < position) {        current = current.next;    }    return current.data;};// 方法2DoublyLinkedList.prototype.get = function(position) {    var current = this.tail;    var index = this.length - 1;    while (index-- > position) {        current = current.prev;    }    return current.data;};

3. 查找方法：返回元素在链表中的索引

DoublyLinkedList.prototype.indexOf = function(data) {    var current = this.head;    var index = 0;    while (current) {        if (current.data === data) {            return index;        } else {            current = current.next;            index++;        }    }    return -1;};

4. 更新方法：修改数据元素

DoublyLinkedList.prototype.update = function(position, newData) {    if (position < 0 || position >= this.length) return false;    var current = this.head;    var index = 0;    while (index++ < position) {        current = current.next;    }    current.data = newData;    return true;};

5. 删除方法：删除链表中的节点

DoublyLinkedList.prototype.removeAt = function(position) {    if (position < 0 || position >= this.length) return null;    var 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) {            current = this.tail;            this.tail.prev.next = null;            this.tail = this.tail.prev;        } else {            var index = 0;            while (index++ < position) {                current = current.next;            }            current.prev.next = current.next;            current.next.prev = current.prev;        }    }    this.length -= 1;    return current.data;};

6. 删除方法：根据具体数据删除链表中的节点

DoublyLinkedList.prototype.remove = function(data) {    var index = this.indexOf(data);    return this.removeAt(index);};

7. 判断是否为空

DoublyLinkedList.prototype.isEmpty = function() {    return this.length === 0;};

8. 获取链表长度

DoublyLinkedList.prototype.size = function() {    return this.length;};

9. 获取链表首节点数据

DoublyLinkedList.prototype.getHead = function() {    return this.head.data;};

10. 获取链表末节点数据

DoublyLinkedList.prototype.getTail = function() {    return this.tail.data;};

总结

双向链表通过引入前驱和后驱指针，显著提升了链表的灵活性和操作能力。相比单向链表，双向链表能够支持双向遍历，但在实现和内存占用上也存在一定的挑战。

转载地址：http://ohze.baihongyu.com/