package com company public class LinkedList private Node head public i

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
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;
}
}