Repository navigation
Expand file tree
/
Copy pathOneLinkedList.java
More file actions
164 lines (136 loc) · 4.45 KB
/
Copy pathOneLinkedList.java
File metadata and controls
164 lines (136 loc) · 4.45 KB
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
// Односвязный список, который может работать с различной типизации
package java_algorithms;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class OneLinkedList<T> implements Iterable<T> {
// первый узел, в него вставляются все другие
private Node<T> firstNode;
// текущее кол-во элементов в списке
private int countElements;
public void add(T val) {
if (firstNode == null) {
firstNode = new Node<T>(val, null);
}
Node<T> curNode = firstNode;
while (curNode.getNext() != null) {
curNode = curNode.getNext();
}
Node<T> newNode = new Node<>(val, null);
curNode.setNext(newNode);
countElements++;
}
public T get(int index) {
if (index > countElements - 1) {
throw new IndexOutOfBoundsException("No such index " + index);
}
int k = 0;
Node<T> curNode = firstNode;
while (curNode.getNext() != null) {
if (k == index) {
break;
}
curNode = curNode.getNext();
k++;
}
return curNode.getValue();
}
public int getCount() {
return countElements;
}
public void remove(int index) {
if (index > countElements - 1) {
throw new IndexOutOfBoundsException("No such index " + index);
}
if (index == 0) {
firstNode = firstNode.getNext();
return;
}
int k = 0;
Node<T> curNode = firstNode;
Node<T> prevNode = null;
while (curNode.getNext() != null) {
if (k == index) {
break;
}
prevNode = curNode;
curNode = curNode.getNext();
k++;
}
prevNode.setNext(curNode.getNext());
countElements--;
}
/**
* Список перестраивается в обратном порядке
*/
public void reverse() {
// в tmpNode собираем новый список с обратным порядком
Node<T> tmpNode = null;
Node<T> curNode = firstNode;
while (curNode.getNext() != null) {
// добавление элемента в начало
tmpNode = new Node<T>(curNode.getValue(), tmpNode);
// переход к следующему элементу
curNode = curNode.getNext();
}
// добавление последнего элемента в начало
tmpNode = new Node<T>(curNode.getValue(), tmpNode);
// заменяем текущий новым списком
firstNode = tmpNode;
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
Node<T> curNode = firstNode;
while (curNode.getNext() != null) {
str.append(curNode.getValue()).append(", ");
curNode = curNode.getNext();
}
str.append(curNode.getValue());
return "[" + str.toString() + "]";
}
@Override
public Iterator<T> iterator() {
return new Iterator<>() {
private Node<T> nextNode;
private int curIndex = -1;
@Override
public boolean hasNext() {
return curIndex + 1 < countElems;
}
@Override
public T next() {
curIndex++;
if (curIndex >= 0 && curIndex < countElems) {
if (nextNode == null) {
nextNode = firstNode;
} else {
nextNode = nextNode.getNext();
}
return nextNode.getValue();
} else {
throw new NoSuchElementException();
}
}
};
}
public static class Node<T> {
private T value;
private Node<T> next;
public Node(T value, Node<T> next) {
this.value = value;
this.next = next;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}
}