реализация двусвязного списка

Question

Какой из них будет более эффективным?

Я хочу сохранить список предметов, но от меня требуется отсортировать список

• по id,
• по имени
• по кредитам курса
• пользователем

Было бы лучше добавить элементы в список по идентификатору, а затем отсортировать по другим или просто добавитьэлементы без заказа и сортировка в порядке, необходимом для пользователя?

Answer 1

Вы можете использовать три карты (или хеш-карты): одну, отображающую идентификатор для элемента, одно имя для ссылки на элемент (или указатель), и одну карту для сопоставления кредитов с ссылкой на элемент снова.

Answer 2

Если вам действительно необходимо сохранить список отсортированным - в отличие от использования других структур данных для предоставления отсортированного доступа к списку - тогда вы можете просто создать список, элементы которого имеют разные указатели для разных критериев сортировки.

Другими словами, вместо того, чтобы хранить только указатели previous и next, используйте previousById, nextById, previousByName, previousByCredits и nextByCredits. Точно так же у вас будет три указателя головы и / или хвоста, а не один.

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

Answer 3

Более эффективным было бы хранить узлы как есть и поддерживать 4 различных индекса в актуальном состоянии. Таким образом, когда требуется один заказ, вы просто выбираете правильный индекс и все. Стоимость составляет O (log N) для ввода и O (1) для обхода.

Конечно, хранить 4 индекса одновременно, возможно, с разными требованиями к уникальности и с учетом возможных исключений, относительно сложно, но для этого есть библиотека Boost: Boost MultiIndex

В качестве примера можно создать набор, который может быть отсортирован по идентификатору или по имени .

Поскольку вы можете добавить столько индексов, сколько пожелаете, это должно помочь вам:)

Answer 4

Было бы более эффективно отсортировать его в любом порядке, который, как вы знаете, будет отсортирован наиболее часто, например, если вы знаете, что вы будете получать по id чаще всего, сохраняйте сортировку по idв противном случае выберите один из других вариантов, хотя id будет проще всего, если это просто целочисленное поле

. Тогда для этого нужно будет выполнить вставку, чтобы найти, где newid меньше nextidно больше, чем previousid, затем выделите новый узел с new и установите указатели соответствующим образом.

Лучше хранить отсортированный связанный список каким-либо образом, чем просто сохранять его несортированным.Вы добавляете некоторое время к тому, сколько времени потребуется, чтобы вставить элемент, но ничтожно мало к тому, сколько времени потребуется, чтобы отсортировать его особым образом

Answer 5

Храните свои объекты в виде списка в случайном порядке.Чтобы отсортировать список по любому ключу, используйте этот псевдокод:

struct LinkedList {
    string name;
    LinkedList *prev;
    LinkedList *next;
};

void FillArray(LinkedList *first, LinkedList **output, size_t &size) {
    //function creates an array of pointers to every LinkedList object
    LinedList *now;
    size_t i; //you may use int instead of size_t

    //check, how many objects are there in linked list
    now=first;
    while(now!=NULL) {
        size++;
        now=now->next;
    }

    //if linked list is empty
    if (size==0) {
        *output=NULL;
        return;
    }

    //create the array;
    *output = new LinkedList[size];

    //fill the array
    i=0;
    now=first;
    while(now!=NULL) {
        *output[i++]=now;
        now=now->next;
    }
}

SortByName(LinkedList *arrayOfPointers, size_t size) {
    // your function to sort by name here
}

void TemporatorySort(LinkedList *first, LinkedList **output, size_t &size) {
    // this function will create the array of pointer to your linked list,
    // sort this array, and return the sorted array. However, the linked
    // list will stay as it is. It's good for example when your lined list
    // is sorted by ID, but you need to print it sorted by names only once.
    FillArray(first, *output, size);
    SortByName(output,size);
}

void PermanentSort(LinkedList *first) {
    // This function will sort the linked list and save the new order
    // permanently.
    LinkedList *sorted;
    size_t size;
    TemporatorySort(first,&sorted,size);
    if (size>0) {
        sorted[0].prev=NULL;
    }
    for(int i=1;i<size;i++) {
        sorted[i-1].next=sorted[i];
        sorted[i].prev=sorted[i-1];
    }
    sorted[size-1].next=NULL;
}

Надеюсь, я действительно вам помог.Если вы не понимаете ни одной строки из кода, просто оставьте комментарий к этому «ответу».