Содержание
В этом уроке я покажу простую реализацию односвязного списка в Java .
Связанный список — это последовательность узлов в памяти, такая что:
- Есть начальный узел.
- Каждый узел содержит указатель, который указывает на следующий или дочерний узел.
- Если узел не имеет дочернего узла, то его указатель устанавливается в NULL.
- Каждый узел содержит данные, может быть, их много.
- Связанный список также имеет функции, которые управляют списком путем выполнения добавлений, удалений, изменения данных узла, возврата количества узлов и т. Д. И т. Д.
Если у вас есть какие-либо из нижеперечисленных вопросов, то вы на правильном посте в блоге
- Как удалить данный узел в связанном списке
- Удалить узел в середине односвязного списка
- СПИСОК ССЫЛКИ :: УДАЛЕНИЕ (УДАЛЕНИЕ)
- Удаление узлов из односвязного списка
Связанный список используется для тех же целей, что и массив. Однако у связанного списка есть некоторые преимущества: массив имеет фиксированный размер (если он не выделяется динамически), связанный список может увеличиваться за счет выделения новой памяти из кучи по мере необходимости. Если вы сохраняете список в массиве, а затем удаляете элемент посередине, то вы должны переместить множество элементов на один, чтобы сократить разрыв. Но в связанном списке вы просто перенаправляете указатели вокруг узла для удаления, а затем удаляете его.
Вот простая реализация списка однократных ссылок:
CrunchifyNode.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
|
пакет ком . crunchify. учебные пособия ;
/ **
* @author Crunchify.com
*
* /
общественности учебный класс CrunchifyNode
// переменные экземпляра
частный В элемент ;
частный CrunchifyNode
// сначала конструктор
общественности CrunchifyNode ( ) {
это ( ноль , ноль ) ;
}
общественности CrunchifyNode ( V элемент , CrunchifyNode
это. элемент знак равно элемент ;
это. следующий знак равно следующий ;
}
общественности В getElement ( ) {
вернуть элемент ;
}
общественности CrunchifyNode
вернуть следующий ;
}
общественности недействительным setElement ( V элемент ) {
это. элемент знак равно элемент ;
}
общественности недействительным setNext ( CrunchifyNode
это. следующий знак равно следующий ;
}
}
|
CrunchifySinglyLinkedList.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
|
пакет ком . crunchify. учебные пособия ;
/ **
* @author Crunchify.com
*
* /
общественности учебный класс CrunchifySinglyLinkedList
// Переменные экземпляра. Добавьте ссылку на хвост.
защищенный CrunchifyNode
защищенный долго размер ;
// Сначала пустой конструктор списка
общественности CrunchifySinglyLinkedList ( ) {
голова знак равно ноль ;
хвост знак равно ноль ;
размер знак равно 0 ;
}
// Способ добавления CrunchifyNodes в список. Место хранения для CrunchifyNode уже выделено в вызывающем методе
общественности недействительным addFirst ( CrunchifyNode
// Установить хвост, только если это самый первый CrunchifyNode
если ( хвост == ноль )
хвост знак равно CrunchifyNode ;
CrunchifyNode . setNext ( head ) ; // Сделать следующий из нового CrunchifyNode ссылкой на заголовок
голова знак равно CrunchifyNode ; // Придаем голове новое значение
// изменить размер
размер ++ ;
}
// Добавляем новый CrunchifyNode после текущего CrunchifyNode, проверяя, находимся ли мы в хвосте
общественности недействительным addAfter ( CrunchifyNode
если ( currentCrunchifyNode == хвост )
хвост знак равно newCrunchifyNode ;
newCrunchifyNode . setNext ( currentCrunchifyNode . getNext ( ) ) ;
currentCrunchifyNode . setNext ( newCrunchifyNode ) ;
// изменить размер
размер ++ ;
}
// Добавить новый CrunchifyNode после хвостового CrunchifyNode.
общественности недействительным addLast ( CrunchifyNode
CrunchifyNode . setNext ( null ) ;
хвост . setNext ( CrunchifyNode ) ;
хвост знак равно CrunchifyNode ;
размер ++ ;
}
// Методы удаления CrunchifyNodes из списка. (К сожалению, с одним связанным списком. Нет возможности удалить последний. Нужна предыдущая ссылка, чтобы сделать это.
общественности CrunchifyNode
если ( голова == ноль )
Система. эээ. println ( «Ошибка: попытка удалить из пустого списка» ) ;
// сохранить тот, который нужно вернуть
CrunchifyNode
// делаем манипулирование ссылками
голова знак равно голова. getNext ( ) ;
темп . setNext ( null ) ;
размер — ;
вернуть темп ;
}
// Удалить CrunchifyNode в конце списка. tail ссылается на этот CrunchifyNode, но так как список является одиночной связью, нет способа сослаться на CrunchifyNode перед хвостовым CrunchifyNode. Нужно пройтись по списку.
общественности CrunchifyNode
// Объявляем локальные переменные / объекты
CrunchifyNode
CrunchifyNode
// Убедитесь, что у нас есть что удалить
если ( размер == 0 )
Система. эээ. println ( «Ошибка: попытка удалить пустой список» ) ;
// Переходим по списку, получая ссылку на CrunchifyNode перед трейлером. Так как нет предыдущей ссылки.
CrunchifyNodeBefore знак равно getFirst ( ) ;
за ( int подсчитывать знак равно 0 ; подсчитывать < размер — 2 ; считать ++ )
CrunchifyNodeBefore знак равно CrunchifyNodeBefore . getNext ( ) ;
// Сохраняем последний CrunchifyNode
CrunchifyNodeToRemove знак равно хвост ;
// Давайте сделаем манипулирование указателем
CrunchifyNodeBefore . setNext ( null ) ;
хвост знак равно CrunchifyNodeBefore ;
размер — ;
вернуть CrunchifyNodeToRemove ;
}
// Удалить известный CrunchifyNode из списка. Нет необходимости искать или возвращать значение. Этот метод использует ссылку «до», чтобы разрешить манипулирование списком.
общественности недействительным удалить ( CrunchifyNode
// Объявляем локальные переменные / ссылки
CrunchifyNode
// Убедитесь, что у нас есть что удалить
если ( размер == 0 )
Система. эээ. println ( «Ошибка: попытка удалить пустой список» ) ;
// начинаем с начала проверки на удаление
currentCrunchifyNode знак равно getFirst ( ) ;
если ( currentCrunchifyNode == CrunchifyNodeToRemove )
removeFirst ( ) ;
currentCrunchifyNode знак равно getLast ( ) ;
если ( currentCrunchifyNode == CrunchifyNodeToRemove )
removeLast ( ) ;
// Мы уже проверили два CrunchifyNodes, проверьте остальные
если ( размер — 2 > 0 ) {
CrunchifyNodeBefore знак равно getFirst ( ) ;
currentCrunchifyNode знак равно getFirst ( ) . getNext ( ) ;
за ( int подсчитывать знак равно 0 ; подсчитывать < размер — 2 ; считать ++ ) {
если ( currentCrunchifyNode == CrunchifyNodeToRemove ) {
// удаляем текущий CrunchifyNode
CrunchifyNodeBefore . setNext ( currentCrunchifyNode . getNext ( ) ) ;
размер — ;
перерыв ;
}
// Изменить ссылки
CrunchifyNodeBefore знак равно currentCrunchifyNode ;
currentCrunchifyNode знак равно currentCrunchifyNode . getNext ( ) ;
}
}
}
// Возвращает голову и / или хвост CrunchifyNodes и размер списка
общественности CrunchifyNode
вернуть голова ;
}
общественности CrunchifyNode
вернуть хвост ;
}
общественности долго getSize ( ) {
вернуть размер ;
}
}
|
Не стесняйтесь предоставить свой комментарий, если вы обнаружите какую-либо ошибку или другое условие, которое не обрабатывается правильно :). Ваш отзыв очень важен.
0.00 (0%) 0 votes
