singly-linked-list - 带有标记节点的单链表的插入和删除之间的差异

Question

我们的任务是为带有哨兵节点的单链表编写 Insert(L,k) 和 Delete(L,k) 函数。我的问题是：

1. 它是正确的还是接近正确的答案？

2. 假设我所做的是正确的，我没有看到与没有哨兵节点的单链表的普通 Delete() 有任何显着差异。我在那个陈述中正确吗？

插入说明(L,k)：

该函数在列表中插入一个带有 key == k 的新节点（如果它不存在）。

删除(L,k)说明：

该函数查找其键 == k 的节点，如果找到，则将其删除。

我们可以假设每个节点的键都是唯一的。

我的插入实现：

fun Insert(pointer L,Key k) {
    pointer p;
    pointer currNode = L; // first element

    while(currNode != NULL && currNode->data != k) {
        currNode = currNode->next;
    }

    if(currNode == NULL) { // element doesn't exist
        p = newcell(Node); // allocate memory for a new node
        p->data = k;
        p->next  = L;
        L = p;
        return;
    }
    else { // element exists
        throw error;
    }
}

我的删除实现：

    fun Delete(pointer L, Key k) {
        pointer currNode = L; //first element
        pointer prev = NULL; // A pointer to the previous node

    if(currNode != NULL && currNode->data == k) { // first elemenent has k
        L = currNode->next;
        free(currNode);
    }

    // look for the elemenent to delete
    while(currNode->next != NULL && currNode->data != k) {
        prev = currNode;
        currNode = currNode->next;
    }

    if(currNode->next == NULL) throw error; // element not found

    // elemenent found
    prev->next = currNode->next;
    free(currNode);
}

PS 以下是我们的示例中带有哨兵节点的单链表的样子

标签： singly-linked-listpseudocode