JavaScript 数据结构与算法 - 链表练习

链表的实现

一、单向链表

// Node 类
function Node (element) {
    this.element = element;
    this.next = null;
}
// LinkedList 类
function LList () {
    this.head = new Node('head');
    this.find = find;
    this.insert = insert;
    this.findPrevious = findPrevious;
    this.remove = remove;
    this.display = display;
}
// 查找
function find (item) {
    let currNode = this.head;
    while (currNode.element !== item) {
        currNode = currNode.next;
    }
    return currNode;
}
// 插入
function insert (newElement, item) {
    let newNode = new Node(newElement);
    let current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}
// 显示
function display () {
    let currNode = this.head;
    while (currNode.next !== null) {
        currNode = currNode.next;
        console.log(currNode.element);
    }
}
// 检查节点
function findPrevious (item) {
    let currNode = this.head;
    while (currNode.next !== null && currNode.next.element !== item) {
        currNode = currNode.next;
    }
    return currNode;
}
// 删除
function remove (item) {
    let prevNode = this.findPrevious(item);
    if (prevNode.next !== null) {
        prevNode.next = prevNode.next.next;
    }
}

二、双向链表

function Node (element) {
    this.element = element;
    this.next = null;
    this.previous = null;
}
function DList () {
    this.head = new Node('head');
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.remove = remove;
    this.findLast = findLast;
    this.dispReverse = dispReverse;
}
function dispReverse () {
    let currNode = this.head;
    currNode = this.findLast();
    while (currNode !== null && currNode.element !== 'head') {
        console.log(currNode.element);
        currNode = currNode.previous;
    }
}
function findLast () {
    let currNode = this.head;
    while (currNode.next !== null) {
        currNode = currNode.next;
    }
    return currNode;
}
function remove (item) {
    let currNode = this.find(item);
    if (currNode.next !== null) {
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.next = null;
        currNode.previous = null;
    }
}
function display () {
    let currNode = this.head;
    while (currNode.next !== null) {
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}
function find (item) {
    let currNode = this.head;
    while (currNode.element !== item) {
        currNode = currNode.next;
    }
    return currNode;
}
function insert (newElement, item) {
    let newNode = new Node(newElement);
    let currNode  = this.find(item);
    newNode.next = currNode.next;
    newNode.previous = currNode;
    currNode.next = newNode;
}

三、循环链表

// Node类
function Node (element) {
    this.element = element;
    this.next = null;
}
// LinkedList类
function CList () {
    this.head = new Node('head');
    // 修改
    this.head.next = this.head;
    this.find = find;
    this.insert = insert;
    this.findPrevious = findPrevious;
    this.remove = remove;
    this.display = display;
}
// 其他
// ...

练习

一、实现 advance(n) 方法，使当前节点向前移动 n 个节点。

// 向前移动一位
DList.prototype.goPrevious = function (thisNode) {
    let node1, node2, node3, node4;
    if (thisNode.previous.element !== 'head') {
        node1 = thisNode.previous.previous;
        node2 = thisNode.previous;
        node3 = thisNode;
        node4 = thisNode.next;
        // 位置调整
        node1.next = node3;
        node3.previous = node1;
        node3.next = node2;
        node2.previous = node3;
        node2.next = node4;
        node4.previous = node2;
    }
};
DList.prototype.advance = function (n, item) {
    let currNode  = this.find(item);
    while (n--) {
        this.goPrevious(currNode);
    }
};
// 示例
let names = new DList();
names.insert('Mazey', 'head');
names.insert('Cherrie', 'Mazey');
names.insert('John', 'Cherrie');
names.insert('Luna', 'John');
names.insert('Ada', 'Luna');
names.display();
console.log('---');
names.advance(2, 'Luna');
names.display(); // Mazey, Luna, Cherrie, John, Ada

二、实现 back(n) 方法，使当前节点向后移动 n 个节点。

// 向前移动一位
DList.prototype.goNext = function (thisNode) {
    let node1, node2, node3, node4;
    if (thisNode.next.element !== null) {
        node1 = thisNode.previous;
        node2 = thisNode;
        node3 = thisNode.next;
        node4 = thisNode.next.next;
        // 位置调整
        node1.next = node3;
        node3.previous = node1;
        node3.next = node2;
        node2.previous = node3;
        node2.next = node4;
        node4.previous = node2;
    }
};
DList.prototype.back = function (n, item) {
    let currNode  = this.find(item);
    while (n--) {
        this.goNext(currNode);
    }
};
// 示例
let names = new DList();
names.insert('Mazey', 'head');
names.insert('Cherrie', 'Mazey');
names.insert('John', 'Cherrie');
names.insert('Luna', 'John');
names.insert('Ada', 'Luna');
names.display();
console.log('---');
names.back(2, 'Cherrie');
names.display(); // Mazey, John, Luna, Cherrie, Ada