Содержание
Если вы на самом деле строите настоящую производственную систему, то да, вы, как правило, просто используете материал из стандартной библиотеки, если там есть то, что вам нужно. Тем не менее, не думайте об этом как бессмысленное упражнение. Хорошо понимать, как все работает, и understanding linked lists является важным шагом к пониманию более сложных структур данных, многих из которых нет в стандартных библиотеках.
Существуют некоторые различия между тем, как вы создаете связанный список, и тем, как это делает API коллекций Java. API коллекций пытается придерживаться более сложного интерфейса. Ваш LinkedList всегда будет содержать хотя бы один элемент. При такой настройке вы будете использовать null, когда вам нужен пустой список. Думайте о «следующем» как о «остальной части списка». На самом деле многие люди называют это «хвостом» вместо «следующего».
Вот схема отдельного LinkedList:
Другой должен прочитать:
Какой лучший способ сделать связанный список в Java с нуля?
Ну, вот простейшая реализация класса LinkedList в Java .
CrunchifyLinkedListTest.java
Джава
|
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
204
205
206
207
208
209
210
211
212
213
214
215
216
|
пакет crunchify. ком . учебник ;
/ **
* @author Crunchify.com
* версия: 1.2
* последнее обновление: 11.10.2015
* /
общественности учебный класс CrunchifyLinkedListTest {
общественности статический CrunchifyLinkedList crunchifyList ;
общественности статический недействительным main ( Строка [ ] аргументы ) {
// Конструктор по умолчанию — давайте поместим «0» в элемент head.
crunchifyList знак равно новый CrunchifyLinkedList ( ) ;
// добавляем больше элементов в LinkedList
crunchifyList . добавить ( 1 ) ;
crunchifyList . добавить ( 2 ) ;
crunchifyList . добавить ( «3» ) ;
crunchifyList . добавить ( 4 ) ;
crunchifyList . добавить ( 5 ) ;
/ *
* Обратите внимание, что примитивные значения не могут быть добавлены в LinkedList напрямую. Они должны быть преобразованы в их
* соответствующий класс обертки.
* /
Система. вне. println ( «Печать: crunchifyList: / t / t» + crunchifyList ) ;
Система. вне. println ( .size (): / t / t / t / t + crunchifyList . размер ( ) ) ;
Система. вне. println ( .get (3): / t / t / t / t + crunchifyList . получить ( 3 ) + (получить элемент по индексу: 3 — список начинается с 0) ) ;
Система. вне. println ( .remove (2): / t / t / t / t + crunchifyList . удалить ( 2 ) + (элемент удален) ) ;
Система. вне. println ( .get (3): / t / t / t / t + crunchifyList . получить ( 3 ) + (получить элемент по индексу: 3 — список начинается с 0) ) ;
Система. вне. println ( .size (): / t / t / t / t + crunchifyList . размер ( ) ) ;
Система. вне. println ( «Распечатать снова: crunchifyList: / t» + crunchifyList ) ;
}
}
учебный класс CrunchifyLinkedList {
частный статический ИНТ счетчик ;
частный Голова узла ;
// Конструктор по умолчанию
общественности CrunchifyLinkedList ( ) {
}
// добавляет указанный элемент в конец этого списка.
общественности недействительным добавить ( объект данные ) {
// Инициализируем Node только в случае 1-го элемента
если ( голова == ноль ) {
голова знак равно новый Узел ( данные ) ;
}
Узел crunchifyTemp знак равно новый Узел ( данные ) ;
Узел crunchifyCurrent знак равно голова ;
// Давайте проверим NPE перед итерацией по crunchifyCurrent
если ( crunchifyCurrent ! знак равно ноль ) {
// начинаем с головного узла, сканируем до конца списка и затем добавляем элемент после последнего узла
в то время как ( crunchifyCurrent . getNext ( ) ! знак равно ноль ) {
crunchifyCurrent знак равно crunchifyCurrent . getNext ( ) ;
}
// ссылка «следующий» последнего узла на наш новый узел
crunchifyCurrent . setNext ( crunchifyTemp ) ;
}
// увеличиваем количество элементов переменной
incrementCounter ( ) ;
}
частный статический ИНТ getCounter ( ) {
вернуть счетчик ;
}
частный статический недействительным incrementCounter ( ) {
counter ++ ;
}
частный недействительным decmentCounter ( ) {
счетчик — ;
}
// вставляет указанный элемент в указанную позицию в этом списке
общественности недействительным добавить ( объект данные , ИНТ индекс ) {
Узел crunchifyTemp знак равно новый Узел ( данные ) ;
Узел crunchifyCurrent знак равно голова ;
// Давайте проверим NPE перед итерацией по crunchifyCurrent
если ( crunchifyCurrent ! знак равно ноль ) {
// сканировать до запрошенного индекса или до последнего элемента в списке, в зависимости от того, что произойдет раньше
за ( int я знак равно 0 ; я < индекс && crunchifyCurrent.getNext ()! = null; я ++ ) {
crunchifyCurrent знак равно crunchifyCurrent . getNext ( ) ;
}
}
// устанавливаем ссылку следующего узла нового узла на ссылку следующего узла этого узла
crunchifyTemp . setNext ( crunchifyCurrent . getNext ( ) ) ;
// теперь устанавливаем ссылку следующего узла этого узла на новый узел
crunchifyCurrent . setNext ( crunchifyTemp ) ;
// увеличиваем количество элементов переменной
incrementCounter ( ) ;
}
общественности объект получить ( int индекс )
// возвращает элемент в указанной позиции в этом списке.
{
// индекс должен быть 1 или выше
если ( индекс < 0 )
вернуть ноль ;
Узел crunchifyCurrent знак равно ноль ;
если ( голова ! знак равно ноль ) {
crunchifyCurrent знак равно голова. getNext ( ) ;
за ( int я знак равно 0 ; я < индекс ; я ++ ) {
если ( crunchifyCurrent . getNext ( ) == ноль )
вернуть ноль ;
crunchifyCurrent знак равно crunchifyCurrent . getNext ( ) ;
}
вернуть crunchifyCurrent . getData ( ) ;
}
вернуть crunchifyCurrent ;
}
// удаляет элемент в указанной позиции в этом списке.
общественности логический удалить ( int индекс ) {
// если индекс выходит за пределы диапазона, выход
если ( индекс < 1 | | индекс > размер ( ) )
вернуть ложь ;
Узел crunchifyCurrent знак равно голова ;
если ( голова ! знак равно ноль ) {
за ( int я знак равно 0 ; я < индекс ; я ++ ) {
если ( crunchifyCurrent . getNext ( ) == ноль )
вернуть ложь ;
crunchifyCurrent знак равно crunchifyCurrent . getNext ( ) ;
}
crunchifyCurrent . setNext ( crunchifyCurrent . getNext ( ) . getNext ( ) ) ;
// уменьшаем количество элементов переменной
decmentCounter ( ) ;
вернуть правда ;
}
вернуть ложь ;
}
// возвращает количество элементов в этом списке.
общественности ИНТ размер ( ) {
вернуть getCounter ( ) ;
}
общественности строка toString ( ) {
строка выход знак равно ;
если ( голова ! знак равно ноль ) {
Узел crunchifyCurrent знак равно голова. getNext ( ) ;
в то время как ( crunchifyCurrent ! знак равно ноль ) {
выход + = [ + crunchifyCurrent . getData ( ) . toString ( ) + ] ;
crunchifyCurrent знак равно crunchifyCurrent . getNext ( ) ;
}
}
вернуть вывод ;
}
частный учебный класс Узел {
// ссылка на следующий узел в цепочке, или ноль, если его нет.
Узел следующий ;
// данные, переносимые этим узлом. может быть любого типа, который вам нужен.
объект данные ;
// Узел конструктор
общественности Узел ( Объект dataValue ) {
следующий знак равно ноль ;
данные знак равно dataValue ;
}
// другой конструктор Node, если мы хотим указать узел для указания.
@SuppressWarnings ( «не используется» )
общественности Узел ( Объект dataValue , Узел nextValue ) {
следующий знак равно nextValue ;
данные знак равно dataValue ;
}
// эти методы должны быть понятны
общественности объект getData ( ) {
вернуть данные ;
}
@SuppressWarnings ( «не используется» )
общественности недействительным setData ( Object dataValue ) {
данные знак равно dataValue ;
}
общественности Узел getNext ( ) {
вернуть следующий ;
}
общественности недействительным setNext ( Node nextValue ) {
следующий знак равно nextValue ;
}
}
}
|
Несколько вещей:
Здесь мы инициализируем Node только пока adding 1st element ,
|
1
2
3
4
|
// Инициализируем Node только в случае 1-го элемента
если ( голова == ноль ) {
голова знак равно новый Узел ( данные ) ;
}
|
Результат:
|
1
2
3
4
5
6
7
|
Печать : crunchifyList : [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]
, размер ( ) : 5
, получить ( 3 ) : 4 ( получить элемент по индексу : 3 — список начинается с 0 )
, удалить ( 2 ) : правда ( элемент удален )
, получить ( 3 ) : 5 ( получить элемент по индексу : 3 — список начинается с 0 )
, размер ( ) : 4
Напечатайте еще раз : crunchifyList : [ 1 ] [ 2 ] [ 4 ] [ 5 ]
|
Улучшения этой реализации включают в себя double-linked list , добавив методы к insert а также delete от середины или конца, и добавив get а также sort методы также.
Ссылочный ответ от переполнения стека Лоуренс Гонсалвес . Вы можете быть заинтересованы в списке всех учебных пособий по Java .
0.00 (0%) 0 votes
