Java Reference
In-Depth Information
/
**
Insert"it"atcurrentposition
*
/
publicvoidinsert(Eit){
curr.setNext(Link.get(it,curr.next()));//Getlink
if(tail==curr)tail=curr.next(); //Newtail
cnt++;
}
/
**
Append"it"tolist
*
/
publicvoidappend(Eit){
tail=tail.setNext(Link.get(it,null));
cnt++;
}
/
**
Removeandreturncurrentelement
*
/
publicEremove(){
if(curr.next()==null)returnnull;//Nothingtoremove
Eit=curr.next().element(); //Remembervalue
if(tail==curr.next())tail=curr;//Removedlast
Link<E>tempptr=curr.next(); //Rememberlink
curr.setNext(curr.next().next()); //Removefromlist
tempptr.release();
//Releaselink
cnt--;
//Decrementcount
returnit;
//Returnremoved
}
Figure4.12
Linked-list class members that are modified to use the freelist ver-
sion of the link class in Figure 4.11.
DE, regardless of the number of elements actually stored in the list at any given
time. The amount of space required for the linked list is n(P + E). The smaller
of these expressions for a given value n determines the more space-efficient imple-
mentation for n elements. In general, the linked implementation requires less space
than the array-based implementation when relatively few elements are in the list.
Conversely, the array-based implementation becomes more space efficient when
the array is close to full. Using the equation, we can solve for n to determine
the break-even point beyond which the array-based implementation is more space
efficient in any particular situation. This occurs when
n > DE=(P + E):
If P = E, then the break-even point is at D=2. This would happen if the element
field is either a four-byte
int
value or a pointer, and the next field is a typical four-
byte pointer. That is, the array-based implementation would be more efficient (if
the link field and the element field are the same size) whenever the array is more
than half full.
As a rule of thumb, linked lists are more space efficient when implementing
lists whose number of elements varies widely or is unknown. Array-based lists are
generally more space efficient when the user knows in advance approximately how
large the list will become.
