Class: LinkedList

• Inheritance
• Description
• Warning
• Related information
• Class protocol
  • instance creation
• Instance protocol
  • accessing
  • adding & removing
  • enumerating
  • initialization
  • queries
  • testing
• Examples

Inheritance:

   Object
   |
   +--Collection
      |
      +--SequenceableCollection
         |
         +--LinkedList

Package:

stx:libbasic

Category:

Collections-Linked

Version:

rev: 1.37 date: 2007/07/05 11:23:33

user: cg

file: LinkedList.st directory: libbasic

module: stx stc-classLibrary: libbasic

Author:

Claus Gittinger

Description:

this class implements an anchor to a list of Links.
The data itself is held in the link elements.
See (the abstract) Link, ValueLink and (possibly other) classes,
which can be used as elements of a linkedList.

LinkedList does not care for storage; all it does is handling
chained link elements, which must respond to #nextLink/#nextLink:.
(i.e. any object which can do this, can be used as elements of a linked
 list).
An abstract superclass for linkElements is Link; a concrete class is
ValueLink, which holds a reference to some object.


Although LinkedList is a subclass of SequenceableCollection (and therefore
supports indexed access via at:), you should be careful in using it or
other methods based upon at:.
The reason is that #at: walks the linkedlist to find the indexed element
and is therefore slow.
This means that some linear-in-time algorithms inherited from
SequenceableCollection become square in runtime.
In general, if you need access via a numeric index, you better use Array,
OrderedCollection or similar.

For the above reasons, the system does not make heavily use of LinkedLists;
the only good application is where elements must be repeatedly be removed
at the front and added at the end.
(the schedulers process handling code does this to manage process lists.)

[memory requirements:]
    (OBJ-HEADER + (3 * ptr-size)) * size
                + any additional instvars due to subclassing

Warning:

Be careful when subclassing Link, since there is a big drawback,
which may be overlooked by beginners:
    a Link element can only be in one LinkedList
    - adding the same element to another LinkedList
    will remove it from the first as a side effect.
Therefore, NEVER simply add something to a linkedList (except for
valueLinks) unless you know what you do.
The ST-80 implementors probably wanted this behavior, to move
processes from the waitingList to runLists and vice versa;
however, literature seems to not point this out enough.

Related information:

    Link
    ValueLink
    Process

Class protocol:

 new

create and return a new LinkedList

Instance protocol:

 at: index

return the n'th element - use of this method should be avoided,
since it is slow to walk through the list - think about using
another collection if you need indexed access.
Notice, that many methods in SeqColl are based on at:-access,
so other inherited methods may be very slow (showing square runtime).

 at: index ifAbsent: exceptionBlock

return the n'th element - use of this method should be avoided,
since it is slow to walk through the list - think about using
another collection if you need indexed access.
Notice, that many methods in SeqColl are based on at:-access,
so other inherited methods may be very slow (showing square runtime).

 first

return the first node in the list

 firstIfEmpty: exceptionalValue

return the first node in the list or exceptionlValue, if empty

 last

return last node in the list

 add: aLink

adds aLink to the end of the sequence. Returns aLink

 add: linkToAdd after: aLink

adds linkToAdd after another link, aLink. If aLink is nil,
linkToAdd is inserted at the beginning. Returns linkToAdd.

 addFirst: aLink

adds aLink to the beginning of the sequence. Returns aLink

 remove: aLink ifAbsent: exceptionBlock

remove the argument, aLink from the sequence and return it;
if absent, evaluate the exceptionBlock.
Actually this is really a #removeIdentical (but for compatibility ...)

 removeAll

remove all elements from the sequence. Returns the receiver.

 removeFirst

remove and return the first node from the sequence

 do: aBlock

evaluate the argument, aBlock with 1 arg for every element in the list

 initialize

 size

return the size of the LinkedList i.e. the number of nodes

 identityIndexOf: aLink startingAt: start

search the collection for aLink, starting the search at index start;
if found, return the index otherwise return 0. Here, index is defined
as the link-nodes position in the list.
The comparison is done using ==
(i.e. equality test - not identity test).

 indexOf: aLink startingAt: start

search the collection for aLink, starting the search at index start;
if found, return the index otherwise return 0. Here, index is defined
as the link-nodes position in the list.
The comparison is done using = (i.e. equality test - not identity test).

 isEmpty

return true, if the collection is empty

 notEmpty

return true, if the collection is not empty

Examples:

    |l|

    l := LinkedList new.
    l addLast:(ValueLink new value:'one').
    l addLast:(ValueLink new value:'two').
    l addLast:(ValueLink new value:'three').
    l addLast:(ValueLink new value:'four').
    l inspect

    |l|

    l := LinkedList new.
    l addLast:(ValueLink new value:'one').
    l addLast:(ValueLink new value:'two').
    l addLast:(ValueLink new value:'three').
    l addLast:(ValueLink new value:'four').
    (l at:3) value inspect.        'slow operation for large lists'.

    |l link|

    l := LinkedList new.
    l addLast:(ValueLink new value:'one').
    l addLast:(ValueLink new value:'two').
    l addLast:(ValueLink new value:'three').
    l addLast:(ValueLink new value:'four').
    link := l removeFirst.
    l addLast:link.
    l inspect.