package com.company;
public class LinkedList {
private Node head;
public int Count() {
int count = 0;
Node curr = head;
while (curr != null) {
curr = curr.next;
count++;
}
return count;
}
public boolean isValidData(Integer data) {
if (data == null) {
return false;
}
try {
return (data) > 0;
} catch (NumberFormatException e) {
return false;
}
}
public boolean addFirst(Integer data) { //добавить спереди
if (!isValidData(data)) {
return false;
}
Node node = new Node(Integer.valueOf(data)); //создаём новый элемент
// указатель на следующий элемент автоматически инициализируется как null
if (head == null) { //если список пуст то указываем ссылки начала и конца на новый элемент
head = node; //т.е. список теперь состоит из одного элемента
} else {
node.next = head; //иначе новый элемент теперь ссылается на "бывший" первый
head = node; //а указатель на первый элемент теперь ссылается на новый элемент
}
return true;
}
public boolean addLast(Integer data) {
if (!isValidData(data)) {
return false;
}
if (head == null) {
addFirst(data);
return true;
}
Node curr = head;
while (curr.next != null) {
curr = curr.next;
}
curr.next = new Node(Integer.valueOf(data));
return true;
}
public void printList()
{
while (head != null)
{
System.out.print( head.getData() + " ");
head = head.next;
}
}
public boolean isEmpty() {
return head == null;
}
String getString() //печать списка
{
if (isEmpty()) {
return null;
}
StringBuilder sb = new StringBuilder();
Node t = head; //получаем ссылку на первый элемент
while (t != null) //пока элемент существуе
{
sb.append(t.data).append(' ');
t = t.next; //и переключаемся на следующий
}
return sb.toString().trim();
}
public boolean removeFirst() {
if (isEmpty()) {
return false;
}
head = head.next;
return true;
}
public boolean remove(int index) {
if (index < 0 || index >= Count()) {
return false;
} else if (index == 0) {
head = head.next;
} else if (index == Count() - 1) {
Node current = head;
for (int i = 0; i < index - 1; i++)
current = current.next;
current.next = null;
} else {
Node current = head;
for (int i = 0; i < index - 1; i++)
current = current.next;
current.next = current.next.next;
}
return true;
}
public boolean Insert(int index, Integer item) {
if (!isValidData(item)) {
return false;
}
if (isEmpty()) {
return addFirst(item);
}
if (index < 0 || index > Count() ) {
return false;
}
if (index == Count() )
return addLast(item);
Node current = head;
for (int i = 0; i < index - 1; i++)
current = current.next;
Node temp = new Node(Integer.valueOf(item));
temp.next = current.next;
current.next = temp;
return true;
}
private Node nodeAt(int index) {
if (index < 0 || index > Count())
throw new IllegalArgumentException();
Node curr = head;
int i = 0;
while (i++ != index) {
curr = curr.next;
}
return curr;
}
private int getIndexOfMin(int startIndex) {
Node minNode = nodeAt(startIndex);
int minIndex = startIndex;
Node curr = nodeAt(startIndex);
int index = startIndex;
while (curr != null)
if(passesSortCondition(curr, minNode)){
{
minIndex = index;
minNode = curr;
}
index++;
curr = curr.next;
}
return minIndex;
}
public void selectionSort() {
// unsortedIndex - индекс начала неотсортированой части
for (int unsortedIndex = 0; unsortedIndex < Count(); unsortedIndex++) {
int minIndex = getIndexOfMin(unsortedIndex);
Node minNode = nodeAt(minIndex);
remove(minIndex);
Insert(minNode.getData(), unsortedIndex);
}
}
private boolean passesSortCondition(Node a, Node b) {
return a.data < b.data;
}
public Integer getAt(Integer index) {
Node curr = head;
int i =0 ;
while (curr != null) {
if (i == index)
{
i++;
return curr.getData();
}
curr = curr.next;
}
return null;
}
}