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();
}
}