拒绝排序双向链表中重复项的最佳方法是什么

Question

我正在尝试制作一个不插入重复项的排序双向链表，但我无法找到执行此操作的方法。我查看了有关如何删除重复项的帖子，但没有有关防止重复插入的帖子。

这是我必须在不拒绝重复项的情况下插入和排序的代码。参数 dataIn 从 main 中预定义的 Student 对象列表中获取值 (Student s = {{gpa, name}, ..., {gpa, name}}:

void StudentList::insertNode(Student dataIn)
{
    ListNode *newNode; // A new node pointer
    ListNode *pCur; // To traverse the list
    // Allocate a new node and store num there.
    newNode = new ListNode;
    newNode->stu = dataIn;
    newNode->forw = NULL;
    newNode->back = NULL;
    
    //Check if there is node in list
    if(head ->forw == NULL && head->back == NULL){
        head->forw = newNode;
        newNode->back = head;
        newNode->forw = head;
        head->back = newNode;
    }
    else{
        // Initialize pointers
        pCur = head->forw;
        // Find location: skip all nodes whose name is less than dataIn's name
        while (pCur != head && pCur->stu.name < dataIn.name)
        {
            pCur = pCur->forw;
        }
        // Insert the new node between pPre and pCur
        ListNode *pPre = pCur->back; // The previous node
        newNode->back = pPre;
        newNode->forw = pCur;
        pCur->back = newNode;
        pPre->forw = newNode;
    }
    // Update the counter
    count++;
}

有谁知道拒绝重复而不删除的方法吗？谢谢大家！

Answer 1

What is the best way to reject duplicates in a sorted doubly linked list?

我建议推迟创建新 ListNode 直到您知道新节点不是重复节点。

假设 ListNode 看起来像这样

struct ListNode {        
    Student stu;
    ListNode *back;
    ListNode *forw;
};

并且您有一个 head 和 tail ListNode* 当 StudentList 为空时设置为 nullptr，然后 insertNode 函数可能如下所示：

bool StudentList::insertNode(const Student& dataIn) { // return true if node is inserted
    ListNode* prev = nullptr;
    ListNode* pCur = head;

    // search for a good insertion spot
    for(; pCur; prev = pCur, pCur = pCur->forw) {
        if(dataIn.name == pCur->stu.name) return false; // equal, reject
        if(dataIn.name < pCur->stu.name) break;         // found a good spot before pCur
    }

    // delayed creation until here:
    ListNode* newNode = new ListNode{dataIn, prev, pCur};

    // linking        
    if(prev) prev->forw = newNode;
    else head = newNode;
    
    if(pCur) pCur->back = newNode;
    else tail = newNode; // comment this line out if you don't have a "tail"

    ++count;

    return true; // node inserted
}

拒绝排序双向链表中重复项的最佳方法是什么

What is the best way to reject duplicates in a sorted doubly linked list

c++

vector

iterator

duplicates

doubly-linked-list