JS 实现单向链表、双向链表

JS 实现单向链表、双向链表

单向链表

在计算机科学中，单链表是一种数据结构，保存了一系列链接的节点。 每个节点中包含数据和一个可指向另一个节点的指针。

单链表的操作

因为单链表包含节点，这两者的构造函数可以是两个独立的构造函数，所以我们需要些构造函数：Node 和 SinglyList

Node

• data 存储数据
• next 指向链表中下一个节点的指针

SinglyList

• _length 用于表示链表中的节点数量
• head 分配一个节点作为链表的头
• add(value) 向链表中添加一个节点
• searchNodeAt(position) 找到在列表中指定位置 n 上的节点
• remove(position) 删除指定位置的节点

单链表实现

function Node(data) {
	this.data = data;
	this.next = null;
}
 
function SinglyList() {
	this._length = 0;
	this.head = null;
}
 
SinglyList.prototype.add = function(value) {
	var node = new Node(value),
		currentNode = this.head;
 
	// 1st use-case: an empty list
	if (!currentNode) {
		this.head = node;
		this._length++;
 
		return node;
	}
 
	// 2nd use-case: a non-empty list
	while (currentNode.next) {
		currentNode = currentNode.next;
	}
 
	currentNode.next = node;
 
	this._length++;
	 
	return node;
};
 
SinglyList.prototype.searchNodeAt = function(position) {
	var currentNode = this.head,
		length = this._length,
		count = 1,
		message = {failure: 'Failure: non-existent node in this list.'};
 
	// 1st use-case: an invalid position
	if (length === 0 || position < 1 || position > length) {
		throw new Error(message.failure);
	}
 
	// 2nd use-case: a valid position
	while (count < position) {
		currentNode = currentNode.next;
		count++;
	}
 
	return currentNode;
};
 
SinglyList.prototype.remove = function(position) {
	var currentNode = this.head,
		length = this._length,
		count = 0,
		message = {failure: 'Failure: non-existent node in this list.'},
		beforeNodeToDelete = null,
		nodeToDelete = null,
		deletedNode = null;
 
	// 1st use-case: an invalid position
	if (position < 0 || position > length) {
		throw new Error(message.failure);
	}
 
	// 2nd use-case: the first node is removed
	if (position === 1) {
		this.head = currentNode.next;
		deletedNode = currentNode;
		currentNode = null;
		this._length--;
		 
		return deletedNode;
	}
 
	// 3rd use-case: any other node is removed
	while (count < position) {
		beforeNodeToDelete = currentNode;
		nodeToDelete = currentNode.next;
		count++;
	}
 
	beforeNodeToDelete.next = nodeToDelete.next;
	deletedNode = nodeToDelete;
	nodeToDelete = null;
	this._length--;
 
	return deletedNode;
};

var list = new SinglyList()
list.add(1);
list.add(2);
list.add(3);
var node = list.searchNodeAt(3);
console.log(node)

双向链表

双向链表具有单链表的所有功能，并将其扩展为在链表中可以进行双向遍历。 换句话说，我们可从链表中第一个节点遍历到到最后一个节点；也可以从最后一个节点遍历到第一个节点。

双向链表的操作

我们的链表将包括两个构造函数：Node和DoublyList。看看他们是怎样运作的。

Node

• data 存储数据。
• next 指向链表中下一个节点的指针。
• previous 指向链表中前一个节点的指针。

DoublyList

• _length 保存链表中节点的个数
• head 指定一个节点作为链表的头节点
• tail 指定一个节点作为链表的尾节点
• add(value) 向链表中添加一个节点
• searchNodeAt(position) 找到在列表中指定位置 n 上的节点
• remove(position) 删除链表中指定位置上的节点

双向链表的实现

function Node(value) {
    this.data = value;
    this.previous = null;
    this.next = null;
}
 
function DoublyList() {
    this._length = 0;
    this.head = null;
    this.tail = null;
}
 
DoublyList.prototype.add = function(value) {
    var node = new Node(value);
 
    if (this._length) {
        this.tail.next = node;
        node.previous = this.tail;
        this.tail = node;
    } else {
        this.head = node;
        this.tail = node;
    }
 
    this._length++;
 
    return node;
};
 
DoublyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'};
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: a valid position
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
 
    return currentNode;
};
 
DoublyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
 
        // 2nd use-case: there is a second node
        if (!this.head) {
            this.head.previous = null;
        // 2nd use-case: there is no second node
        } else {
            this.tail = null;
        }
 
    // 3rd use-case: the last node is removed
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    // 4th use-case: a middle node is removed
    } else {
        while (count < position) {
            currentNode = currentNode.next;
            count++;
        }
 
        beforeNodeToDelete = currentNode.previous;
        nodeToDelete = currentNode;
        afterNodeToDelete = currentNode.next;
 
        beforeNodeToDelete.next = afterNodeToDelete;
        afterNodeToDelete.previous = beforeNodeToDelete;
        deletedNode = nodeToDelete;
        nodeToDelete = null;
    }
 
    this._length--;
 
    return message.success;
};