Hello everyone
in Data structures and algorithms
We'll continue to learn the second chapter of the linear list
Today we learn the Link structure
among linear list
That is the linked list
Linked list express the logical relationships 8 00:00:18,034 --> between the data
by pointers
In addition to this data data field
We also need a next field
It is such a memory address
pointing to its successor element
According to its linked list form
and how many pointers are there
link lists can be divided into singly, doubly and circular linked list
For simple singly list of it
We may have learned this pointer
when we learn designed programming languange
For the singly list
the implement of it
is often the head pointer
That means is linked directly to the first element
of the list
If it is an empty list
that head pointer is equal to an empty directly
In the data structure
We take singly linked list with the head point in.
This node inside the list is the same with
other elements
It has a feature that
there is a data field
which is meaningless
For the first element of it
it is the next field which the head pointer points to
Then if it is an empty list
we can not say head is equal to an empty
Because the head is not always empty
We should determine the next field of head
whether it is pointing to empty
In this case
in fact when we express
this current element
It is often expressed by the precursor node
In this case
in many operatoins
this can be very convenient
Now we look at the node type of singly list
In the definition of it
In addition to the data field
I have a point to this node in my whole list
a pointer of the same type
By the next pointer field
the nodes in the singly list
can be associated
Let's look at the definition of singly list
in addition to these functions
definition of those CRUD
in linear list
I have head and tail
these two variables
to maintain such head or tail nodes
inside the singly list
I have a function
that specifies the location of such a subscript
Then
I find it appropriate pointer and node
We look at finding I-th element algorithm
in a singly list
This algorithm
In fact, it corresponds to our sequential list
namely that an array
for the i-th subscript element to be positioned
this i
It is also numbered from 0 to n-1
For this positioning
My first step is to set a variable count = 0
Then I counts
If i = -1
In fact, what we mean positioning
that current position is before the first element
inside the whole list
That is to say
in the case of insertion
my requirement is inserted element into the head of the entire linear list
as the first element
In this case
A parameter we entered
Is i = -1
In this case we are returning
its virtual head node inside the entire
linear list
For other cases
We start with the linear list's
first valid element
That is, from the next node of the virtual
head node
We assign it as p
Then, when this p is not empty
and the count has not reached
the i you specified
We just let p = p->next
Then go down and continue the count
If such a positioning element is found
then we will return the corresponding node p
Now we look at
Insertion of the singly list
If I was inserting an element
before 12 at the current node
first I want to create a new element
And then I link this new element 10
with its successor and predecessor
in the linked list
Then it is inserted into the list
We look at the implement of this algorithm
in this algorithm
it is required in the subscripts i
to insert an element
I gave a value "value"
First, find the i subscript
Its predecessor node
We give "setPos"
For this parameter
the value "i-1" is assigned to it
If such a legal position can not find
we will return false
After it found
We start a new node q
Then set this node q's
value to "value"
Its next field
We set the p->next
In fact, it is what we inserted
the i-th node
Then we have to do some judge
See if p is in the tail
If p is at the end of it
In fact, this means
this parameter i you just passed
is equal to n
That means you insert
throughout this list
In this case
We need to put this list's tail pointer tail
as just inserted q
then return true
Now for delete of singly list
We first need to locate it
This node you need to delete
This positioning process
may be located
based on the value or subscript
And then we put this node
down from the single chain
Finally, to release its relative space
Let's see
Such a delete example
First,
I have this to be deleted node x
I am also by positioning algorithm
Then I found its precursor p
The process of locating it
is also start from the virtual head node
Then one by one to find
seeing p's next field
If it is not x
then continue to look down
until X has been found just a precursor of p
When we delete it
I put this p, its next
recorded in the variable q inside
This is the to be deleted x
Then we let the next domain p
directly across the q
Then to the next node of q
Then put the node x out
Then we free (q)
and complete the delete operation
We look at the algorithm itself
This algorithm
also is based on the positioning of subscript position
We also want to set
Currently pending delete subscript i
and its precursor
I firstly found this precursor p
If p is illegal
Then I would return false
Otherwise, I'll continue to operate
I make this q equal to p->next
q is positioned our x
If q is the tail node
Then we let the tail pointer is equal to p
And let p->next refers to empty value
This is very important
We ensure that the entire list's
last node 's next field is empty
In our control of singly list
Some operations
are often be done through the last node
It points to an empty
to stop such a
traversal to a single list
Otherwise we let the p->next
to q's next node field
This q node
is stripped out
Then we delete q
and returns true
We look at a singly list operator
For nodes on top of a singly list
We are positioning it first
and then make the appropriate operation
This orientation process
are often started from head node
Then find orderly in it
This process requires a large O (n) time
Insert and delete itself
is actually very simple
Always use big O (1) time
to partial maintenance of these lists pointer
That's OK
But the overall cost of it
is still big O (n)
Doubly list is more easily to find
precursor
Of course, it also brings
some other troubles when doing Maintaining
That is when we insert or delete it
In addition to such a next field
I also need to maintain this prev field
We look at
the definition of the type of doubly list
In addition to this data field
We also point to the next node in the next field
and pointing to the prev precursor field
The other case is implemented similarly
We notice
the insertion process of doubly list
In doubly list
When I express this node
I only need to locate
the current node on the line
Because it is very convenient to find precursors
When inserting
I first navigate to p
Then I new a new node
This new node's
next field points p
Then it's prev point p itself
Then I go and
Maintain
other pointers of the list
I put the p's next field to p
The original p's next
For the precursor of it
We point q
Because that original next of p
has been inherited by q
So in fact it is the new node q
Its next field points to q itself
Deletion process is simpler
When we delete
we navigate to the current to be deleted this p
Then I put the prev precursor p
this node to its next field
point to p's next
Then the next node p
Prev field
Point to the p->prev
So
P is safely stripped out this doubly list
Then we put p node delete off
For circularly linked list
It link up head and tail
to it
If it is circular doubly list
Our tail of the next field pointing head
Then head prev field pointing to tail
The circularly linked list does not increase particular cost
Which allows us to do some arithmetic
more conveniently
We start from the circularly linked list's
any node
can reach other nodes
When I need to see some whole list
as a ring case
it will be very convenient
to have such a circularly linked list operations
But we have to pay attention
for the judgment condition of ending
you may use the methods of counting
Or when we encounter the virtual head node
you may need to end this loop
For processing of list
Because there exists a pointer
So in fact it is quite troublesome
We pay special attention not to
make illegal pointer operation
There are two types of situations that require special handling
The first is for some special nodes
For example, head or tail
We have to do the appropriate process
In particular cases of the tail of it
for this singly list
its last node
should be kept
Its next field is pointing to empty
So as to ensure
for lists
when doing such a traversal operation
it can be successfully finished
There is a circular list to pay attention to
For its tail next field
need to refer back to the first node
Then for processing the entire list
We should do a judgment on an empty list
And when we do insertion and deletion
Pay attention to modify the corresponding pointer
Makes the whole list
be able to maintain the correct logical structure
And when we do the pointer moves
we also need to be handled properly
Otherwise, we may fall into an infinite loop
For example, for list
traversal operation
I such a current node is the p
But inside the loop
You forgot to set the p = p->next
In this case it will form a dead loop
We finally left for everyone a question
For cases with and without header
what are the differences
In the previous lecture
We realized the situation with a header
Insert and Delete
You can implement
without header case
Insertion and deletion algorithms
You can look
In which case
It has more trouble
need to handle about the boundary conditions
In addition, when it is to deal with the list
In addition to
our previous summary
what mistakes do you often make
Summarize it
For List
We must be able to fully grasp
such a data structure
After mastering the list
We can handle a pointer operations
Then in some complex data structures
like tree, graph
When you're in the operating
it is not so easy to make some pointers mistakes
Thank you