8.3.列表处理

\(8.3.\)List Processing

1.List processing

  $a.Creation

  The client process is described as below:

1. We create a V pointer. We will get the variable containing 0, because all local variables are initialized to 0.
2. 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.
3. V is going to point to the base address of the object that was returned by the constructor.
4. 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:

1. We create current, it's an identifier that exist outside the world of list. We use a special variable called this which stands for the current object.

   • this is the point from which we are going to refer to the object that was passed with.

2. The entry point of the list is this, and we set current to this, then we get two pointers referring to the head of the list.

3. Now we enter the loop, we print the data and move current to next.

4. At last we return, current no longer exists and this is reinstated and points to the list as before.

  When the client want to create a list:

1. 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).

2. Once the List.new is called, the previous vesion of V is no longer relevant. The rest steps are trival.

  \(c.\)Recursive access

  Let's take the dispose method as an example:

1. As usual, we first call a variable V. The dispose method doesn't know what V is, so the variable this was passed to dispose.
2. The next isn't null, so we go to the recursive call. The this now points at the tail of the list.

3. We finally meet 5, do the deAlloc and return. Once we do the return, we get completely out of the recursive method, and what used to be called this goes back to be named V.

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