CODEWITHSUNDEEP
linked-listlanguage-agnostic
Axoren
Axoren

Reputation: 643

Is there a more efficient way to find the middle of a singly-linked list? (Any language)

Let's set the context/limitations:

  1. A linked-list consists of Node objects.
  2. Nodes only have a reference to their next node.
  3. A reference to the list is only a reference to the head Node object.
  4. No preprocessing or indexing has been done on the linked-list other than construction (there are no other references to internal nodes or statistics collected, i.e. length).
  5. The last node in the list has a null reference for its next node.

Below is some code for my proposed solution.

Node cursor = head;
Node middle = head;

while (cursor != null) {
    cursor = cursor.next;
    if (cursor != null) {
        cursor = cursor.next;
        middle = middle.next;
    }
}
return middle;

Without changing the linked-list architecture (not switching to a doubly-linked list or storing a length variable), is there a more efficient way to find the middle element of singly-linked list?

Note: When this method finds the middle of an even number of nodes, it always finds the left middle. This is ideal as it gives you access to both, but if a more efficient method will always find the right middle, that's fine, too.

Upvotes: 0

Views: 104

Answers (1)

paxdiablo
paxdiablo

Reputation: 881523

No, there is no more efficient way, given the information you have available to you.

Think about it in terms of transitions from one node to the next. You have to perform N transitions to work out the list length. Then you have to perform N/2 transitions to find the middle.

Whether you do this as a full scan followed by a half scan based on the discovered length, or whether you run the cursor (at twice speed) and middle (at normal speed) pointers in parallel is not relevant here, the total number of transitions remains the same.

The only way to make this faster would be to introduce extra information to the data structure which you've discounted but, for the sake of completeness, I'll include it here. Examples would be:

  • making it a doubly-linked list with head and tail pointers, so you could find it in N transitions by "squeezing" in from both ends to the middle. That doubles the storage requirements for pointers however so may not be suitable.

  • having a skip list with each node pointing to both it's "child" and its "grandchild". This would speed up the cursor transitions resulting in only about N in total (that's N/2 for each of cursor and middle). Like the previous point, there's an extra pointer per node required for this.

  • maintaining the length of the list separately so you could find the middle in N/2 transitions.

  • same as the previous point but caching the middle node for added speed under certain circumstances.

That last point bears some extra examination. Like many optimisations, you can trade space for time and the caching shows one way to do it.

First, maintain the length of the list and a pointer to the middle node. The length is initially zero and the middle pointer is initially set to null.

If you're ever asked for the middle node when the length is zero, just return null. That makes sense because the list is empty.

Otherwise, if you're asked for the middle node and the pointer is null, it must be because you haven't cached the value yet.

In that case, calculate it using the length (N/2 transitions) and then store that pointer for later, before returning it.

As an aside, there's a special case here when adding to the end of the list, something that's common enough to warrant special code.

When adding to the end when the length is going from an even number to an odd number, just set middle to middle->next rather than setting it back to null.

This will save a recalculation and works because you (a) have the next pointers and (b) you can work out how the middle "index" (one-based and selecting the left of a pair as per your original question) changes given the length:

Length   Middle(one-based)
------   -----------------
     0      none
     1         1
     2         1
     3         2
     4         2
     5         3
     :         :

This caching means, provided the list doesn't change (or only changes at the end), the next time you need the middle element, it will be near instantaneous.

If you ever delete a node from the list (or insert somewhere other than the end), set the middle pointer back to null. It will then be recalculated (and re-cached) the next time it's needed.

So, for a minimal extra storage requirement, you can gain quite a bit of speed, especially in situations where the middle element is needed more often than the list is changed.

Upvotes: 1

Related Questions