public class List<E extends Comparable <E>> {
    /**
    * Класс, описывающий объекты-узлы, находящиеся в списке
    * @author Дмитрий Касинцев, группа 1742, ЕНФ
    *
    * @param <E> : Тип информации узла
    */
    private static class Node <E> {
        /**
         * Информация узла
         */
        E info;
        /**
         * Ссылка на следующий узел списка
         */
        Node <E> next;
        /**
         * Конструктор, создающий новый элемент списка, с определенной
         * информацией и ссылкой на следующий узел
         * @param info: Информация узла
         * @param next: Ссылка на следующий узел списка
         */
        public Node(E info, Node<E> next) {
            this.info = info;
            this.next = next;
        }
    }
    /**
     *
     */
    Node <E> head = null;

    // Добавление элементов в список
    public void addAll(E ... arr) {
        for (E e : arr) {
            add(e);
        }
    }

    // Выводит список на экран
    public void print() {
        Node<E> cur = head;
        while (cur != null) {
            System.out.print(cur.info + " > ");
            cur = cur.next;
        }
        System.out.println("null|");
    }

    /**
     * Метод, меняющий два элемента списка местами; в случае
     * если параметры выходят за пределы списка, возникает прерывание
     * @param i : номер элемента списка
     * @param j : номер элемента списка
     */
    public void swap (int i, int j) {
        Node <E> current = head;
        Node <E> pred = null;
        Node<E> a = null;
        Node<E> b = null;
        Node<E> c = null;
        Node<E> d = null;
        int k = 0;
        if ((i < 0) || (j < 0) || (i >= length()) || (j >= length())  )
            throw  new IndexOutOfBoundsException();
        else {
            if (i != j) {
                while (current != null && ((k <= i) || (k <= j))) {
                    if (k == Math.min(i, j)) {
                        a = current;
                        c = pred;
                    }
                    if (k == Math.max(i, j)) {
                        b = current;
                        d = pred;
                    }
                    pred = current;
                    current = current.next;
                    k++;
                }
                b.next = a.next;
                a.next = current;
                if (a == head) head = b;
                else c.next = b;
                if (Math.abs(j - i) == 1)b.next = a;
                else d.next = a;
            }
        }
    }
    /**
     * Cортирует список в порядке возрастания при помощи
     * алгоритма простых вставок
     */
    public void sort() {
        for (int k = 1; k < length(); ++k)
            sort(get(k).info, k);
    }
    /**
     * Вспомогательный приватный метод для метода sort()
     * @param elem : данный элемент, с которым происходит сравнение элементов списка
     * @param index: номер элемента списка, который сравнивается с данным элементом
     */
    private void sort(E elem, int index) {
        int k = index;
        while (k > 0 && get(k - 1).info.compareTo(elem) > 0) {
            swap(k - 1, k);
            --k;
        }

    }
    /**
     * Метод, удаляющий из списка все элементы, меньшие заданного, и возвращающий
     * в качестве результата список этих элементов
     * @param elem : элемент списка, с которым сравниваются все остальные
     * @return: новый список
     */
    public List<E> separate(E elem) {
        Node <E> current = head;
        Node <E> current2 = null;
        Node <E> pred = null;
        Node <E> c = null;
        List <E> sortlist = new List <E>();
        while (current != null ) {
            if (current.info.compareTo(elem) < 0) {
                c = current;
                if (current == head) head = current.next;
                else pred.next = current.next;
                current = current.next;
                c.next = null;
                if (sortlist.head == null) sortlist.head = c;
                else current2.next = c;
                current2 = c;
            } else {
                pred = current;
                current = current.next;
            }
        }
        return sortlist;
    }
    /**
     * вспомогательный метод, возвращающий длину списка
     * @return : длина списка
     */
    public int length() {
        Node <E> current = head;
        int k = 0;
        if (current == null)return 0;
        else
            while (current != null) {
                current = current.next;
                k++;
            }
        return k;
    }
    /**
     * Вспомогательный метод, возвращающий узел списка по его
     * порядкововому номеру
     * @param i: Порядковый номер узла
     * @return : Узел списка
     */
    public Node <E> get(int i) {
        if ((i >= length()) || (i < 0))
            throw new IndexOutOfBoundsException();
        else {
            Node<E> current = head;
            for (int k = 0; k < i; k++) current = current.next;
            return current;
        }
    }
    /**
     * Вспомогательный метод,удаляющий выбранный элемент из списка
     * @param elem: выбранный элемент
     */
    public void remove(E elem) {
        Node<E> current = head;
        Node <E> pred = null;
        while (current != null && elem.compareTo(current.info) != 0) {
            pred = current;
            current = current.next;
        }
        boolean toRemove = current != null && elem.equals(current.info);
        if (toRemove) {
            Node<E> preds = pred;
            Node<E> nexts = current.next;
            if (preds == null) head = nexts;
            else preds.next = nexts;
        }
    }
    /**
     * Вспомогательный метод,добавляющий выбранный элемент в список
     * @param elem: выбранный элемент
     */
    public void add (E elem) {
        Node <E> current = head;
        Node <E> pred = null;
        while (current != null && elem.compareTo(current.info) > 0) {
            pred = current;
            current = current.next;
        }
        Node<E> newNode = new Node<E>(elem, current);
        if (pred == null) head = newNode;
        else pred.next = newNode;
    }



    public static void main(String[] args) {
        List<Integer> list = new List<>();
        list.addAll(1, 4, 4, 3, 2, 1);
        list.print();

        list.swap(2, 1);
        list.print();

        list.sort();
        list.print();

        list.addAll(5, 5, 5, 4, 3, 2, 1);
        list.print();

        System.out.println();
        list.separate(4).print();
        list.print();
    }

}