Cum să implementați o clasă LinkedList de la zero în Java

Publicat: 2013-06-19
Tutorial de implementare Crunchify Java LinkedList

Dacă de fapt construiți un sistem de producție real, atunci da, de obicei ați folosi doar materialele din biblioteca standard dacă ceea ce aveți nevoie este disponibil acolo. Acestea fiind spuse, nu vă gândiți la asta ca la un exercițiu inutil.

Este bine să înțelegeți cum funcționează lucrurile, iar understanding linked lists este un pas important către înțelegerea structurilor de date mai complexe, dintre care multe nu există în bibliotecile standard.

Există unele diferențe între modul în care creați o listă conectată și modul în care API-ul Java Collections o face.

API-ul Collections încearcă să adere la o interfață mai complicată. LinkedList va avea întotdeauna cel puțin un element.

Cu acest tip de configurare, ați folosi null atunci când aveți nevoie de o listă goală. Gândiți-vă la „următorul” ca fiind „restul listei”. De fapt, mulți oameni l-ar numi tail în loc de „următorul”.

Iată o diagramă a unei singure LinkedList:

Crunchify Exemplu de listă legată individual

Altul trebuie să citească:

  • Cum se repetă prin instanța LinkedList în Java?
  • Java: Cum să găsiți elementul de mijloc al LinkedList?

Care este cel mai bun mod de a face o listă linked în Java de la zero?

Ei bine, iată o implementare cea mai simplă a clasei LinkedList în Java.

LinkedList în Java de la zero - Tutorial Crunchify
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
package crunchify . com . tutorial ;
 
/**
* @author Crunchify.com
* version: 1.2
* last updated: 11/10/2015
*/
 
public class CrunchifyLinkedListTest {
public static CrunchifyLinkedList crunchifyList ;
 
public static void main ( String [ ] args ) {
 
// Default constructor - let's put "0" into head element.
crunchifyList = new CrunchifyLinkedList ( ) ;
 
// add more elements to LinkedList
crunchifyList . add ( "1" ) ;
crunchifyList . add ( "2" ) ;
crunchifyList . add ( "3" ) ;
crunchifyList . add ( "4" ) ;
crunchifyList . add ( "5" ) ;
 
/*
* Please note that primitive values can not be added into LinkedList directly. They must be converted to their
* corresponding wrapper class.
*/
 
System . out . println ( "Print: crunchifyList: \t\t" + crunchifyList ) ;
System . out . println ( ".size(): \t\t\t\t" + crunchifyList . size ( ) ) ;
System . out . println ( ".get(3): \t\t\t\t" + crunchifyList . get ( 3 ) + " (get element at index:3 - list starts from 0)" ) ;
System . out . println ( ".remove(2): \t\t\t\t" + crunchifyList . remove ( 2 ) + " (element removed)" ) ;
System . out . println ( ".get(3): \t\t\t\t" + crunchifyList . get ( 3 ) + " (get element at index:3 - list starts from 0)" ) ;
System . out . println ( ".size(): \t\t\t\t" + crunchifyList . size ( ) ) ;
System . out . println ( "Print again: crunchifyList: \t" + crunchifyList ) ;
}
 
}
 
class CrunchifyLinkedList {
 
private static int counter ;
private Node head ;
 
// Default constructor
public CrunchifyLinkedList ( ) {
 
}
 
// appends the specified element to the end of this list.
public void add ( Object data ) {
 
// Initialize Node only incase of 1st element
if ( head == null ) {
head = new Node ( data ) ;
}
 
Node crunchifyTemp = new Node ( data ) ;
Node crunchifyCurrent = head ;
 
// Let's check for NPE before iterate over crunchifyCurrent
if ( crunchifyCurrent ! = null ) {
 
// starting at the head node, crawl to the end of the list and then add element after last node
while ( crunchifyCurrent . getNext ( ) ! = null ) {
crunchifyCurrent = crunchifyCurrent . getNext ( ) ;
}
 
// the last node's "next" reference set to our new node
crunchifyCurrent . setNext ( crunchifyTemp ) ;
}
 
// increment the number of elements variable
incrementCounter ( ) ;
}
 
private static int getCounter ( ) {
return counter ;
}
 
private static void incrementCounter ( ) {
counter ++ ;
}
 
private void decrementCounter ( ) {
counter -- ;
}
 
// inserts the specified element at the specified position in this list
public void add ( Object data , int index ) {
Node crunchifyTemp = new Node ( data ) ;
Node crunchifyCurrent = head ;
 
// Let's check for NPE before iterate over crunchifyCurrent
if ( crunchifyCurrent ! = null ) {
// crawl to the requested index or the last element in the list, whichever comes first
for ( int i = 0 ; i < index && crunchifyCurrent.getNext() != null; i ++ ) {
crunchifyCurrent = crunchifyCurrent . getNext ( ) ;
}
}
 
// set the new node's next-node reference to this node's next-node reference
crunchifyTemp . setNext ( crunchifyCurrent . getNext ( ) ) ;
 
// now set this node's next-node reference to the new node
crunchifyCurrent . setNext ( crunchifyTemp ) ;
 
// increment the number of elements variable
incrementCounter ( ) ;
}
 
public Object get ( int index )
// returns the element at the specified position in this list.
{
// index must be 1 or higher
if ( index < 0 )
return null ;
Node crunchifyCurrent = null ;
if ( head ! = null ) {
crunchifyCurrent = head . getNext ( ) ;
for ( int i = 0 ; i < index ; i ++ ) {
if ( crunchifyCurrent . getNext ( ) == null )
return null ;
 
crunchifyCurrent = crunchifyCurrent . getNext ( ) ;
}
return crunchifyCurrent . getData ( ) ;
}
return crunchifyCurrent ;
 
}
 
// removes the element at the specified position in this list.
public boolean remove ( int index ) {
 
// if the index is out of range, exit
if ( index < 1 | | index > size ( ) )
return false ;
 
Node crunchifyCurrent = head ;
if ( head ! = null ) {
for ( int i = 0 ; i < index ; i ++ ) {
if ( crunchifyCurrent . getNext ( ) == null )
return false ;
 
crunchifyCurrent = crunchifyCurrent . getNext ( ) ;
}
crunchifyCurrent . setNext ( crunchifyCurrent . getNext ( ) . getNext ( ) ) ;
 
// decrement the number of elements variable
decrementCounter ( ) ;
return true ;
 
}
return false ;
}
 
// returns the number of elements in this list.
public int size ( ) {
return getCounter ( ) ;
}
 
public String toString ( ) {
String output = "" ;
 
if ( head ! = null ) {
Node crunchifyCurrent = head . getNext ( ) ;
while ( crunchifyCurrent ! = null ) {
output += "[" + crunchifyCurrent . getData ( ) . toString ( ) + "]" ;
crunchifyCurrent = crunchifyCurrent . getNext ( ) ;
}
 
}
return output ;
}
 
private class Node {
// reference to the next node in the chain, or null if there isn't one.
Node next ;
 
// data carried by this node. could be of any type you need.
Object data ;
 
// Node constructor
public Node ( Object dataValue ) {
next = null ;
data = dataValue ;
}
 
// another Node constructor if we want to specify the node to point to.
@SuppressWarnings ( "unused" )
public Node ( Object dataValue , Node nextValue ) {
next = nextValue ;
data = dataValue ;
}
 
// these methods should be self-explanatory
public Object getData ( ) {
return data ;
}
 
@SuppressWarnings ( "unused" )
public void setData ( Object dataValue ) {
data = dataValue ;
}
 
public Node getNext ( ) {
return next ;
}
 
public void setNext ( Node nextValue ) {
next = nextValue ;
}
 
}
}

Câteva lucruri:

Aici inițializam Node numai în timp ce adding 1st element .

1
2
3
4
// Initialize Node only incase of 1st element
if ( head == null ) {
head = new Node ( data ) ;
}

Rezultat:

1
2
3
4
5
6
7
Print : crunchifyList : [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]
. size ( ) : 5
. get ( 3 ) : 4 ( get element at index : 3 - list starts from 0 )
. remove ( 2 ) : true ( element removed )
. get ( 3 ) : 5 ( get element at index : 3 - list starts from 0 )
. size ( ) : 4
Print again : crunchifyList : [ 1 ] [ 2 ] [ 4 ] [ 5 ]

Îmbunătățirile aduse acestei implementări includ crearea unei double-linked list , adăugarea de metode de insert și delete de la mijloc sau de la sfârșit, precum și prin adăugarea de metode de get și sort .

Răspuns referit de la Stack Overflow de Laurence Gonsalves. Ați putea fi interesat de lista tuturor tutorialelor Java.