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

链表的实现

一. 单向链表

// 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