Оптимальная сортировка вставки для двусвязного списка - PullRequest
Новая
       12

Оптимальная сортировка вставки для двусвязного списка

0 голосов
/ 30 марта 2019

Я реализую сортировку вставки в двусвязном списке (DBL).Вставка, а также сортировка нового узла в двусвязном списке происходит в режиме реального времени независимо от предыдущего состояния двусвязного списка (при условии, что двусвязный список уже был отсортирован).

Указатели ниже имеют глобальную область видимости

head = указатель, содержащий начальное значение двусвязного списка

tail = указатель, содержащий последнее значение

midl = указатель, содержащий среднее значение 

void insert()
{
    struct node *newnode = getnode(); //This function creates and returns a node 
                                      //The node has integer id along with previous and 
                                      //next pointers
    if (head == NULL)
    {
        head = newnode;
        tail = newnode;    //if no elements in dbl
    } else
    {
        if (newnode->id > tail->id)
        {
            tail->next = newnode;
            newnode->prev = tail; //new element inserted after tail
            tail = tail->next;
        } else if (newnode->id < head->id)
        {
            newnode->next = head;
            head->prev = newnode;
            head = head->prev;         //new element inserted before head
        } else
        {
            struct node *temp;
            if (newnode->id > midl->id)
                temp = tail;
            else
                temp = midl;  //new element inserted in dbl such that sorting is justified
            while (temp != NULL && newnode->id < temp->id)
                temp = temp->prev;
            newnode->prev = temp;
            newnode->next = temp->next;
            temp->next->prev = newnode;
            temp->next = newnode;
        }
    }
}

Мой вопрос:

Приведенный выше фрагмент кода выполняет свою работу.Есть ли способ еще более оптимизировать код, чтобы уменьшить сравнение для вставки?

...