[FEATURE REQUEST] MidLinkedList: Optimized Doubly Linked List with mid pointer

[omatheus-edev]

What would you like to Propose?

I propose adding a new optimized data structure: MidLinkedList.

MidLinkedList is an enhanced Doubly Linked List that maintains three strategic pointers (head, mid, tail) and optimizes search and traversal operations by always choosing the shortest path from these anchors.

The mid pointer automatically rebalances during insertions and deletions. This structure drastically reduces the constant factor in linear operations, and enables efficient O(1) access for head/tail, and O(n/4) on average for arbitrary searches, insertions, and deletions.

Issue details

Name: MidLinkedList
Problem statement: Standard Doubly Linked Lists are limited to bidirectional traversal from head and tail, which makes search and update operations less efficient. This proposal introduces a third access point (the mid pointer, always at size/2) to the list, enabling faster access, and optimized operations for large lists.

Key differences:

• Keeps mid pointer up-to-date on every insertion/deletion
• Calculates shortest path (head/mid/tail) for all traversal
• Reduces search cost to O(n/4) on average.

Implementation is generic and provides full support for insertion, deletion, access, and search.

Additional Information

Full implementation available:

public final class MidLinkedList<T> {
    private Node<T> head;
    private Node<T> tail;
    private Node<T> mid;
    private int size = 0;
    private int midIndex = 0;
    // Constructor, add, remove, access, contains, etc.
    
    public final static class Node<T> {
        T value;
        private Node<T> previous;
        private Node<T> next;
        public Node(T value) { 
            this.value = value; 
            this.previous = null; 
            this.next = null; 
        }
    }
}

Performance characteristics:

• insert/remove at head/tail: O(1)
• search/insert at arbitrary index: O(n/4) average
• mid pointer auto-balancing during all operations

Benefits: Suitable for large datasets where optimized traversal is desired. Provides a practical alternative to standard Doubly Linked List with minimal space overhead.

Author: Matheus Sousa (https://github.com/omatheus-edev)
Category: datastructures/list

Test case suggestion: Insert, remove, search, and access by index and value, comparing traversal steps vs standard list.