So implementieren Sie eine LinkedList-Klasse von Grund auf neu in Java

Veröffentlicht: 2013-06-19
Crunchify Java LinkedList-Implementierungs-Tutorial

Wenn Sie tatsächlich ein echtes Produktionssystem bauen, dann würden Sie normalerweise einfach die Dinge in der Standardbibliothek verwenden, wenn das, was Sie brauchen, dort verfügbar ist. Betrachten Sie dies jedoch nicht als sinnlose Übung.

Es ist gut zu verstehen, wie die Dinge funktionieren, und understanding linked lists ist ein wichtiger Schritt zum Verständnis komplexerer Datenstrukturen, von denen viele in den Standardbibliotheken nicht vorhanden sind.

Es gibt einige Unterschiede zwischen der Art und Weise, wie Sie eine verknüpfte Liste erstellen, und der Art und Weise, wie die Java-Sammlungs-API dies tut.

Die Sammlungs-API versucht, sich an eine kompliziertere Schnittstelle zu halten. Ihre LinkedList hat immer mindestens ein Element.

Bei dieser Art von Setup würden Sie null verwenden, wenn Sie eine leere Liste benötigen. Stellen Sie sich „nächster“ als „den Rest der Liste“ vor. Tatsächlich würden viele Leute es tail statt „Next“ nennen.

Hier ist ein Diagramm einer einzelnen LinkedList:

Crunchify Einfach verkettete Liste Beispiel

Ein weiteres muss gelesen werden:

  • Wie durchläuft man die LinkedList-Instanz in Java?
  • Java: Wie finde ich das mittlere Element von LinkedList?

Was ist der beste Weg, um eine Linkedlist in Java von Grund auf neu zu erstellen?

Nun, hier ist eine einfachste Implementierung der LinkedList-Klasse in Java.

LinkedList in Java von Grund auf neu - Crunchify Tutorial
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 ;
}
 
}
}

Wenige Sachen:

Hier initialisieren wir den Node nur, während wir adding 1st element .

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

Ergebnis:

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 ]

Zu den Verbesserungen an dieser Implementierung gehören das Erstellen einer double-linked list , das Hinzufügen von Methoden zum insert und delete in der Mitte oder am Ende sowie das Hinzufügen von get und sort -Methoden.

Referenzierte Antwort von Stack Overflow von Laurence Gonsalves. Sie könnten an einer Liste aller Java-Tutorials interessiert sein.