Связанный список: Это решение хорошее?

Question

Я искал способ избежать перехода от главы списка каждый раз, когда хочу найти узел, поэтому я думал о назначении индексов узлам, сохраняя указатель на случайный (не точно случайный, см. Ниже) узел а затем найти указатель, который ближе всего к индексу, который я хочу найти. Позвольте мне объяснить, с кодом:

// head and last are pointers to the first and last items of a doubly-linked list 
// current is a pointer that will change over time. It's used as a temporary pointer 
template <class T>a 
Node<T>* List<T>::get_closest(Node<T> node, int& difference) { 
    int curr_to_i = current->index - node->index; 
    int last_to_i = last->index - node->index; 
    Node* closest = node->index < abs(curr_to_i) ? head : current; 
    closest = closest->index < abs(last_to_i) ? closest : last; 
    difference = closest->index - node->index; 
    return closest; 
} 

/* 
* This functions adds a node with the given value to the given index. The node at that 
* index and all the following are moved, and the new node is inserted before them. 
*/ 
template <class T> 
bool List<T>::add(T value, int index) { 
    if (index < 0) { //Invalid index 
     return false; 
    } else if (index == last->index +1) { 
     push(value); 
     return true; 
    } else if (index > 0) { 
     Node* new_n = new Node; 
     new_n->value = value; 
     new_n->index = index; 
     int difference; 
     Node* closest = get_closest(new_n, difference); 
     if (difference < 0) { 
      for (int i = 0; i < abs(difference); i++) { 
       current = current->previous; 
      } 
     } else if (difference > 0) { 
       for (int i = 0; i < abs(difference); i++) { 
       current = current->next; 
      } 
     } /* current now points to the node we want to move */ 
     new_n->previous = current->previous; 
     new_n->next = current; 
     current->previous->next = new_n; 
     current->previous = new_n; 
     if (index == 0) { 
      root = new_n; 
     } 
     new_n = new_n->next; 
     while (new_n != null) { 
      new_n->index++; 
      new_n = new_n->next; 
     } 
     return true;   
    } 
} 

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

Answer 1

Если вам нужно получить доступ к элементам в середине списка, вам лучше использовать массив. Список представляет собой абстрактную структуру данных (ADT), которая может быть реализована различными способами. По сути дела, вы создаете избыточное представление, которое имеет накладные расходы обоих методов.

Преимущество связанного списка в том, что вставки могут быть очень быстрыми в начале списка - O (1) против O (n) для массива. Однако, поскольку вы должны поддерживать свой индекс, у вас есть O (N) накладные расходы в любом случае для вставок.

Если вам нужна индексация, просто используйте массив. Проще и быстрее.

Answer 2

Похоже, что вставка станет намного дороже. Почему бы не написать тестовую программу и разницу?

Answer 3

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

Answer 4

Звучит так, как будто вы пытаетесь изобрести Skip Lists, что является своего рода сбалансированным, сортированным деревом.

Возможно, что вы действительно хотите использовать что-то вроде boost :: multi_index, что позволит вам использовать комбинацию индексов, чтобы получить хорошую производительность по целому ряду операций. Один из examples очень похож на то, что вы пытаетесь сделать.

Прежде чем пытаться использовать что-то вроде этого, вы должны профилировать фактическое использование, чтобы определить, есть ли какая-либо реальная возможность оптимизировать эту часть вашего кода, а затем, если это окажется узким местом, попробуйте множество разных комбинаций чтобы увидеть, какой из них действительно лучше всего подходит для вашего конкретного использования. Если ваш набор данных довольно велик, std::vector почти всегда будет самым быстрым из-за местоположения.