StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POLinked List: Is this solution good?
text
Body
copied!<p>I was looking for a way to avoid starting from the head of the list each time I want to find a node, so I thought of assigning indexes to nodes, keeping a pointer to a random (not exactly random; see below) node and then finding the pointer that's closest to the index I want to find. Allow me to explain with code:</p> <pre><code>// 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; } } </code></pre> <p>Is this more efficient than starting from the head and advancing forward a number of times?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload