C++ Добавить в связанный список в отсортированном порядке

Question

Привет у меня есть связанный список, используя структуры. Прямо сейчас я получил это, чтобы добавить каждый элемент в конце. Однако я хотел бы добавить каждый элемент в отсортированном порядке на основе идентификатора. Структура имеет два элемента: строковое имя и длинный идентификатор.

node* temp = new node;
temp->name = nameRead;
temp->id = idRead;

//check if first item, if so add as head
if(head == NULL)
{
    head = temp;
}
else
{
   node* temp2 = head;
   while(temp2->next != NULL)
   {
      temp2 = temp2->next;
   }
   temp2->next = temp;
}

Answer 1

node* temp = new node;
temp->name = nameRead;
temp->id = idRead;

node* temp2 = head;
node** temp3 = &head;
while(temp2 != null && temp2->id < temp->id)
{
   temp3 = &temp2->next;
   temp2 = temp2->next;
}
*temp3 = temp;
temp->next = temp2;

РЕДАКТИРОВАТЬ: Объяснение: указатель 'temp3' указывает на то, куда нужно идти 'temp'. Инициализируйте temp2 для заголовка и продолжайте цикл до тех пор, пока мы не достигнем конца списка или пока идентификатор temp2 не станет равным>= чем идентификатор temp. На каждой итерации цикла продвигайте как temp3, так и temp2.

В конце цикла "temp3" будет содержать адрес указателя, где должен находиться "temp". Поэтому назначьте *temp3 для указания на temp и присвойте temp-> рядом с точкой для temp2 (которая в этот момент будет либо нулевой, либо будет указывать на элемент, имеющий больший идентификатор, чем temp->id).

Answer 2

Взято из моей студенческой тетради:

void addSorted(node * head, int id){
        node* newNode = new node;
        newNode->number = n;
        newNode->next = NULL;

        if(head == NULL || head->number >= id   ){
            newNode->next = head;
            head = newNode;
            return;
        }else if(head->next != NULL && head->next->id >= id){
            node * nextNode = head->next;
            newNode->next = nextNode;
            head->next = newNode;
            return;
        }else{
            node * left;
            node * right = head;
            while(right != NULL && right->next->id <= id){
                left = right;
                right = right->next;
            }
            left->next=newNode;
            newNode->next = right;
        }
    }

Answer 3

Большинство изменений в коде довольно тривиальны - просто добавьте сравнение, основанное на идентификаторе, чтобы вы только проходили по списку, пока не дойдете до узла с идентификатором, который больше, чем новый, который нужно вставить (или достигните конца списка).

Вот где все становится немного сложнее: прежде чем вы "поймете", что достигли нужного места в списке, вы уже зашли на один узел слишком далеко (и в односвязном списке нет пути назад). Уловка, чтобы исправить это довольно просто: выделите новый (пустой) узел и вставьте его после найденного слишком большого узла. Скопируйте содержимое этого слишком большого узла в новый, который вы только что вставили, а затем скопируйте данные для нового узла в место, которое он только что освободил.

Я должен добавить, однако, что все это в основном спорный вопрос. Если вы хотите отсортированную коллекцию элементов, связанный список обычно является действительно паршивым выбором. Если вы не делаете что-то вроде домашней работы, где у вас нет выбора, кроме как делать то, что вам назначили до смерти, посмотрите вверх std::set [Редактор std::multiset, если дубликаты разрешены - или, возможно, std::map или же std::multimap, если вы хотите найти узел на основе идентификатора] и забыть о его реализации самостоятельно.