eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'LinkedList':

Home

Documentation
www.exept.de
Everywhere
for:
 [back]

Class: LinkedList

Inheritance:

   Object
   |
   +--Collection
      |
      +--SequenceableCollection
         |
         +--LinkedList
            |
            +--DoubleLinkedList
Package:
stx:libbasic
Category:
Collections-Linked
Version:
rev: 1.61 date: 2021/01/20 13:03:16
user: cg
file: LinkedList.st directory: libbasic
module: stx stc-classLibrary: libbasic

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


copyright
COPYRIGHT (c) 1989 by Claus Gittinger
             All Rights Reserved

This software is furnished under a license and may be used
only in accordance with the terms of that license and with the
inclusion of the above copyright notice.   This software may not
be provided or otherwise made available to, or used by, any
other person.  No title to or ownership of the software is
hereby transferred.

Class protocol:

instance creation
o  new
create and return a new LinkedList

Instance protocol:

accessing
o  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

o  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

Usage example(s): 

     |l|

     l := LinkedList new.
     l add:'one'.
     l add:'two'.
     l add:'hello'.
     l at:3 ifAbsent:'missing'.
     l at:4 ifAbsent:'missing'.

o  first
return the first value in the list

o  firstIfEmpty: exceptionalValue
return the first value in the list or exceptionlValue, if empty

o  firstLink
return the first node in the list

o  firstLinkIfEmpty: exceptionalValue
return the first node in the list or exceptionlValue, if empty

o  last
return last value in the list

o  lastLink
return last node in the list

o  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

adding & removing
o  add: aLinkOrAnyOtherObject
adds aLink to the end of the sequence. Returns aLink

o  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.

o  addFirst: aLinkOrAnyOtherObject
adds aLink to the beginning of the sequence. Returns aLink

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

o  removeAll
remove all elements from the sequence. Returns the receiver.

o  removeFirst
remove and return the first node from the sequence

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

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

enumerating
o  do: aBlock
evaluate the argument, aBlock with for every value element in the list

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

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

initialization
o  initialize

queries
o  isEmpty
return true, if the collection is empty

o  notEmpty
return true, if the collection is not empty

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

searching-equality
o  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.

Usage example(s): 

     |l|

     l := LinkedList new.
     l indexOf:'hello' startingAt:1

Usage example(s): 

     |l v|

     l := LinkedList new.
     l add:(ValueLink new value:'one').
     l add:(ValueLink new value:'two').
     l add:(v := ValueLink new value:'hello').
     l indexOf:v startingAt:2.

searching-identity
o  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.

Usage example(s): 

     |l|

     l := LinkedList new.
     l identityIndexOf:'hello' startingAt:1

Usage example(s): 

     |l v|

     l := LinkedList new.
     l add:(ValueLink new value:'one').
     l add:(ValueLink new value:'two').
     l add:(v := ValueLink new value:'hello').
     l identityIndexOf:v startingAt:2.

testing
o  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.

ST/X 7.7.0.0; WebServer 1.702 at 20f6060372b9.unknown:8081; Sat, 27 Jul 2024 06:47:52 GMT