Hello everyone
Now we learn data structures and algorithms
The second chapter the linear list's
final content
Compare the
sequential list and linked list and you'll see
for sequential list, because it is implemented using an array
it has no pointer
So for the operation
Ii is very convenient
And in sequential list
we specify a sequence
which is the index value
Then come back to read the corresponding element
This is also very convenient
The linked list's
advantage is that
I do not need to be specified The size of this linear list
in advance
According to my need
it can dynamically generate this node
So
it is ideally suited for dynamic insertion and deletion of cases
Therefore,the sequential list is more suited to
relatively static scenes
The linked list is suitable for more dynamic environments
Now we look at some features
about the sequential list and linked list
in time and space
For sequential list,
its insertion and deletion
in order to maintain a consistent relationship between memory and logic
in average case , we probably need to
move about half of the elements
So its cost is a big O (n)
But in finding side,it is also very easy
so it is the big O (1)
Sequential list requires
a continuous fixed-length array everytime
In this situation
sometimes
when you apply a particularly large array
the system runs out of continuous space
then you may fail
Besides
if this sequential list
is very full of array elements
for we do not require such additional
space to maintain the logical relationship between the elements
inside the sequential list
Therefore
its structural cost
is very low
Its storage density is very high
For linked list
from this single algorithm
its insert and delete operations is
just after the positioning
I just need to be inserted on the current
Or in this element to be deleted position
and conduct a number of local
pointer changes
This is very fast
It is big O (1) time
But this positioning operation is very troublesome
I must find the i-th element in the linked list
this often start to go one by one from the header
In the average case
I must traverse the list's
about half of the elements
Therefore, cost of finding its i-th element
is big O (n)
We put this together with the positioning operation
Taken together it
sequential list and linked list
are both big O (n) time
The linked list on the memory
utilizes the advantages of such a pointer
Therefore, it can dynamically as needed
to apply or release space
Its storage efficiency
is not so high
Not as high as sequential list
Each node has its structural overhead
To maintain its next element
which is the next field
While also need maintaining a content of a structure
like an element prev domain
So its storage density
is much lower than the sequential list
Now we look at the sequential list and linked list's
estimate of their storage densities
I assume there are n valid elements
and P is a pointer cost
Our cost of data field is E
For sequential list
for I want to apply for a pre-
relatively large space
that may also be slightly larger than the current element
the number n
The D is number of sequential list
It is an application that can accommodate
the largest number of the number of elements
For the Space Requirements table order
that is DE
And the linked lists's space requirements
is n (P + E)
We can find
n has a critical situation
which is DE / (P + E)
When n is becoming greater
this sequential list's space efficiency is higher
When P = E
We can estimate the value of this critical value
is D / 2
That means when in the whole sequential list
more than half of all elements
is full
Our sequential list's
storage efficiency is more than a linked list
For sequential list and the linked list
they have some scenes respectively
not suitable
For example, in the sequential list
if you do often want to insert or delete
this element of the table
or do a lot of dynamic modification
Or that you do not know
your list's length
then you can not estimate in advance
how much space you need to set aside
This case
do not very suitable
For the linked list
if I often need to read
the i-th element of it
I need one by one to read from the header
until the tail
If this operation is too often
then the linked list is not a very good data structure too
Another case is
Pointer relatived to the data field
occupies a larger space
If this linear list's
elements is the character
Character relatived to the pointer
Its space is much smaller
If you enforce to realize it with the list
its storage efficiency is very low
For sequential list and linked list
they are suitable for some of the scenes
We can summarized that
for the sequential list
If in your entire linear list
its number of nodes
can roughly be estimated
and its state of nodes is
Relatively stable
that means insertion and deletion is not so frequent
and this n
is larger than a critical value of such a situation
We are very suitable for use sequential list
For linked list
If the number of nodes in the linear
can not be predicted
and if insert /delete
changes frequently
and n is less than this critical value
That is to say, if you use the linked list
its storage density loss is not so great
in this case we use the linked list on the suitability
Finally, everyone think about
sequential list and linked list
When we choose them
What issues need to be considered
For example, the dynamics of the node's changing
which means the frequency of insert or deletion
and storage density and so on
We give you a linear list's
applications as example
For a polynomial terms
it
has a corresponding coefficient
In linear list
we can express that
assuming each element inside the table
Corresponds to the term in the polynomial
For example, pi corresponding to xi's coefficients
In this case
We collect all the coefficients
in order
to form a linear list
For this linear list
if we put it there inside the array
I just need to save its coefficient
pi corresponding to the i-th element
xi's coefficients
is able to express
such a polynomial
For data-intensive case
this is no problem
However, if these items are very sparse
for instance
for this situation
If you open such a large array
Like this example, then
you must open such an array more than 40,000
While inside it has only two non-0 unitaries
Obviously it is very inefficient storage
Based on this store
We also do very inefficient operation
It wants you to recover such an expression
like a one unitary polynomial
then you have to go inside the array one by one to find
its non-0
In this case
We use the linked list to represent
will be very convenient
nodes of my list
in addition to the coefficient
I also have kept its index
and one more pointer domain
The polynomial
can be expressed in such a way
You can see
it can be very convenient from the header node
until the end of the list
Immediately we can find its non-0
out
For such an application of a polynomial
We can experiment it with
a polynomial algorithm for addition
and the subtraction algorithm
Thank you