Вы можете попробовать настраиваемую структуру данных связанного списка, где каждый узел поддерживает следующий / предыдущий, а также отсортированные ссылки следующий / предыдущий.Затем вставка становится двухфазным процессом, сначала всегда вставляйте узел в хвост, и сортировка вставки, и сортировка вставки будет возвращать число чисел меньше x.Удаление - это просто удаление головы.
Вот пример, ПРИМЕЧАНИЕ: ЭТО ОЧЕНЬ НЕВЕРНО ЯВА, ЭТО ПРИМЕРНЫЙ КОД ДЛЯ ЧИСТОГО Демонстрации ИДЕИВы поняли идею!;) Кроме того, я только добавляю несколько элементов, но это должно дать вам представление о том, как это будет работать ... Худший случай для этого - полная итерация по отсортированному связанному списку - что не хуже, чем в примерах.Наверное, выше?
import java.util.*;
class SortedLinkedList {
public static class SortedLL<T>
{
public class SortedNode<T>
{
public SortedNode(T value)
{
_value = value;
}
T _value;
SortedNode<T> prev;
SortedNode<T> next;
SortedNode<T> sortedPrev;
SortedNode<T> sortedNext;
}
public SortedLL(Comparator comp)
{
_comp = comp;
_head = new SortedNode<T>(null);
_tail = new SortedNode<T>(null);
// Setup the pointers
_head.next = _tail;
_tail.prev = _head;
_head.sortedNext = _tail;
_tail.sortedPrev = _head;
_sortedHead = _head;
_sortedTail = _tail;
}
int insert(T value)
{
SortedNode<T> nn = new SortedNode<T>(value);
// always add node at end
nn.prev = _tail.prev;
nn.prev.next = nn;
nn.next = _tail;
_tail.prev = nn;
// now second insert sort through..
int count = 0;
SortedNode<T> ptr = _sortedHead.sortedNext;
while(ptr.sortedNext != null)
{
if (_comp.compare(ptr._value, nn._value) >= 0)
{
break;
}
++count;
ptr = ptr.sortedNext;
}
// update the sorted pointers..
nn.sortedNext = ptr;
nn.sortedPrev = ptr.sortedPrev;
if (nn.sortedPrev != null)
nn.sortedPrev.sortedNext = nn;
ptr.sortedPrev = nn;
return count;
}
void trim()
{
// Remove from the head...
if (_head.next != _tail)
{
// trim.
SortedNode<T> tmp = _head.next;
_head.next = tmp.next;
_head.next.prev = _head;
// Now updated the sorted list
if (tmp.sortedPrev != null)
{
tmp.sortedPrev.sortedNext = tmp.sortedNext;
}
if (tmp.sortedNext != null)
{
tmp.sortedNext.sortedPrev = tmp.sortedPrev;
}
}
}
void printList()
{
SortedNode<T> ptr = _head.next;
while (ptr != _tail)
{
System.out.println("node: v: " + ptr._value);
ptr = ptr.next;
}
}
void printSorted()
{
SortedNode<T> ptr = _sortedHead.sortedNext;
while (ptr != _sortedTail)
{
System.out.println("sorted: v: " + ptr._value);
ptr = ptr.sortedNext;
}
}
Comparator _comp;
SortedNode<T> _head;
SortedNode<T> _tail;
SortedNode<T> _sortedHead;
SortedNode<T> _sortedTail;
}
public static class IntComparator implements Comparator
{
public int compare(Object v1, Object v2){
Integer iv1 = (Integer)v1;
Integer iv2 = (Integer)v2;
return iv1.compareTo(iv2);
}
}
public static void main(String[] args){
SortedLL<Integer> ll = new SortedLL<Integer>(new IntComparator());
System.out.println("inserting: " + ll.insert(1));
System.out.println("inserting: " + ll.insert(3));
System.out.println("inserting: " + ll.insert(2));
System.out.println("inserting: " + ll.insert(5));
System.out.println("inserting: " + ll.insert(4));
ll.printList();
ll.printSorted();
System.out.println("inserting new value");
System.out.println("inserting: " + ll.insert(3));
ll.trim();
ll.printList();
ll.printSorted();
}
}