add:, do:,
remove:ifAbsent:, and
size ... the other methods can all be inherited
from Collection. (For example, printOn:,
collect:, etc will all now work on linked lists.) We'll
represent the linked list in the usual way as a list of list nodes (see
class definition below).
We make a separate class LinkedList rather than just passing around the node at the head of the list so that we can have a single object representing the list as we add and delete elements -- if we just passed around the head of the list the identity of the list can change (which is not how collections work in Smalltalk).
If you want to file these classes in, first file in the ListNode class (later) and then the LinkedList class.
Collection subclass: #LinkedList
instanceVariableNames:
'head '
classVariableNames: ''
poolDictionaries: '' !
!LinkedList class methods !
new
"make a new instance of LinkedList, initialize it, and return it"
^super new initialize! !
!LinkedList methods !
add: item
"override from Collection: add item to this list"
head := NonEmptyListNode new first: item rest: head!
do: aBlock
"override from Collection: evaluate aBlock for every element of the list"
head do: aBlock!
initialize
"private initialization method: make this an empty list"
head := EmptyListNode new.!
remove: anObject ifAbsent: aBlock
"override from Collection: remove anObject from the list.
This makes use of an auxiliary method for link elements.
Note that the auxiliary version returns the new head of
the list in all cases (in case we are removing the first element)."
head := head remove: anObject ifAbsent: aBlock!
size
"return the number of elements in this list"
| n |
n := 0.
self do: [:x | n := n+1].
^n! !
Here is the helper class ListNode. Rather than having just one class, we
make an abstract class ListNode -- which specifies the methods that
ListNodes must understand -- and define two concrete subclasses, for
EmptyListNode and NonEmptyListNode. Note how elegantly this lets us
implement different versions of do: and
remove:ifAbsent:
Object subclass: #ListNode
instanceVariableNames: ''
classVariableNames: ''
poolDictionaries: '' !
!ListNode class methods ! !
!ListNode methods !
do: aBlock
"evaluate aBlock for each element in this list. Since the list
is empty do nothing."
^self implementedBySubclass!
remove: anObject ifAbsent: aBlock
"remove anObject from this linked list (if present) and return
the new head of the list. Evaluate aBlock if it's not found. "
^self implementedBySubclass! !
ListNode subclass: #EmptyListNode
instanceVariableNames: ''
classVariableNames: ''
poolDictionaries: '' !
!EmptyListNode class methods ! !
!EmptyListNode methods !
do: aBlock
"evaluate aBlock for each element in this list. Since the list
is empty do nothing."!
remove: anObject ifAbsent: aBlock
"remove anObject from this linked list (if present) and return
the new head of the list. Evaluate aBlock if it's not found. "
aBlock value.
^self! !
ListNode subclass: #NonEmptyListNode
instanceVariableNames:
'first rest '
classVariableNames: ''
poolDictionaries: '' !
!NonEmptyListNode class methods ! !
!NonEmptyListNode methods !
do: aBlock
aBlock value: first.
rest do: aBlock!
first: f rest: r
first := f.
rest := r.!
remove: anObject ifAbsent: aBlock
"remove anObject from this linked list (if present) and return
the new head of the list. Evaluate aBlock if it's not found"
first = anObject ifTrue: [^rest].
rest := rest remove: anObject ifAbsent: aBlock.
^self! !