Class LinkedList

Inheritance:

Object  »
  Collection  »
    SequenceableCollection  »
      LinkedList

A LinkedList is a sequenceable collection of Links, which are chainable containers for other objects. Using the message sequence addFirst:, removeLast causes the receiver to behave as a stack; using addLast:, removeFirst causes the receiver to behave as a queue.

Instance Variables:

• firstLink - Link or nil
  The first element of the collection or nil if the collection is empty.

• lastLink - Link or nil
  The last element of the collection or nil if the collection is empty.

Important Instance Methods:

The following methods are all compatible to OrderedCollection.

• addFirst: aLink
  Add aLink as the first element of the collection. Answer aLink.

• addLast: aLink
  Add aLink as the last element of the collection. Answer aLink.

• add: aLink
  same as addLast:.

• removeFirst
  Remove the first element from the collection and answer the removed element.

• removeLast
  Remove the last element from the collection and answer the removed element.

Hint:

It is not allowed to use LinkedList to set up a circular structure. Most of the inherited protocol is not designed to process circular structures and would fail for a circular linked list.

Implementation Notes:

LinkedList computes the length of the list of chained objects to answer the size of the collection. It would be possible to add a counter variable and to update it when elements are added or removed.

Do not carelessly modify the instance protocol of this class! The ProcessorScheduler implements process queues as linked lists. A carelessly introduced bug in one of the instance methods of LinkedList can damage process scheduling, it may even irrecoverably destroy Smalltalk.