Hello everyone. From this lecture we begin to learn
Chapter 2 of Data Structures and Algorithms, the linear list.
We will introduce the basic concepts of linear list
and the sequential list and linked list.
linear list is
a finite sequence
consisting of zero or more elements.
This element of it
may also be called a record or entry.
The linear elements' relative position
inside table
can also be called the subscript or index.
The number of the elements
is called the Length.
If the length is 0,
then the list is an empty one.
Linear list is such a data structure
that is simple,
easy for storage and computing.
For small-scale applications,
adopting linear list to achieve them
is very efficient.
We can see
there are some special elements
and some relationships between them
inside linear list.
We use two-tuples to express the linear list.
The node set of two-tuples is
the set of all elements of
the inear list.
And in fact,
it was the precursor / successor relationship.
If ai and ai +1 is directly adjacent,
then we called the ai ai +1's precursor ,
Ai and ai +1 called successor.
We are here referring to the direct precursor
and the direct successor
In this linear list inside
there is a special start node
It has no predecessor
Only a unique direct successor
There is an end node
which has no successor,
Only has a single precursor
What else are all internal nodes
These internal nodes
only have a direct precursor
and only a direct successor
This predecessor successor relationship
is anti-symmetric
This means that if ai is a precursor of ai +1
Then we can not say ai +1 is also a precursor of ai
It's the same with successor relationship
For transitive,
it is a broader view of
How we look at this precursor & successor relationship
That is to say
If ai is a precursor of aj
and aj is a precursor of ak
then we can say
ai is a precursor of ak
The head of the list
is the precursor of other elements throughout the linear list
The end of the list is the successor of all the elements
Linear structures have some characteristics
If we look at the
Common simple linear structure in RAM.
for each node
We can say
it is the same type of elements
Its elements length is the same
That means it has uniformity
In addition, it also has a orderliness nature
The elements inside list
all have a corresponding sequence
There is a sequence relationship between them logically
In the memory
We have to give a very good expression
for such relationship
In accordance with the linear list's complexity
some are divided into a class of simple linear list
that is what we'll introduce in the first few chapters
There are stacks and queues in linear list too
In addition
We will introduce the hash table later on
Hash table is an effective index structure
Supporting efficient retrieval operation
There are also advanced linear structure
based on the linear structure to do some expansion
such as generalized list multidimensional arrays, etc.
In accordance with access method
they are divided into three types
Direct access type
based on the subscripts
we will be able to directly find
Such a position of an element
The array is such a
form of direct access
Secondly
Sequential access type
in this list we need to
find the element
one by one by one
Such as list
which is sequential access type
Search Index type is
In order to accelerate the speed of retrieval
we do some effective index
such as,dictionary and hash table
which belong to the type of linear structure Index
In accordance with the operation, linear structures
can be divided into general linear list
and the stack (its operation and access are restricted in the same end )
and queues
its operation and access can be performed in different end.
Let's look at
Several factors of linear list
The first one is its logical structure
In this entire chapter of linear list
As what we discussed are all the linear structure
they all have the same logical structure
But we have to consider
the logical structure of the linear list
and what are the key attributes of it
Depending on the diverse storage ways
We can divide them into
several types of linear structures
Also, according to its different operations
they can also be divided into different linear structures
we can say that data structure
logical, storage and computing
these three elements
As long as one of these in data structure is different
We can see these data structure as different data structures
Firstly, let's look at the logical structure of the linear list
We have to consider
how many elements is there in a linear list
This consideration
relates to the store and manipulate
we do later
In addition
We need to consider the linear list's starting
and ending node
When doing some special operations
We need do some corresponding operations
in the header or tail
Another is the current position
for our operations
is likely to be associated
If I found the position of the element
Then in this position
I am going to carry out the appropriate operation
This time
we need to record the current position first
then proceeds to the next operation
OK
Depending on diverse storage structures
We divide linear list into
the sequential list
that is an array
and lists
these two types
Sequential list
is a very efficient storage structure
Its physical storage structure
expresses its associated logic relation
so we do not need additional storage fields
to express logical adjacent relationships
in this way we can very closly
store the related data
If the entire list
keep valid elements
then we can achieve storage density to 1
linked list needs pointer relationships
to express the logic sequence relationship
Therefore
it requires a pointer
an additional storage space
Its storage efficiency
is not as good as an sequential list
Linked Lists
include singly,doubly and circular linked list, etc.
Such special forms
according to operations
can be divided into without-any-restriction
common linear list
Besides, other structures that I can restrict insertion and deletion
carried out at the same end
This is the stack
The insertion and deletion of linear structure
at both ends
This is queue
Firstly, let's look at the stack
Stack limits the insertion and deletion
at the same end of the table
So
an element inserted first
will finally be able to come out
That means the last in but first out
This nature in our algorithm
such an depth-First-Search
has good application
As for queue, the insertion performed at one end of the list
and deletion is done at the other end
This creates a FIFO
nature
FIFO in width-First-search
also has a good application
For a data structure
We always tend to consider
how to build this structure
And how to destroy this structure
and to free
the corresponding memory space
Additionally for the entire inside structure
We can have add,delete,search and modify
such corresponding operationes
and sorting and retrieval
Those are the entire list's related operations
We will introduce those in later chapters
OK, now let' see
the realization of these operations of the linear list
Here
we write the relevant interfaces
For instance,Elements are added here
We can insert at the end of the list
also can
insert it at a designated location
And then in the corresponding position
Delet an element
For particularly important
We may need
given an element value
I find the relevant elements in a list inside
and then we do the insert delete, etc.
and other operations
and change the value of the elements in relative position
Please think
Which taxonomy do linear list have
In various taxonomy methods
what about the corresponding data structures
What are their differences and connections
In addition
There are various concepts of linear list
For example, the sequential list, linked list
stack, queues, etc.
What about these concepts
which one is associated with the storage structure
Which one has something related with the operation
Thank you