8.3.列表处理
\(8.3.\)List Processing
1.List processing
$a.Creation
The client process is described as below:
- We create a V pointer. We will get the variable containing 0, because all local variables are initialized to 0.
- We invoke the list constructor, and the list constructor is going to come back with a block of memory that represents the number 5 and null.
- V is going to point to the base address of the object that was returned by the constructor.
- The previous version of V is no longer relevant, and the next command will do exactly the same.
\(b.\)Sequential access
We will use the print
method to illustrate the
sequential process:
In Object-based Programming, when we call a method on an object, we are implicitily passing the object as a parameter to this method.
In the constructor, we do these things:
We create
current
, it's an identifier that exist outside the world of list. We use a special variable calledthis
which stands for the current object.this
is the point from which we are going to refer to the object that was passed with.
- The entry point of the list is
this
, and we setcurrent
tothis
, then we get two pointers referring to the head of the list.
- Now we enter the loop, we print the
data
and movecurrent
tonext
.
- At last we
return
,current
no longer exists andthis
is reinstated and points to the list as before.
When the client want to create a list:
- It all starts by creating a
V
pointer. We get the variable containing value 0 because all local variables are initialized to 0.
Then we call the constructor, and the list constructor is going to
come back with a block of memory that represents the
(5, null)
.
- Once the
List.new
is called, the previous vesion ofV
is no longer relevant. The rest steps are trival.
\(c.\)Recursive access
Let's take the dispose
method as an example:
- As usual, we first call a variable
V
. Thedispose
method doesn't know whatV
is, so the variablethis
was passed todispose
. - The
next
isn't null, so we go to the recursive call. Thethis
now points at the tail of the list.
- We finally meet 5, do the
deAlloc
andreturn
. Once we do thereturn
, we get completely out of the recursive method, and what used to be calledthis
goes back to be namedV
.
- Now the
V
points to nothing, for we basically disposed everything in this list.
However, recursion is very inefficient operation and if you do this
with a big list, you will probably get a StackOverflow
error.
4.List representation
The following list:
is represented in the host RAM like this:
Then who makes these work?
- High-level: the constructor
- Low-level: when compiling the constructor, the compiler plants calls to OS routines that find, and allocate, available memory space for the new object.