Hello, everyone.
In this video, we are going to learn generalized list in Chapter 12 of Data Structure and Algorithm.
I'm going to introduce some concepts about generalized list and its storage and algorithms.
Let's see its relationship with linear list.
In linear list, elements are of the same type.
Even the size of storage is fixed.
Sometimes we may handle an list that its elements are of different types.
And there may be sub-lists in the list.
In that case, we should use generalized list.
The representation of generalized list seems linear, but its elements may be of different types.
Some elements are atomic, while others may be sub-list.
A sub-list may be referred multiple times, so we'd better give it a name.
In addition, the size of the top level of the list should be determined.
The sub-list can be iterative defined, so the generalized list has a property of depth.
If sub-lists are defined recursive, the depth is infinite.
Let's look at two important concepts, head and tail.
The head of a generalized list is the first element of it.
The head may be an atom or a sub-list.
The tail is the sub-list that removes the head from the original list.
In such a definition, we can conveniently represent a generalized list.
So we can use such recursive definition to represent the structure of storage.
And for the algorithm, we can also take advantage of such a structure, by processing the head node firstly and recursive processing the rest of the generalized list.
It seems like that we process the head node one by one, until the whole list is processed.
Let's look at some forms of generalized list.
The simplest is pure list.
In a pure list, there is only one path from the root to every leaf.
In other words, the paths are not re-entrant.
Every node has at most one in-edge.
Another list is re-entrant list, such as L1.
L1 is referred by two up-level list, so it's re-entrant.
If the re-entrant list doesn't have a circle, it's equal to a DAG(Directed Acyclic Graph).
If it has a circle, it can be extended infinitely, so its depth is infinite.
There are two circles.
The first one is L4.
It consists of d and L4 itself, so it's a self-circle.
However, L1 and L2 are pointing to each other, so they form a indirected circle.
Let's look at the form of this generalized list.
The biggest re-entrant list consists of some different sub-lists.
You can extend it layer by layer.
E consists of B and D, and D is a independent list, and B is like this.
We can see that D refers B, so both E and D point to B, so B is a re-entrant structure.
In this list, we should label the sub-list to represent re-entrant structure.
Such as List B, when it occurs firstly, we extend it to 6, 2.
And when it occurs subsequently, we just need to refer its name, B, other than extending it.
Labels make it convenient to represent recursive list, such as F.
We can see, the structures in this diagram can be corresponding to the structure of graph, which we have learned.
The little difference is that in graph we don't consider the case of self-circle.
After all, if we allow re-entrance, it's re-entrant list, otherwise it's pure list.
If a pure list just has one layer, it's a linear list.
If a re-entrant list has circle, its recursive list.
That's their relations.
Generalized list can be applied in variety of situations, such as function call.
You can regard a function as a sub-list.
In a function, there may be several layers, calling several functions.
In addition, functional blocks in a function can be regarded as atoms, which can not be extended to sub-list.
Another example of generalized list is the relation of references in memory.
There is an AI language, named LISP, using the structure of generalize list.
The structure of generalized list.
Firstly we should distinguish sub-list and atom, because atom needn't to extend.
Obviously, we can't extend the sub-list in this layer.
When deleting data, we should traverse the whole generalized list to find all the pointers pointing to the data.
After finding the pointers, we modify them to pointing the nest element to the data.
Thus, we complete to delete the data and release a node.
It's quite inconvenient.
So we consider to add a head node for each sub-list.
A node has three values, head, data and pointer.
For an atom, its head equals 0.
For an sub-list, its head equals 1.
Then, the first node of a sub-list is a virtual node.
We set the head of virtual node to -1.
Then if we need to delete some data, we just delete it directly, because all references are reserved by the head node.
It's quite more convenient than before.
Let's consider the traversal in a recursive generalized list.
The traversal is just like the depth-first traversal in a graph.
It begins at the first element.
If it meets an atom, print it.
If it meets a sub-list, traverse into it.
If we finish to traversal a sub-list, we trace back to the up-layer list and continue to traverse the next element.
If we meet a sub-list having been visited, we just print its name, like L2.
We continue to depth-first traversing, until the whole list is visited.
Finally, I leave some questions.
We can see that the generalized list has some relationship with linear list, tree and graph.
So what's the relationship? What's the similarities and differences between them?
In addition, you can implement an traversal algorithm of generalized list.
Traversal is a basic function of every data structure, as insertion, searching and other functions are based on traversal.
Thank you!