--- a/LinkedList.st Thu Aug 11 06:44:08 2016 +0200
+++ b/LinkedList.st Fri Aug 12 06:44:59 2016 +0200
@@ -1,5 +1,3 @@
-"{ Encoding: utf8 }"
-
"
COPYRIGHT (c) 1989 by Claus Gittinger
All Rights Reserved
@@ -182,6 +180,17 @@
theLink := self linkAt:index ifAbsent:[^ exceptionValue value].
^ theLink value
+
+ "
+ |l|
+
+ l := LinkedList new.
+ l add:'one'.
+ l add:'two'.
+ l add:'hello'.
+ l at:3 ifAbsent:'missing'.
+ l at:4 ifAbsent:'missing'.
+ "
!
first
@@ -230,7 +239,7 @@
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,
+ 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.
@@ -238,14 +247,17 @@
but please consider using another type of collection if you use it"
|theLink
- runIndex "{Class: SmallInteger}"|
+ count "{Class: SmallInteger}"|
+
+ count := index.
+ (count < 1 or:[count > numberOfNodes]) ifTrue:[
+ ^ exceptionBlock value.
+ ].
theLink := firstLink.
- runIndex := 1.
- [runIndex == index] whileFalse:[
+ count-1 timesRepeat:[
theLink isNil ifTrue:[^ exceptionBlock value].
theLink := theLink nextLink.
- runIndex := runIndex + 1.
].
^ theLink
! !
@@ -438,6 +450,7 @@
|thisNode|
+ "aBlock may add elements, so do not use 'numberOfNodes-1 timesRepeat:[]'"
thisNode := firstLink.
[thisNode notNil] whileTrue:[
aBlock value:thisNode value.
@@ -450,6 +463,7 @@
|thisNode|
+ "aBlock may add elements, so do not use 'numberOfNodes-1 timesRepeat:[]'"
thisNode := firstLink.
[thisNode notNil] whileTrue:[
aBlock value:thisNode.
@@ -492,21 +506,26 @@
but please consider using another type of collection if you use it.
"
- |theNode idx "{ Class: SmallInteger }"
+ |theNode count "{ Class: SmallInteger }"
linkOrValue|
+ count := start.
+ (count < 1 or:[count > numberOfNodes]) ifTrue:[
+ ^ 0.
+ ].
+
+ theNode := firstLink.
+ count-1 timesRepeat:[
+ theNode isNil ifTrue:[^ 0]. "reached the end"
+ theNode := theNode nextLink.
+ ].
+
linkOrValue := aLinkOrValue value.
- theNode := firstLink.
- idx := 1.
- [idx < start] whileTrue:[
- theNode isNil ifTrue:[^ 0]. "reached the end"
+
+ [theNode notNil] whileTrue:[
+ (linkOrValue = theNode value) ifTrue:[^ count].
theNode := theNode nextLink.
- idx := idx + 1.
- ].
- [theNode notNil] whileTrue:[
- (linkOrValue = theNode value) ifTrue:[^ idx].
- theNode := theNode nextLink.
- idx := idx + 1.
+ count := count + 1.
]. "reached the end"
^ 0
@@ -514,7 +533,7 @@
|l|
l := LinkedList new.
- l indexOf:'hello'
+ l indexOf:'hello' startingAt:1
"
"
@@ -524,7 +543,7 @@
l add:(ValueLink new value:'one').
l add:(ValueLink new value:'two').
l add:(v := ValueLink new value:'hello').
- l indexOf:v
+ l indexOf:v startingAt:2.
"
! !
@@ -542,21 +561,26 @@
but please consider using another type of collection if you use it.
"
- |theNode idx "{ Class: SmallInteger }"
+ |theNode count "{ Class: SmallInteger }"
linkOrValue|
+ count := start.
+ (count < 1 or:[count > numberOfNodes]) ifTrue:[
+ ^ 0.
+ ].
+
+ theNode := firstLink.
+ count-1 timesRepeat:[
+ theNode isNil ifTrue:[^ 0]. "reached the end"
+ theNode := theNode nextLink.
+ ].
+
linkOrValue := aLinkOrValue value.
- theNode := firstLink.
- idx := 1.
- [idx < start] whileTrue:[
- theNode isNil ifTrue:[^ 0]. "reached the end"
+
+ [theNode notNil] whileTrue:[
+ (linkOrValue == theNode value) ifTrue:[^ count].
theNode := theNode nextLink.
- idx := idx + 1.
- ].
- [theNode notNil] whileTrue:[
- (linkOrValue == theNode value) ifTrue:[^ idx].
- theNode := theNode nextLink.
- idx := idx + 1.
+ count := count + 1.
]. "reached the end"
^ 0
@@ -564,7 +588,7 @@
|l|
l := LinkedList new.
- l indexOf:'hello'
+ l identityIndexOf:'hello' startingAt:1
"
"
@@ -574,7 +598,7 @@
l add:(ValueLink new value:'one').
l add:(ValueLink new value:'two').
l add:(v := ValueLink new value:'hello').
- l indexOf:v
+ l identityIndexOf:v startingAt:2.
"
! !