1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
 100
 101
 102
 103
 104
 105
 106
 107
 108
 109
 110
 111
 112
 113
 114
 115
 116
 117
 118
 119
 120
 121
 122
 123
 124
 125
 126
 127
 128
 129
 130
 131
 132
 133
 134
 135
 136
 137
 138
 139
 140
 141
 142
 143
 144
 145
 146
 147
 148
 149
 150
 151
 152
 153
 154
 155
 156
 157
 158
 159
 160
 161
 162
 163
 164
 165
 166
 167
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227
 228
 229
 230
 231
 232
 233
 234
 235
 236
 237
 238
 239
 240
 241
 242
 243
 244
 245
 246
 247
 248
 249
 250
 251
 252
 253
 254
 255
 256
 257
 258
 259
 260
 261
 262
 263
 264
 265
 266
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285
 286
 287
 288
 289
 290
 291
 292
 293
 294
 295
 296
 297
 298
 299
 300
 301
 302
 303
 304
 305
 306
 307
 308
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323
 324
 325
 326
 327
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338
 339
 340
 341
 342
 343
 344
 345
 346
 347
 348
 349
 350
 351
 352
 353
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395
 396
 397
 398
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437
 438
 439
 440
 441
 442
 443
 444
 445
 446
 447
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521
 522
 523
 524
 525
 526
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537
 538
 539
 540
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567
 568
 569
 570
 571
 572
 573
 574
 575
 576
 577
 578
 579
 580
 581
 582
 583
 584
 585
 586
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624
 625
 626
 627
 628
 629
 630
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1
00:00:00,000 --> 00:00:03,381
>> [MUSIC nagpe-play]

2
00:00:03,381 --> 00:00:04,604

3
00:00:04,604 --> 00:00:05,520
DOUG LLOYD: Lahat ng karapatan.

4
00:00:05,520 --> 00:00:07,860
Kaya't kung ikaw lang tapos na
video sa isa-isa-link listahan ng paumanhin

5
00:00:07,860 --> 00:00:09,568
Iniwan ko sa iyo off sa isang
piraso ng isang cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Ngunit Natutuwa akong nandito ka upang matapos
ang kuwento ng doble-link list.

7
00:00:12,790 --> 00:00:15,250
>> Kaya kung ang pagpapabalik sa iyo mula sa
video na, usapan natin

8
00:00:15,250 --> 00:00:18,500
tungkol sa kung paano isa-isa na naka-link
mga listahan ng gagawin dumalo sa aming kakayahan

9
00:00:18,500 --> 00:00:22,090
sa pakikitungo sa mga impormasyon
kung saan ang bilang ng mga elemento

10
00:00:22,090 --> 00:00:24,442
o ang bilang ng mga item sa
isang listahan ay maaaring lumaki o pag-urong.

11
00:00:24,442 --> 00:00:26,400
Maaari naming ngayon makikitungo sa
isang bagay tulad na, kung saan

12
00:00:26,400 --> 00:00:28,310
hindi namin ma haharapin ang mga ito sa array.

13
00:00:28,310 --> 00:00:30,560
>> Subalit sila magtiis sa isa
kritikal na limitasyon na

14
00:00:30,560 --> 00:00:33,790
ay na may isang isa-isa na naka-link
listahan, maaari naming lamang kailanman ilipat

15
00:00:33,790 --> 00:00:36,200
sa isang solong direksyon sa pamamagitan ng mga listahan.

16
00:00:36,200 --> 00:00:39,010
At ang tanging tunay na sitwasyon
saan na maaaring maging isang problema

17
00:00:39,010 --> 00:00:41,250
ay kapag kami ay nagsisikap na
tanggalin ang isang elemento.

18
00:00:41,250 --> 00:00:46,000
At hindi namin kahit na pag-usapan kung paano ito gawin
sa isang isa-isa-link na listahan sa pseudocode.

19
00:00:46,000 --> 00:00:48,797
Ito ay tiyak na maaaring gawin, ngunit
maaaring ito ay isang bit ng isang problema.

20
00:00:48,797 --> 00:00:50,630
Kaya kung nakita mo ang iyong sarili
sa isang sitwasyon na kung saan ang

21
00:00:50,630 --> 00:00:53,175
sinusubukan mong tanggalin ang
single elemento mula sa listahan

22
00:00:53,175 --> 00:00:55,430
o ito ay pagpunta sa kinakailangan
na kayo ay pagbubura

23
00:00:55,430 --> 00:00:57,970
single elemento mula sa
listahan, maaari mong isaalang

24
00:00:57,970 --> 00:01:02,090
isaalang-alang ang paggamit ng isang doble-link
ilista sa halip ng isang isa-isa-link na listahan.

25
00:01:02,090 --> 00:01:06,320
Dahil magpapahintulot sa inyo doble-link na listahan
upang ilipat ang parehong pasulong at pabalik

26
00:01:06,320 --> 00:01:09,340
sa pamamagitan ng mga listahan sa halip ng
lamang pasulong sa pamamagitan ng list--

27
00:01:09,340 --> 00:01:13,950
sa pamamagitan lamang ng pagdaragdag ng isa dagdag na elemento
sa aming mga kahulugan ng istraktura

28
00:01:13,950 --> 00:01:16,690
para sa mga doble-link listahan node.

29
00:01:16,690 --> 00:01:19,770
>> Muli, kung hindi ka pagpunta sa
ay pagtanggal single elemento

30
00:01:19,770 --> 00:01:24,810
mula sa list-- dahil kami ay nagdadagdag ng
ng dagdag na field sa aming istraktura

31
00:01:24,810 --> 00:01:28,340
kahulugan, ang nodes sa kanilang sarili
para sa doble-link na listahan

32
00:01:28,340 --> 00:01:29,550
ay magiging mas malaki.

33
00:01:29,550 --> 00:01:31,600
Sila ay pagpunta sa tumagal
up pa bytes ng memorya.

34
00:01:31,600 --> 00:01:34,160
At kaya kung hindi ito ay isang bagay
ikaw ay pagpunta sa kailangan upang gawin,

35
00:01:34,160 --> 00:01:36,300
maaari kang magpasya ito ay
Hindi karapat-dapat ang off kalakalan

36
00:01:36,300 --> 00:01:39,360
na magkaroon ng gastusin sa dagdag na
bytes ng memory kinakailangan

37
00:01:39,360 --> 00:01:43,940
para sa isang doble-link na listahan kung hindi ka
pagpunta sa pagtanggal ng nag-iisang sangkap.

38
00:01:43,940 --> 00:01:46,760
Ngunit ang mga ito rin ay cool na
para sa masyadong iba pang mga bagay.

39
00:01:46,760 --> 00:01:51,260
>> Kaya tulad ng sinabi ko, kami na lang si
isang single field sa aming istraktura

40
00:01:51,260 --> 00:01:55,360
definition-- ito paniwala
ng isang Previous pointer.

41
00:01:55,360 --> 00:01:58,620
Kaya sa isang isa-isa-link na listahan, kami
may halaga at ang Next pointer,

42
00:01:58,620 --> 00:02:02,850
kaya ang doble-link na listahan lamang ay
isang paraan upang ilipat paurong rin.

43
00:02:02,850 --> 00:02:04,960
>> Ngayon sa isa-isa na naka-link
listahan ng video, usapan natin

44
00:02:04,960 --> 00:02:07,210
tungkol sa mga ito ay limang ng
pangunahing bagay na kailangan mo upang maging

45
00:02:07,210 --> 00:02:09,449
magawa sa trabaho na may mga listahan ng link.

46
00:02:09,449 --> 00:02:12,880
At para sa karamihan sa mga ito, ang katunayan
na ito ay isang doble-link na listahan

47
00:02:12,880 --> 00:02:14,130
ay hindi tunay na isang malaking jump.

48
00:02:14,130 --> 00:02:17,936
Maaari pa rin kami sa paghahanap sa pamamagitan lamang sa pamamagitan ng
paglipat ng pasulong mula simula hanggang katapusan.

49
00:02:17,936 --> 00:02:20,810
Maaari pa rin naming lumikha ng isang node sa labas ng
manipis na hangin, medyo marami sa parehong paraan.

50
00:02:20,810 --> 00:02:23,591
Maaari naming tanggalin ang mga listahan pretty
marami sa parehong paraan masyadong.

51
00:02:23,591 --> 00:02:25,340
Ang tanging bagay na
ay subtly naiiba,

52
00:02:25,340 --> 00:02:28,970
talaga, ay pagpasok
bagong nodes sa listahan,

53
00:02:28,970 --> 00:02:33,722
at kami ay sa wakas makipag-usap tungkol sa pagtanggal
isang solong elemento mula sa listahan pati na rin.

54
00:02:33,722 --> 00:02:35,430
Muli, medyo marami
ang iba pang mga tatlong, hindi namin

55
00:02:35,430 --> 00:02:37,888
hindi pagpunta sa makipag-usap tungkol sa mga ito
sa ngayon dahil hindi lang nila

56
00:02:37,888 --> 00:02:43,920
very minor tweak sa mga ideya na tinalakay
sa isa-isa-link na listahan ng video.

57
00:02:43,920 --> 00:02:46,292
>> Kaya hayaan ipasok ang isang bagong node
sa isang doble-link na listahan.

58
00:02:46,292 --> 00:02:48,750
Usapan natin ang tungkol sa paggawa nito para sa
isa-isa-link listahan pati na rin,

59
00:02:48,750 --> 00:02:52,020
ngunit may isang pares ng mga dagdag
nakakakuha sa doble-link list.

60
00:02:52,020 --> 00:02:55,280
Humihingi kami [? pagpasa?] sa ulo ng
listahan dito at ilang di-makatwirang halaga,

61
00:02:55,280 --> 00:02:58,600
at gusto naming makuha ang bagong ulo
ng listahan ng mga function na ito.

62
00:02:58,600 --> 00:03:01,414
Iyon ang dahilan kung bakit ito ay nagbabalik ng isang dllnode star.

63
00:03:01,414 --> 00:03:02,330
Kaya ano ang mga hakbang na ito?

64
00:03:02,330 --> 00:03:04,496
Ang mga ito ay, muli, halos katulad
upang isa-isa-listahan ng link

65
00:03:04,496 --> 00:03:05,670
may isang extrang karagdagan.

66
00:03:05,670 --> 00:03:08,900
Gusto naming naglalaan space para sa isang bagong
node at suriin upang tiyakin na ito ay may-bisa.

67
00:03:08,900 --> 00:03:11,510
Gusto naming punan na node up
sa kahit anong impormasyon ang aming

68
00:03:11,510 --> 00:03:12,564
gusto mong ilagay sa mga ito.

69
00:03:12,564 --> 00:03:15,480
Ang huling bagay na kailangan namin upang do-- ang
dagdag na bagay na kailangan naming gawin, rather--

70
00:03:15,480 --> 00:03:19,435
ay upang ayusin ang Previous pointer
ng lumang ulo ng listahan.

71
00:03:19,435 --> 00:03:21,310
Tandaan na dahil
ng doble-link na listahan,

72
00:03:21,310 --> 00:03:23,110
maaari naming sumulong
at backwards-- saan

73
00:03:23,110 --> 00:03:27,080
ay nangangahulugan na ang bawat node aktwal na tumuturo
sa dalawang iba pang mga nodes sa halip na isa lamang.

74
00:03:27,080 --> 00:03:29,110
At kaya kailangan namin upang ayusin
ang lumang ulo ng listahan

75
00:03:29,110 --> 00:03:32,151
upang ituro paatras na ang bagong pinuno ng
ang listahan ng mga link, na kung saan ay isang bagay na

76
00:03:32,151 --> 00:03:33,990
hindi namin ay may sa gawin bago.

77
00:03:33,990 --> 00:03:37,420
At tulad ng dati, bumalik kami lamang ng isang
pointer sa bagong ulo ng listahan.

78
00:03:37,420 --> 00:03:38,220
>> Kaya narito ang isang listahan.

79
00:03:38,220 --> 00:03:40,144
Gusto naming ipasok 12 sa listahan na ito.

80
00:03:40,144 --> 00:03:42,060
Abiso na ang mga diagram
ay bahagyang naiiba.

81
00:03:42,060 --> 00:03:47,710
Ang bawat node ay naglalaman ng tatlong fields--
data, at isang Next pointer sa pula,

82
00:03:47,710 --> 00:03:50,170
at isang Previous pointer sa asul.

83
00:03:50,170 --> 00:03:54,059
Walang dumating bago ang 15 node,
kaya nito Nakaraan pointer ay null.

84
00:03:54,059 --> 00:03:55,350
Ito ang simula ng listahan.

85
00:03:55,350 --> 00:03:56,560
May walang bago ito.

86
00:03:56,560 --> 00:04:03,350
At walang dumating pagkatapos ng 10 node, at
kaya Susunod pointer ay null rin.

87
00:04:03,350 --> 00:04:05,616
>> Kaya sabihin magdagdag ng 12 sa listahan na ito.

88
00:04:05,616 --> 00:04:08,070
Kailangan namin [hindi marinig] space para sa mga node.

89
00:04:08,070 --> 00:04:11,480
Inilalagay namin ang 12 sa loob ng mga ito.

90
00:04:11,480 --> 00:04:14,840
At pagkatapos ay muli, kailangan namin upang maging tunay
maingat na hindi masira ang kadena.

91
00:04:14,840 --> 00:04:17,144
Gusto naming muling ayusin ang mga
mga payo sa tamang pagkakasunod-sunod.

92
00:04:17,144 --> 00:04:19,519
At kung minsan na baka mean--
dahil kakailanganin namin makita lalo

93
00:04:19,519 --> 00:04:24,120
may delete-- na mayroon kaming ilang mga
kalabisan ng mga payo, ngunit iyan ay OK.

94
00:04:24,120 --> 00:04:25,750
>> Kaya kung ano ang gusto naming gawin ang unang?

95
00:04:25,750 --> 00:04:28,290
Gusto ko inirerekomenda ang
mga bagay na dapat mong malamang

96
00:04:28,290 --> 00:04:35,350
gawin ay upang punan ang mga payo ng 12
node bago mo pindutin ang kahit sinong tao.

97
00:04:35,350 --> 00:04:38,640
Kaya kung ano ang 12 pagpunta upang tumuro sa susunod?

98
00:04:38,640 --> 00:04:39,860
15.

99
00:04:39,860 --> 00:04:42,430
Ano ang dumating bago 12?

100
00:04:42,430 --> 00:04:43,640
Wala.

101
00:04:43,640 --> 00:04:46,280
Ngayon na napuno natin ang
dagdag na impormasyon sa loob ng 12

102
00:04:46,280 --> 00:04:49,320
kaya ito ay may Nakaraang, Susunod, at halaga.

103
00:04:49,320 --> 00:04:53,505
>> Ngayon ay maaari naming magkaroon 15-- ito ng dagdag na
step uusap kami about-- namin

104
00:04:53,505 --> 00:04:56,590
ay maaaring magkaroon ng 15 point bumalik sa 12.

105
00:04:56,590 --> 00:04:59,634
At ngayon maaari naming ilipat ang mga pinuno ng
ang listahan ng mga link upang maging 12 din.

106
00:04:59,634 --> 00:05:02,550
Kaya ito ay medyo kapareho sa kung ano ang aming
ginagawa sa isa-isa na naka-link na listahan,

107
00:05:02,550 --> 00:05:06,940
maliban para sa mga dagdag na hakbang ng
pagkonekta sa lumang ulo ng listahan

108
00:05:06,940 --> 00:05:09,810
i-back sa bagong ulo ng listahan.

109
00:05:09,810 --> 00:05:12,170
>> Ngayon sabihin sa wakas tanggalin
isang node mula sa isang listahan ng mga link.

110
00:05:12,170 --> 00:05:14,350
Kaya sabihin nating mayroon kaming
sa ilang ibang mga pag-andar na

111
00:05:14,350 --> 00:05:18,080
ay paghahanap ng isang node gusto naming tanggalin
at binigyan niya tayo ng isang pointer sa eksakto

112
00:05:18,080 --> 00:05:19,710
node na gusto naming tanggalin.

113
00:05:19,710 --> 00:05:22,360
Hindi namin kahit na need-- sabihin ang
ulo ay pa rin globally ipinahayag.

114
00:05:22,360 --> 00:05:23,590
Hindi natin kailangan ang ulo dito.

115
00:05:23,590 --> 00:05:26,830
Lahat ng mga function na ito ay ginagawa ay hindi namin
Natagpuan ang isang pointer sa eksakto ang node namin

116
00:05:26,830 --> 00:05:28,090
nais na makakuha ng alisan ng.

117
00:05:28,090 --> 00:05:28,940
Sabihin makakuha ng alisan ng ito.

118
00:05:28,940 --> 00:05:31,859
Ito ay isang pulutong mas madali sa
doble-link list.

119
00:05:31,859 --> 00:05:33,650
First-- ito ay aktwal na
lamang ng ilang mga bagay.

120
00:05:33,650 --> 00:05:38,760
Kailangan lang namin upang ayusin ang mga nakapalibot
payo nodes 'upang laktawan ang mga ito sa paglipas ng

121
00:05:38,760 --> 00:05:40,240
node gusto naming tanggalin.

122
00:05:40,240 --> 00:05:43,484
At pagkatapos ay maaari naming tanggalin na node.

123
00:05:43,484 --> 00:05:45,150
Kaya muli, lang kami ng pagpunta sa pamamagitan dito.

124
00:05:45,150 --> 00:05:49,625
Malas Kami ay nagpasya na
gusto naming tanggalin ang mga node X.

125
00:05:49,625 --> 00:05:51,500
At muli, kung ano Ako
ginagawa here-- ng way--

126
00:05:51,500 --> 00:05:54,580
ito ay isang pangkalahatang kaso para sa isang
node na nasa gitna.

127
00:05:54,580 --> 00:05:56,547
Mayroong isang pares ng mga
dagdag caveats na kayo

128
00:05:56,547 --> 00:05:59,380
kailangan mong isaalang-alang kapag nagtatanggal ka
sa tunay simula ng listahan

129
00:05:59,380 --> 00:06:01,040
o sa dulo ng listahan.

130
00:06:01,040 --> 00:06:03,730
May isang pares ng mga espesyal na
kaso sulok sa pakikitungo sa doon.

131
00:06:03,730 --> 00:06:07,960
>> Kaya ito ay gumagana para sa pagtanggal ng anumang node
sa gitna ng isa list-- na

132
00:06:07,960 --> 00:06:11,550
ay isang lehitimong pointer forward
at isang lehitimong pointer paatras,

133
00:06:11,550 --> 00:06:14,460
lehitimong Nakaraang at susunod na pointer.

134
00:06:14,460 --> 00:06:16,530
Muli, kung ikaw ay nagtatrabaho
sa dulo, ikaw

135
00:06:16,530 --> 00:06:18,500
kailangan upang pangasiwaan ang mga
bahagyang naiiba,

136
00:06:18,500 --> 00:06:19,570
at hindi namin ang pagpunta sa
makipag-usap tungkol sa na ngayon.

137
00:06:19,570 --> 00:06:21,319
Ngunit maaari mong malamang
malaman kung ano ang mga kailangan

138
00:06:21,319 --> 00:06:24,610
upang gawin lamang sa pamamagitan ng panonood ng video na ito.

139
00:06:24,610 --> 00:06:28,910
>> Kaya ko na ihiwalay namin X. X ay ang node
gusto naming tanggalin mula sa listahan.

140
00:06:28,910 --> 00:06:30,140
Ano ang gagawin namin?

141
00:06:30,140 --> 00:06:32,800
Una, kailangan namin upang muling ayusin
labas mga payo.

142
00:06:32,800 --> 00:06:35,815
Kailangan namin upang muling ayusin
9 sa tabi ng laktawan higit sa 13

143
00:06:35,815 --> 00:06:38,030
at punto sa 10-- saan
ay kung ano lang ginawa namin.

144
00:06:38,030 --> 00:06:41,180
At kailangan din namin na
muling ayusin ang 10 ni Nakaraan

145
00:06:41,180 --> 00:06:44,610
upang tumuro sa 9 sa halip na tumuturo sa 13.

146
00:06:44,610 --> 00:06:46,490
>> Kaya muli, ito ay ang
diagram upang magsimula sa.

147
00:06:46,490 --> 00:06:47,730
Ito ay ang aming chain.

148
00:06:47,730 --> 00:06:51,027
Kailangan namin upang laktawan ang higit sa 13,
ngunit kailangan namin upang mapanatili rin

149
00:06:51,027 --> 00:06:52,110
ang integridad ng mga listahan.

150
00:06:52,110 --> 00:06:54,680
Hindi namin nais na mawala ang anumang
impormasyon sa alinmang direksyon.

151
00:06:54,680 --> 00:06:59,620
Kaya kailangan namin upang muling ayusin
ang mga payo nang mabuti

152
00:06:59,620 --> 00:07:02,240
kaya hindi namin basagin ang kadena sa lahat.

153
00:07:02,240 --> 00:07:05,710
>> Kaya maaari naming sabihin 9 ni Next pointer
puntos sa parehong lugar

154
00:07:05,710 --> 00:07:08,040
na Next labintatlo ni
pointer points ngayon.

155
00:07:08,040 --> 00:07:10,331
Dahil kami sa huli
pagpunta sa nais upang laktawan ang higit sa 13.

156
00:07:10,331 --> 00:07:13,750
Kaya kahit saan 13 puntos susunod, ikaw
gusto siyam upang ituro doon sa halip.

157
00:07:13,750 --> 00:07:15,200
Kaya iyon na.

158
00:07:15,200 --> 00:07:20,370
At pagkatapos ay kung saan 13 puntos pabalik
sa, anumang dumating bago 13,

159
00:07:20,370 --> 00:07:24,800
Gusto namin ng 10 upang ituro
na na sa halip ng 13.

160
00:07:24,800 --> 00:07:29,290
Ngayon pansinin, kung susundin mo
ang mga arrow, maaari naming i-drop 13

161
00:07:29,290 --> 00:07:32,380
walang tunay na pagkawala ng anumang impormasyon.

162
00:07:32,380 --> 00:07:36,002
Iningatan namin ang integridad ng mga listahan,
paglipat ng parehong pasulong at paatras.

163
00:07:36,002 --> 00:07:38,210
At pagkatapos ay maaari naming uri lamang
ng malinis na ito ng isang maliit na piraso

164
00:07:38,210 --> 00:07:40,930
sa pamamagitan ng paghila sa listahan ng sama-sama.

165
00:07:40,930 --> 00:07:43,270
Kaya rearranged namin ang
mga payo sa magkabilang gilid.

166
00:07:43,270 --> 00:07:46,231
At pagkatapos ay napalaya namin X ang
node na ang 13 na nilalaman,

167
00:07:46,231 --> 00:07:47,480
at hindi namin masira ang kadena.

168
00:07:47,480 --> 00:07:50,980
Kaya ginawa namin mabuti.

169
00:07:50,980 --> 00:07:53,000
>> Final note dito sa naka-link na mga listahan.

170
00:07:53,000 --> 00:07:55,990
Kaya parehong singly- at doble-link
mga listahan, tulad ng nasaksihan namin,

171
00:07:55,990 --> 00:07:58,959
pag talagang mabisa insertion
at pagtanggal ng mga sangkap.

172
00:07:58,959 --> 00:08:00,750
Maaari mong medyo marami gawin
ito sa tapat na oras.

173
00:08:00,750 --> 00:08:03,333
Ano ang kailangan nating gawin upang tanggalin
isang elemento lamang ng isang segundo na nakalipas?

174
00:08:03,333 --> 00:08:04,440
Lumipat kami sa isang pointer.

175
00:08:04,440 --> 00:08:05,920
Lumipat kami ng isa pang pointer.

176
00:08:05,920 --> 00:08:07,915
Napalaya namin X-- kinuha ng tatlong mga operasyon.

177
00:08:07,915 --> 00:08:14,500
Ito ay palaging tumatagal ng tatlong mga operasyon sa
tanggalin na node-- upang magbakante ng isang node.

178
00:08:14,500 --> 00:08:15,280
>> Paano namin ipasok?

179
00:08:15,280 --> 00:08:17,280
Well, hindi namin palaging lamang
tacking sa simula

180
00:08:17,280 --> 00:08:19,400
kung kami ay pagpasok ng mahusay.

181
00:08:19,400 --> 00:08:21,964
Kaya kailangan namin upang rearrange--
depende sa kung ito ay

182
00:08:21,964 --> 00:08:24,380
isang singly- o doble-link
list, maaaring kailangan namin upang gawin ang tatlong

183
00:08:24,380 --> 00:08:26,824
o apat na mga operasyon max.

184
00:08:26,824 --> 00:08:28,365
Ngunit muli, ito ay palaging tatlo o apat.

185
00:08:28,365 --> 00:08:30,531
Hindi mahalaga kung gaano karaming
sangkap na ito ay sa aming listahan,

186
00:08:30,531 --> 00:08:33,549
ito ay palaging tatlo o apat na operations--
tulad ng pagtanggal ay palaging

187
00:08:33,549 --> 00:08:35,320
tatlo o apat na mga operasyon.

188
00:08:35,320 --> 00:08:36,919
Ito ay pare-pareho ang panahon.

189
00:08:36,919 --> 00:08:38,169
Kaya na talagang mahusay.

190
00:08:38,169 --> 00:08:40,620
>> Sa array, kami ay gumagawa ng
isang bagay tulad ng uri pagpapasok.

191
00:08:40,620 --> 00:08:44,739
Ikaw ay malamang na isipin ang insertion na
uri ay hindi isang constant time algorithm.

192
00:08:44,739 --> 00:08:46,030
Ito ay talagang medyo mahal.

193
00:08:46,030 --> 00:08:48,840
Kaya ito ay isang pulutong mas mahusay para sa pagpasok.

194
00:08:48,840 --> 00:08:51,840
Ngunit tulad ng nabanggit ko sa
isa-isa-link na listahan ng video,

195
00:08:51,840 --> 00:08:54,030
Mayroon kami ng downside dito rin, di ba?

196
00:08:54,030 --> 00:08:57,580
Nawala namin ang kakayahan na
random access ang mga elemento.

197
00:08:57,580 --> 00:09:02,310
Hindi namin maaaring sabihin, gusto kong element bilang apat
o elemento number 10 ng isang listahan ng mga link

198
00:09:02,310 --> 00:09:04,990
sa parehong paraan na aming makakaya
gawin iyon sa isang array

199
00:09:04,990 --> 00:09:08,630
o maaari naming lamang direkta index
sa element aming array ni.

200
00:09:08,630 --> 00:09:10,930
>> At kaya sinusubukan upang makahanap ng isang
sangkap sa isang naka-link list--

201
00:09:10,930 --> 00:09:15,880
kung naghahanap ay important--
Maaari na ngayong kumuha ng linear oras.

202
00:09:15,880 --> 00:09:18,330
Bilang makakakuha listahan na, ito
maaaring tumagal ng isang karagdagang hakbang

203
00:09:18,330 --> 00:09:22,644
para sa bawat solong elemento sa listahan sa
Upang makita kung ano ang aming hinahanap.

204
00:09:22,644 --> 00:09:23,560
Kaya may trade off.

205
00:09:23,560 --> 00:09:25,780
May isang piraso ng isang pro
at con elemento dito.

206
00:09:25,780 --> 00:09:29,110
>> At doble-link na listahan ay hindi ang
huling uri ng kumbinasyon na istraktura ng data

207
00:09:29,110 --> 00:09:32,840
na namin makipag-usap tungkol sa,
pagkuha ng lahat ng mga pangunahing gusali

208
00:09:32,840 --> 00:09:34,865
bloke ng C isang paglalagay ng magkasama.

209
00:09:34,865 --> 00:09:37,900
Dahil sa katunayan, maaari naming
kahit na mas mahusay kaysa sa na ito gawin

210
00:09:37,900 --> 00:09:41,970
upang lumikha ng isang istraktura ng data na
maaaring ikaw ay maaaring sa paghahanap sa pamamagitan

211
00:09:41,970 --> 00:09:43,360
nasa tapat na panahon masyadong.

212
00:09:43,360 --> 00:09:46,080
Ngunit higit pa sa na sa isa pang video.

213
00:09:46,080 --> 00:09:47,150
>> Ako Doug Lloyd.

214
00:09:47,150 --> 00:09:49,050
Ito ay CS50.

215
00:09:49,050 --> 00:09:50,877