在排序的双链接列表中，拒绝重复项的最佳方法是什么

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

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

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

假设ListNode看起来像这个

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

如果head和tailListNode*在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
}