Class: LinkedList

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

Inheritance:

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

Package:

stx:libbasic

Category:

Collections-Linked

Version:

rev: 1.58 date: 2019/02/10 13:54:52

user: cg

file: LinkedList.st directory: libbasic

module: stx stc-classLibrary: libbasic

Author:

Claus Gittinger (July 1993)

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 scheduler's 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 at a time
    - 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 value - 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 O^2 runtime).
It is a very bad idea to access LinkedList elements by index.
many algorithms degenerate to poor performance if you do.
This method is provided for protocol completeness,
but please consider using another type of collection if you use it

 at: index ifAbsent: exceptionValue

return the n'th value - 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 O^2 runtime).
It is a very bad idea to access LinkedList elements by index.
many algorithms degenerate to poor performance if you do.
This method is provided for protocol completeness,
but please consider using another type of collection if you use it

 first

return the first value in the list

 firstIfEmpty: exceptionalValue

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

 firstLink

return the first node in the list

 firstLinkIfEmpty: exceptionalValue

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

 last

return last value in the list

 lastLink

return last node in the list

 linkAt: index ifAbsent: exceptionBlock

return the n'th link - 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 the superclass, SequenceableCollection are based on at:-access,
so other inherited methods may be very slow (showing O^2 runtime).
It is a very bad idea to access LinkedList elements by index.
many algorithms degenerate to poor performance if you do.
This method is provided for protocol completeness,
but please consider using another type of collection if you use it

 add: aLinkOrAnyOtherObject

adds aLink to the end of the sequence. Returns aLink

 add: aLinkOrAnyOtherObject after: aLinkOrValue

adds aLinkOrAnyOtherObject after another aLinkOrValue.
If aLinkOrValue is nil, linkToAdd is inserted at the beginning.
If aLinkOrValue is not in the list, linkToAdd is added at the end.
Returns aLinkOrAnyOtherObject.

 addFirst: aLinkOrAnyOtherObject

adds aLink to the beginning of the sequence. Returns aLink

 remove: aLinkOrValue ifAbsent: exceptionBlock

remove the argument, aLinkOrValue from the sequence and return it;
if absent, evaluate the exceptionBlock.

 removeAll

remove all elements from the sequence. Returns the receiver.

 removeFirst

remove and return the first node from the sequence

 removeIdentical: aLinkOrValue ifAbsent: exceptionBlock

remove the argument, aLinkOrValue from the sequence and return it;
if absent, evaluate the exceptionBlock.

 removeLast

remove the last link element and return it;
if empty, raise an exception.

 do: aBlock

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

 linksDo: aBlock

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

 printElementsDo: aBlock

perform aBlock (1 arg) for all elements.
Used in #printOn:.

 initialize

 isEmpty

return true, if the collection is empty

 notEmpty

return true, if the collection is not empty

 size

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

 indexOf: aLinkOrValue startingAt: start

search the collection for aLinkOrValue, starting the search at index start;
if found, return the index otherwise return 0.
Here, index is defined as the link-node's position in the list.
The comparison is done using = (i.e. equality test - not identity test).
Warning:
it is a very bad idea to access LinkedList elements by index.
many algorithms degenerate to poor performance if you do.
This method is provided for protocol completeness,
but please consider using another type of collection if you use it.

 identityIndexOf: aLinkOrValue startingAt: start

search the collection for aLinkOrValue, starting the search at index start;
if found, return the index otherwise return 0.
Here, index is defined as the link-node's position in the list.
The comparison is done using == (i.e. identity test - not equality test).
Warning:
it is a very bad idea to access LinkedList elements by index.
many algorithms degenerate to poor performance if you do.
This method is provided for protocol completeness,
but please consider using another type of collection if you use it.

 isFixedSize

return true if the receiver cannot grow

Examples:

    |l|

    l := LinkedList new.
    l addLast:'one'.
    l addLast:'two'.
    l addLast:'three'.
    l addLast:'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 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.