javascript - JavaScript 中的 LinkedList，如何将更改附加到列表？

Question

我在 JavaScript 中遇到了变量的引用问题，我一直在用头撞墙试图解决这个问题。

我正准备教授一门数据结构类(class)，在至少 10 年没有看过这些 Material 后，我正在复习它。

我在理论上了解链接列表，但出于某种原因，我正在努力想出实际在 JavaScript 中运行的代码(我选择 JavaScript 是因为这是我的类(class)最了解的)

这是我的代码:

let LinkedList  = {
    head: {},
    tail: {}
};

let Node = {
    data: {},
    next: {}
}

function isObjectEmpty(obj1) {
    return Object.keys(obj1).length === 0 && obj1.constructor === Object;
}

function count(node, counter) {
    if (node.next) {
        return 1 + count(node.next, counter);
    }
    return counter;
}

/**
 * Adds data to LinkedList
 * @param {LinkedList} list
 * @param {Node} data
 */
function add_node(list, data) {
    let temp = Object.assign({}, Node);
    temp.data = data;
    temp.next = {};

    if (Object.keys(list.head).length === 0) {
        list.head = temp;
        list.tail = temp;
    } else {
        list.tail.next = temp;
        list.tail = temp;
    }
    return list;
}
function insert(l, n, position) {
    if (position <= 0) {
        position = 0;
    } else {
        position = position - 1;
    }

    var list = Object.assign({}, l);
    var node = Object.assign({}, Node);
    node.data = n;

    // this only counts elements on the list.
    var elements = count(list.head, 0);

    if (position > elements) {
        return list;
    }

    var currentPosition = list.head;
    var counter = 0;

    while (!isObjectEmpty(currentPosition)) {
        if (position === counter) {
            var tmp = currentPosition;
            currentPosition = node;
            currentPosition.next = tmp.next;
            return list;
        }
        currentPosition = currentPosition.next;
        counter++;
    }

    return list;
}

// how to use the function
let songs = [
{id: '1', name: 'Kamikaze', artist: 'Eminem', releaseDate: '2018-08-31'},
{id: '2', name: 'despacito', artist: 'Luis Fonsi', releaseDate: '2018-08-31'},
{id: '3', name: 'La tortura', artist: 'Shakira', releaseDate: '2018-08-31'},
{id: '4', name: 'Roar', artist: 'Roar', releaseDate: '2018-08-31'},
 ];

let list = Object.assign({}, LinkedList);
    songs.forEach((song) => {
        add_node(list, song); // nothing special, just builds the linkedlist
     });

list = insert(list, {id: '5', name: 'Havana', artist:'who knows', releaseDate:'2018-01-01'}, 3); 
console.log(list); // new object isn't there.

这个函数应该在链表的任意位置插入一个元素。它有点管用。问题是返回的列表在重新关联之前保留了对旧对象的引用。

如果你在这个 block 中放置一个调试器:

    if (position === counter) {
        var tmp = currentPosition;
        currentPosition = node;
        currentPosition.next = tmp.next;
        return list;
    }

您可以看到我实际上成功地将新节点插入到我想要的位置。

但是如果你console.loglist结构，你会发现新插入的节点找不到了。

我不确定我哪里失败了，或者为什么列表保留了旧的引用而不遵循新的“路径”。

非常感谢任何指向正确方向的指示。

Answer 1

If you put a debugger in this block:

if (position === counter) {
    var tmp = currentPosition;
    currentPosition = node;
    currentPosition.next = tmp.next;
    return list;
}

You can see that I'm actually successfully inserting the new node where I want to

不，你不知道。如果我们去掉 tmp 和 currentPosition 赋值混淆，那段代码等同于

if (position === counter) {
    node.next = currentPosition.next;
    return list;
}

所发生的只是您将列表的尾部复制到新节点上，但您从未真正将该节点作为列表中当前节点的 next 插入。它缺少一个

currentPosition.next = node;

---

其他几点:

• 不要使用isObjectEmpty 和空对象来表示“无节点”。请改用 null。如果出于某些教学原因您不想引入 null，请在对象上使用 bool 值 .isNode 属性来区分具有数据的节点和空节点。<

• 避免Object.assign。你的用法真的很单一。在

  let temp = Object.assign({}, Node);
  temp.data = data;
  temp.next = {};
  

  您正在直接覆盖刚刚从 Node 复制的值 - 更好地简化为使用对象字面量:

  let temp = {data, next: {}};
  

  在 var list = Object.assign({}, l); 中，您根本不想创建新对象。您将改变传入的列表，因此您应该保留它。 (如果你想用不可变的数据结构制作纯函数，你必须让所有的节点也不可变，并且为了插入，克隆整个列表直到所需的位置)。

• 如果您对 Object.assign 的意图是创建以后可能涉及您不打算覆盖的其他属性(或方法)的新对象，请改用工厂函数。

• 不要预先计算列表。一次性插入，如果在要插入的位置之前到达列表末尾，则return。

function makeLinkedList() {
    return { head: null, tail: null };
}

function makeNode(data, next = null) {
    return { data, next };
}

function append(list, node) {
    if (list.head) {
        list.tail.next = node;
    } else {
        list.head = node;
    }
    list.tail = node;
}

function insert(list, data, position) {
    if (position < 0) throw new Error("position must be nonnegative");

    let newNode = makeNode(data);
    let prev = null, cur = list.head;
    while (cur != null && position > 0) {
        prev = cur;
        cur = cur.next;
        position--;
    }
    if (cur == null && position > 0) throw new Error("position must be <= list length")
    if (cur == null) {
        list.tail = newNode;
    } else {
        newNode.next = cur;
    }
    if (prev == null) {
        list.head = newNode;
    } else {
        prev.next = newNode;
    }
}