1 00:00:01,216 --> 00:00:04,116 Hello everyone. From this lecture we begin to learn 2 00:00:04,742 --> 00:00:07,577 Chapter 2 of Data Structures and Algorithms, the linear list. 3 00:00:08,009 --> 00:00:10,702 We will introduce the basic concepts of linear list 4 00:00:10,782 --> 00:00:13,241 and the sequential list and linked list. 5 00:00:15,546 --> 00:00:16,822 linear list is 6 00:00:16,910 --> 00:00:20,320 a finite sequence 7 00:00:20,399 --> 00:00:21,523 consisting of zero or more elements. 8 00:00:21,605 --> 00:00:22,910 This element of it 9 00:00:22,982 --> 00:00:26,222 may also be called a record or entry. 10 00:00:27,385 --> 00:00:31,446 The linear elements' relative position 11 00:00:31,517 --> 00:00:33,514 inside table 12 00:00:33,586 --> 00:00:37,437 can also be called the subscript or index. 13 00:00:38,314 --> 00:00:39,307 The number of the elements 14 00:00:39,379 --> 00:00:40,473 is called the Length. 15 00:00:41,065 --> 00:00:42,356 If the length is 0, 16 00:00:42,436 --> 00:00:43,390 then the list is an empty one. 17 00:00:43,964 --> 00:00:46,478 Linear list is such a data structure 18 00:00:47,119 --> 00:00:49,605 that is simple, 19 00:00:49,686 --> 00:00:50,847 easy for storage and computing. 20 00:00:50,927 --> 00:00:53,312 For small-scale applications, 21 00:00:53,992 --> 00:00:55,495 adopting linear list to achieve them 22 00:00:55,559 --> 00:00:57,142 is very efficient. 23 00:00:58,462 --> 00:00:59,858 We can see 24 00:00:59,946 --> 00:01:01,391 there are some special elements 25 00:01:01,463 --> 00:01:03,677 and some relationships between them 26 00:01:03,756 --> 00:01:05,956 inside linear list. 27 00:01:06,044 --> 00:01:10,641 We use two-tuples to express the linear list. 28 00:01:10,736 --> 00:01:13,128 The node set of two-tuples is 29 00:01:13,199 --> 00:01:15,667 the set of all elements of 30 00:01:15,747 --> 00:01:17,464 the inear list. 31 00:01:17,847 --> 00:01:19,461 And in fact, 32 00:01:20,036 --> 00:01:23,553 it was the precursor / successor relationship. 33 00:01:24,483 --> 00:01:28,889 If ai and ai +1 is directly adjacent, 34 00:01:28,940 --> 00:01:33,427 then we called the ai ai +1's precursor , 35 00:01:33,514 --> 00:01:37,432 Ai and ai +1 called successor. 36 00:01:37,504 --> 00:01:40,625 We are here referring to the direct precursor 37 00:01:40,705 --> 00:01:41,992 and the direct successor 38 00:01:42,968 --> 00:01:44,231 In this linear list inside 39 00:01:44,297 --> 00:01:47,294 there is a special start node 40 00:01:47,368 --> 00:01:49,447 It has no predecessor 41 00:01:49,520 --> 00:01:52,030 Only a unique direct successor 42 00:01:52,091 --> 00:01:54,092 There is an end node 43 00:01:54,172 --> 00:01:55,843 which has no successor, 44 00:01:55,919 --> 00:01:58,020 Only has a single precursor 45 00:01:58,097 --> 00:02:00,750 What else are all internal nodes 46 00:02:01,214 --> 00:02:02,387 These internal nodes 47 00:02:03,098 --> 00:02:06,372 only have a direct precursor 48 00:02:06,443 --> 00:02:08,805 and only a direct successor 49 00:02:09,434 --> 00:02:11,564 This predecessor successor relationship 50 00:02:11,636 --> 00:02:13,741 is anti-symmetric 51 00:02:14,254 --> 00:02:19,899 This means that if ai is a precursor of ai +1 52 00:02:20,658 --> 00:02:24,904 Then we can not say ai +1 is also a precursor of ai 53 00:02:25,401 --> 00:02:27,638 It's the same with successor relationship 54 00:02:28,659 --> 00:02:30,641 For transitive, 55 00:02:31,233 --> 00:02:34,031 it is a broader view of 56 00:02:34,086 --> 00:02:36,085 How we look at this precursor & successor relationship 57 00:02:36,671 --> 00:02:37,688 That is to say 58 00:02:37,769 --> 00:02:41,587 If ai is a precursor of aj 59 00:02:42,294 --> 00:02:44,216 and aj is a precursor of ak 60 00:02:44,678 --> 00:02:45,518 then we can say 61 00:02:45,614 --> 00:02:48,776 ai is a precursor of ak 62 00:02:48,864 --> 00:02:51,104 The head of the list 63 00:02:51,716 --> 00:02:55,936 is the precursor of other elements throughout the linear list 64 00:02:56,006 --> 00:03:01,051 The end of the list is the successor of all the elements 65 00:03:03,070 --> 00:03:06,042 Linear structures have some characteristics 66 00:03:06,122 --> 00:03:09,220 If we look at the 67 00:03:09,300 --> 00:03:11,728 Common simple linear structure in RAM. 68 00:03:12,377 --> 00:03:13,833 for each node 69 00:03:13,904 --> 00:03:15,273 We can say 70 00:03:15,361 --> 00:03:18,552 it is the same type of elements 71 00:03:19,416 --> 00:03:22,839 Its elements length is the same 72 00:03:22,919 --> 00:03:25,111 That means it has uniformity 73 00:03:25,687 --> 00:03:28,596 In addition, it also has a orderliness nature 74 00:03:28,676 --> 00:03:30,684 The elements inside list 75 00:03:30,756 --> 00:03:33,234 all have a corresponding sequence 76 00:03:33,818 --> 00:03:35,951 There is a sequence relationship between them logically 77 00:03:36,023 --> 00:03:37,185 In the memory 78 00:03:37,283 --> 00:03:38,840 We have to give a very good expression 79 00:03:38,912 --> 00:03:40,124 for such relationship 80 00:03:41,756 --> 00:03:44,975 In accordance with the linear list's complexity 81 00:03:45,047 --> 00:03:47,873 some are divided into a class of simple linear list 82 00:03:47,956 --> 00:03:50,487 that is what we'll introduce in the first few chapters 83 00:03:50,568 --> 00:03:53,674 There are stacks and queues in linear list too 84 00:03:54,273 --> 00:03:55,138 In addition 85 00:03:55,234 --> 00:03:58,439 We will introduce the hash table later on 86 00:03:58,519 --> 00:04:02,728 Hash table is an effective index structure 87 00:04:02,815 --> 00:04:04,988 Supporting efficient retrieval operation 88 00:04:05,669 --> 00:04:08,749 There are also advanced linear structure 89 00:04:08,828 --> 00:04:11,999 based on the linear structure to do some expansion 90 00:04:12,094 --> 00:04:14,925 such as generalized list multidimensional arrays, etc. 91 00:04:15,980 --> 00:04:17,509 In accordance with access method 92 00:04:17,605 --> 00:04:19,191 they are divided into three types 93 00:04:19,287 --> 00:04:20,888 Direct access type 94 00:04:20,960 --> 00:04:23,586 based on the subscripts 95 00:04:23,666 --> 00:04:26,351 we will be able to directly find 96 00:04:26,415 --> 00:04:28,342 Such a position of an element 97 00:04:29,200 --> 00:04:32,262 The array is such a 98 00:04:32,326 --> 00:04:33,788 form of direct access 99 00:04:34,388 --> 00:04:35,045 Secondly 100 00:04:35,124 --> 00:04:36,523 Sequential access type 101 00:04:36,610 --> 00:04:39,178 in this list we need to 102 00:04:39,267 --> 00:04:41,107 find the element 103 00:04:41,179 --> 00:04:42,689 one by one by one 104 00:04:43,053 --> 00:04:44,898 Such as list 105 00:04:44,986 --> 00:04:46,082 which is sequential access type 106 00:04:46,514 --> 00:04:47,497 Search Index type is 107 00:04:47,569 --> 00:04:50,230 In order to accelerate the speed of retrieval 108 00:04:50,326 --> 00:04:52,784 we do some effective index 109 00:04:53,382 --> 00:04:55,000 such as,dictionary and hash table 110 00:04:55,080 --> 00:04:57,853 which belong to the type of linear structure Index 111 00:04:58,748 --> 00:05:01,708 In accordance with the operation, linear structures 112 00:05:01,798 --> 00:05:04,608 can be divided into general linear list 113 00:05:04,688 --> 00:05:08,889 and the stack (its operation and access are restricted in the same end ) 114 00:05:08,961 --> 00:05:11,937 and queues 115 00:05:12,008 --> 00:05:13,264 its operation and access can be performed in different end. 116 00:05:13,840 --> 00:05:14,849 Let's look at 117 00:05:14,929 --> 00:05:17,650 Several factors of linear list 118 00:05:18,146 --> 00:05:20,911 The first one is its logical structure 119 00:05:21,407 --> 00:05:24,364 In this entire chapter of linear list 120 00:05:24,436 --> 00:05:26,931 As what we discussed are all the linear structure 121 00:05:27,011 --> 00:05:29,650 they all have the same logical structure 122 00:05:29,738 --> 00:05:31,132 But we have to consider 123 00:05:31,204 --> 00:05:33,796 the logical structure of the linear list 124 00:05:33,877 --> 00:05:35,712 and what are the key attributes of it 125 00:05:36,143 --> 00:05:39,984 Depending on the diverse storage ways 126 00:05:40,060 --> 00:05:41,682 We can divide them into 127 00:05:42,321 --> 00:05:44,551 several types of linear structures 128 00:05:44,633 --> 00:05:47,408 Also, according to its different operations 129 00:05:47,513 --> 00:05:50,194 they can also be divided into different linear structures 130 00:05:51,503 --> 00:05:53,756 we can say that data structure 131 00:05:54,382 --> 00:05:56,320 logical, storage and computing 132 00:05:56,404 --> 00:05:57,608 these three elements 133 00:05:57,696 --> 00:06:00,065 As long as one of these in data structure is different 134 00:06:00,500 --> 00:06:03,309 We can see these data structure as different data structures 135 00:06:04,679 --> 00:06:07,592 Firstly, let's look at the logical structure of the linear list 136 00:06:08,352 --> 00:06:09,672 We have to consider 137 00:06:09,744 --> 00:06:12,393 how many elements is there in a linear list 138 00:06:12,778 --> 00:06:13,817 This consideration 139 00:06:13,889 --> 00:06:16,497 relates to the store and manipulate 140 00:06:16,577 --> 00:06:18,409 we do later 141 00:06:19,105 --> 00:06:19,881 In addition 142 00:06:19,969 --> 00:06:25,312 We need to consider the linear list's starting 143 00:06:25,400 --> 00:06:27,455 and ending node 144 00:06:27,529 --> 00:06:29,980 When doing some special operations 145 00:06:30,068 --> 00:06:33,737 We need do some corresponding operations 146 00:06:33,825 --> 00:06:35,005 in the header or tail 147 00:06:36,801 --> 00:06:38,606 Another is the current position 148 00:06:39,341 --> 00:06:40,604 for our operations 149 00:06:40,692 --> 00:06:42,635 is likely to be associated 150 00:06:43,123 --> 00:06:46,070 If I found the position of the element 151 00:06:46,142 --> 00:06:47,855 Then in this position 152 00:06:47,943 --> 00:06:49,969 I am going to carry out the appropriate operation 153 00:06:50,049 --> 00:06:51,463 This time 154 00:06:51,551 --> 00:06:54,035 we need to record the current position first 155 00:06:54,116 --> 00:06:55,980 then proceeds to the next operation 156 00:06:58,094 --> 00:06:59,835 OK 157 00:06:59,915 --> 00:07:02,185 Depending on diverse storage structures 158 00:07:02,271 --> 00:07:04,531 We divide linear list into 159 00:07:04,599 --> 00:07:06,412 the sequential list 160 00:07:06,492 --> 00:07:07,961 that is an array 161 00:07:08,049 --> 00:07:09,512 and lists 162 00:07:09,592 --> 00:07:11,076 these two types 163 00:07:13,493 --> 00:07:14,509 Sequential list 164 00:07:14,597 --> 00:07:17,715 is a very efficient storage structure 165 00:07:18,546 --> 00:07:23,191 Its physical storage structure 166 00:07:23,270 --> 00:07:26,689 expresses its associated logic relation 167 00:07:28,162 --> 00:07:32,765 so we do not need additional storage fields 168 00:07:32,846 --> 00:07:36,455 to express logical adjacent relationships 169 00:07:36,879 --> 00:07:40,624 in this way we can very closly 170 00:07:40,719 --> 00:07:43,436 store the related data 171 00:07:43,916 --> 00:07:46,663 If the entire list 172 00:07:46,747 --> 00:07:48,451 keep valid elements 173 00:07:48,532 --> 00:07:50,723 then we can achieve storage density to 1 174 00:07:51,322 --> 00:07:57,338 linked list needs pointer relationships 175 00:07:57,426 --> 00:08:02,271 to express the logic sequence relationship 176 00:08:03,289 --> 00:08:04,290 Therefore 177 00:08:04,378 --> 00:08:06,824 it requires a pointer 178 00:08:06,899 --> 00:08:08,469 an additional storage space 179 00:08:09,172 --> 00:08:11,690 Its storage efficiency 180 00:08:11,761 --> 00:08:13,604 is not as good as an sequential list 181 00:08:14,626 --> 00:08:15,338 Linked Lists 182 00:08:15,434 --> 00:08:18,027 include singly,doubly and circular linked list, etc. 183 00:08:18,457 --> 00:08:19,713 Such special forms 184 00:08:21,786 --> 00:08:23,082 according to operations 185 00:08:23,186 --> 00:08:27,014 can be divided into without-any-restriction 186 00:08:27,089 --> 00:08:28,704 common linear list 187 00:08:28,783 --> 00:08:33,034 Besides, other structures that I can restrict insertion and deletion 188 00:08:33,105 --> 00:08:35,362 carried out at the same end 189 00:08:35,450 --> 00:08:36,343 This is the stack 190 00:08:36,422 --> 00:08:39,788 The insertion and deletion of linear structure 191 00:08:39,869 --> 00:08:41,139 at both ends 192 00:08:41,227 --> 00:08:42,233 This is queue 193 00:08:43,112 --> 00:08:45,409 Firstly, let's look at the stack 194 00:08:46,094 --> 00:08:49,258 Stack limits the insertion and deletion 195 00:08:49,329 --> 00:08:51,305 at the same end of the table 196 00:08:52,097 --> 00:08:53,060 So 197 00:08:53,165 --> 00:08:56,356 an element inserted first 198 00:08:56,451 --> 00:08:58,817 will finally be able to come out 199 00:08:58,913 --> 00:09:01,930 That means the last in but first out 200 00:09:02,591 --> 00:09:06,043 This nature in our algorithm 201 00:09:06,127 --> 00:09:07,312 such an depth-First-Search 202 00:09:07,398 --> 00:09:08,672 has good application 203 00:09:10,213 --> 00:09:13,599 As for queue, the insertion performed at one end of the list 204 00:09:13,679 --> 00:09:16,113 and deletion is done at the other end 205 00:09:17,154 --> 00:09:20,924 This creates a FIFO 206 00:09:20,996 --> 00:09:22,353 nature 207 00:09:23,121 --> 00:09:25,588 FIFO in width-First-search 208 00:09:25,669 --> 00:09:27,153 also has a good application 209 00:09:29,747 --> 00:09:31,067 For a data structure 210 00:09:31,149 --> 00:09:32,755 We always tend to consider 211 00:09:33,131 --> 00:09:34,504 how to build this structure 212 00:09:34,593 --> 00:09:36,893 And how to destroy this structure 213 00:09:36,980 --> 00:09:39,890 and to free 214 00:09:39,979 --> 00:09:41,202 the corresponding memory space 215 00:09:41,290 --> 00:09:43,876 Additionally for the entire inside structure 216 00:09:43,971 --> 00:09:46,985 We can have add,delete,search and modify 217 00:09:47,081 --> 00:09:48,591 such corresponding operationes 218 00:09:49,762 --> 00:09:52,259 and sorting and retrieval 219 00:09:52,714 --> 00:09:56,112 Those are the entire list's related operations 220 00:09:56,215 --> 00:09:58,677 We will introduce those in later chapters 221 00:09:58,766 --> 00:09:59,949 OK, now let' see 222 00:10:00,366 --> 00:10:03,845 the realization of these operations of the linear list 223 00:10:03,933 --> 00:10:05,413 Here 224 00:10:05,501 --> 00:10:08,234 we write the relevant interfaces 225 00:10:08,322 --> 00:10:11,205 For instance,Elements are added here 226 00:10:11,293 --> 00:10:14,603 We can insert at the end of the list 227 00:10:14,691 --> 00:10:16,791 also can 228 00:10:16,868 --> 00:10:18,237 insert it at a designated location 229 00:10:18,673 --> 00:10:22,239 And then in the corresponding position 230 00:10:22,303 --> 00:10:23,861 Delet an element 231 00:10:24,352 --> 00:10:25,378 For particularly important 232 00:10:25,471 --> 00:10:27,952 We may need 233 00:10:28,031 --> 00:10:29,691 given an element value 234 00:10:29,771 --> 00:10:32,306 I find the relevant elements in a list inside 235 00:10:32,394 --> 00:10:35,668 and then we do the insert delete, etc. 236 00:10:35,756 --> 00:10:36,578 and other operations 237 00:10:36,674 --> 00:10:41,779 and change the value of the elements in relative position 238 00:10:42,867 --> 00:10:44,791 Please think 239 00:10:45,433 --> 00:10:47,854 Which taxonomy do linear list have 240 00:10:47,942 --> 00:10:50,022 In various taxonomy methods 241 00:10:50,755 --> 00:10:52,627 what about the corresponding data structures 242 00:10:52,698 --> 00:10:54,871 What are their differences and connections 243 00:10:55,527 --> 00:10:56,461 In addition 244 00:10:57,220 --> 00:10:59,274 There are various concepts of linear list 245 00:10:59,357 --> 00:11:02,385 For example, the sequential list, linked list 246 00:11:03,058 --> 00:11:04,569 stack, queues, etc. 247 00:11:06,078 --> 00:11:08,425 What about these concepts 248 00:11:08,511 --> 00:11:11,780 which one is associated with the storage structure 249 00:11:11,860 --> 00:11:13,948 Which one has something related with the operation 250 00:11:14,028 --> 00:11:15,004 Thank you