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
>> [Bermain muzik]

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

3
00:00:04,604 --> 00:00:05,520
DOUG LLOYD: Baiklah.

4
00:00:05,520 --> 00:00:07,860
Jadi, jika anda baru sahaja selesai yang
video pada senarai secara tunggal berkaitan maaf

5
00:00:07,860 --> 00:00:09,568
Saya meninggalkan anda di luar pada
sedikit cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Tetapi saya gembira anda berada di sini untuk menyelesaikan
kisah senarai duanya adalah terpakai berkaitan.

7
00:00:12,790 --> 00:00:15,250
>> Jadi, jika anda ingat dari
video itu, kita bercakap

8
00:00:15,250 --> 00:00:18,500
tentang bagaimana secara tunggal berkaitan
senarai lakukan menghadiri keupayaan kami

9
00:00:18,500 --> 00:00:22,090
untuk berurusan dengan maklumat
di mana bilangan elemen

10
00:00:22,090 --> 00:00:24,442
atau bilangan item dalam
senarai boleh berkembang atau mengecut.

11
00:00:24,442 --> 00:00:26,400
Kini kita boleh berurusan dengan
sesuatu seperti itu, di mana

12
00:00:26,400 --> 00:00:28,310
kami tidak dapat menanganinya dengan pameran.

13
00:00:28,310 --> 00:00:30,560
>> Tetapi mereka mengalami satu
had kritikal yang

14
00:00:30,560 --> 00:00:33,790
adalah bahawa dengan secara tunggal berkaitan
senarai, kami hanya pernah boleh bergerak

15
00:00:33,790 --> 00:00:36,200
dalam satu arah melalui senarai.

16
00:00:36,200 --> 00:00:39,010
Dan hanya keadaan sebenar
mana yang boleh menjadi masalah

17
00:00:39,010 --> 00:00:41,250
adalah apabila kita cuba untuk
memadam elemen tunggal.

18
00:00:41,250 --> 00:00:46,000
Dan kami tidak sekali membincangkan bagaimana untuk melakukannya
dalam senarai secara tunggal berkaitan dalam kod pseudo.

19
00:00:46,000 --> 00:00:48,797
Ia sudah pasti boleh dilakukan, tetapi
ia boleh menjadi sedikit kerumitan.

20
00:00:48,797 --> 00:00:50,630
Jadi, jika anda mendapati diri anda
dalam keadaan di mana

21
00:00:50,630 --> 00:00:53,175
anda cuba untuk memadam
elemen tunggal dari senarai

22
00:00:53,175 --> 00:00:55,430
atau ia akan diperlukan
bahawa anda akan memotong

23
00:00:55,430 --> 00:00:57,970
elemen tunggal dari
senarai, anda mungkin mahu

24
00:00:57,970 --> 00:01:02,090
mempertimbangkan untuk menggunakan duanya adalah terpakai berkaitan
senarai bukannya senarai yang secara tunggal berkaitan.

25
00:01:02,090 --> 00:01:06,320
Oleh kerana senarai duanya adalah terpakai berkaitan membolehkan anda
untuk bergerak kedua-dua hadapan dan ke belakang

26
00:01:06,320 --> 00:01:09,340
melalui senarai dan bukannya
hanya ke hadapan melalui list-- yang

27
00:01:09,340 --> 00:01:13,950
hanya dengan menambah satu elemen tambahan
definisi struktur kami

28
00:01:13,950 --> 00:01:16,690
untuk nod senarai duanya adalah terpakai berkaitan.

29
00:01:16,690 --> 00:01:19,770
>> Sekali lagi, jika anda tidak akan
dapat memotong elemen tunggal

30
00:01:19,770 --> 00:01:24,810
dari list-- kerana kami menambah
satu medan tambahan kepada struktur kami

31
00:01:24,810 --> 00:01:28,340
definisi, nod sendiri
untuk senarai duanya adalah terpakai berkaitan

32
00:01:28,340 --> 00:01:29,550
akan menjadi lebih besar.

33
00:01:29,550 --> 00:01:31,600
Mereka akan mengambil
lebih banyak bait ingatan.

34
00:01:31,600 --> 00:01:34,160
Dan jadi jika ini bukan sesuatu
anda akan perlu lakukan,

35
00:01:34,160 --> 00:01:36,300
anda boleh memutuskan ia
tidak bernilai perdagangan luar

36
00:01:36,300 --> 00:01:39,360
perlu menghabiskan tambahan
bait memori diperlukan

37
00:01:39,360 --> 00:01:43,940
untuk senarai duanya adalah terpakai berkaitan jika anda tidak
akan memotong elemen tunggal.

38
00:01:43,940 --> 00:01:46,760
Tetapi mereka juga sejuk
untuk perkara-perkara lain juga.

39
00:01:46,760 --> 00:01:51,260
>> Jadi seperti yang saya katakan, kita hanya perlu menambah
satu medan tunggal untuk struktur kami

40
00:01:51,260 --> 00:01:55,360
definition-- tanggapan ini
daripada penunjuk Sebelumnya.

41
00:01:55,360 --> 00:01:58,620
Jadi dengan senarai yang secara tunggal berkaitan, kita
mempunyai nilai dan penunjuk Seterusnya,

42
00:01:58,620 --> 00:02:02,850
jadi senarai duanya adalah terpakai berkaitan hanya mempunyai
cara untuk bergerak ke belakang juga.

43
00:02:02,850 --> 00:02:04,960
>> Sekarang dalam berkaitan secara tunggal
senarai video, kita berbincang

44
00:02:04,960 --> 00:02:07,210
mengenai adalah lima daripada
perkara utama yang anda perlukan untuk menjadi

45
00:02:07,210 --> 00:02:09,449
dapat melakukan untuk bekerja dengan senarai berkaitan.

46
00:02:09,449 --> 00:02:12,880
Dan bagi kebanyakan, hakikat
bahawa itu senarai duanya adalah terpakai berkaitan

47
00:02:12,880 --> 00:02:14,130
tidak benar-benar satu lompatan besar.

48
00:02:14,130 --> 00:02:17,936
Kita masih boleh mencari melalui dengan hanya
bergerak ke hadapan dari awal hingga akhir.

49
00:02:17,936 --> 00:02:20,810
Kita masih boleh mewujudkan nod daripada
udara nipis, cukup banyak cara yang sama.

50
00:02:20,810 --> 00:02:23,591
Kita boleh memadam senarai cantik
banyak cara yang sama juga.

51
00:02:23,591 --> 00:02:25,340
Perkara-perkara itu sahaja
adalah secara halus berbeza,

52
00:02:25,340 --> 00:02:28,970
benar-benar, adalah memasukkan
nod baru ke dalam senarai,

53
00:02:28,970 --> 00:02:33,722
dan kami akhirnya akan bercakap tentang memotong
satu unsur dari senarai juga.

54
00:02:33,722 --> 00:02:35,430
Sekali lagi, cukup banyak
tiga yang lain, kami

55
00:02:35,430 --> 00:02:37,888
tidak akan bercakap tentang mereka
sekarang kerana mereka hanya

56
00:02:37,888 --> 00:02:43,920
tweak yang sangat kecil kepada idea-idea yang dibincangkan
dalam senarai video secara tunggal berkaitan.

57
00:02:43,920 --> 00:02:46,292
>> Jadi mari kita memasukkan nod baru
ke dalam senarai duanya adalah terpakai berkaitan.

58
00:02:46,292 --> 00:02:48,750
Kita bercakap tentang melakukan ini untuk
secara tunggal berkaitan senarai juga,

59
00:02:48,750 --> 00:02:52,020
tetapi ada beberapa tambahan
menangkap dengan senarai duanya adalah terpakai berkaitan.

60
00:02:52,020 --> 00:02:55,280
Kami [? lulus?] dalam ketua
disenaraikan di sini dan beberapa nilai sewenang-wenangnya,

61
00:02:55,280 --> 00:02:58,600
dan kami mahu mendapatkan ketua baru
senarai daripada fungsi ini.

62
00:02:58,600 --> 00:03:01,414
Itulah sebabnya ia mengembalikan bintang dllnode.

63
00:03:01,414 --> 00:03:02,330
Jadi apakah langkah-langkah?

64
00:03:02,330 --> 00:03:04,496
Mereka adalah, sekali lagi, hampir sama
kepada senarai secara tunggal berkaitan

65
00:03:04,496 --> 00:03:05,670
dengan satu tambahan tambahan.

66
00:03:05,670 --> 00:03:08,900
Kami mahu memperuntukkan ruang untuk yang baru
nod dan periksa untuk memastikan ia adalah sah.

67
00:03:08,900 --> 00:03:11,510
Kami mahu mengisi nod bahawa sehingga
dengan apa sahaja maklumat yang kami

68
00:03:11,510 --> 00:03:12,564
mahu meletakkan di dalamnya.

69
00:03:12,564 --> 00:03:15,480
Perkara terakhir yang perlu kita do-- yang
perkara tambahan yang perlu kita lakukan, rather--

70
00:03:15,480 --> 00:03:19,435
adalah untuk menetapkan penunjuk Sebelum
kepala lama senarai.

71
00:03:19,435 --> 00:03:21,310
Ingat bahawa kerana
senarai duanya adalah terpakai GLC

72
00:03:21,310 --> 00:03:23,110
kita boleh bergerak ke hadapan
dan backwards-- yang

73
00:03:23,110 --> 00:03:27,080
bermakna setiap nod sebenarnya menunjukkan
dua nod lain dan bukan hanya satu.

74
00:03:27,080 --> 00:03:29,110
Dan dengan itu kita perlu untuk menetapkan
kepala lama dalam senarai

75
00:03:29,110 --> 00:03:32,151
untuk menunjukkan ke belakang untuk ketua baru
senarai berkaitan, yang adalah sesuatu

76
00:03:32,151 --> 00:03:33,990
kami tidak perlu lakukan sebelum ini.

77
00:03:33,990 --> 00:03:37,420
Dan seperti sebelum ini, kita hanya mengembalikan
penunjuk kepada ketua baru senarai.

78
00:03:37,420 --> 00:03:38,220
>> Jadi di sini adalah senarai.

79
00:03:38,220 --> 00:03:40,144
Kami mahu memasukkan 12 ke dalam senarai ini.

80
00:03:40,144 --> 00:03:42,060
Perhatikan rajah
adalah sedikit berbeza.

81
00:03:42,060 --> 00:03:47,710
Setiap nod mengandungi tiga fields--
data dan penunjuk seterusnya dalam merah,

82
00:03:47,710 --> 00:03:50,170
dan penunjuk Sebelum warna biru.

83
00:03:50,170 --> 00:03:54,059
Tiada apa-apa sebelum nod 15,
jadi penunjuk Sebelum adalah null.

84
00:03:54,059 --> 00:03:55,350
Ia adalah permulaan senarai.

85
00:03:55,350 --> 00:03:56,560
Tiada apa-apa di hadapannya.

86
00:03:56,560 --> 00:04:03,350
Dan apa-apa yang datang selepas nod 10, dan
jadi ia adalah penunjuk seterusnya ialah null juga.

87
00:04:03,350 --> 00:04:05,616
>> Jadi mari kita menambah 12 ke senarai ini.

88
00:04:05,616 --> 00:04:08,070
Kita perlu [didengar] ruang untuk nod.

89
00:04:08,070 --> 00:04:11,480
Kita meletakkan 12 di dalamnya.

90
00:04:11,480 --> 00:04:14,840
Dan sekali lagi, kita perlu benar-benar
berhati-hati untuk tidak memecahkan rantai.

91
00:04:14,840 --> 00:04:17,144
Kami mahu menyusun semula
petunjuk dalam susunan yang betul.

92
00:04:17,144 --> 00:04:19,519
Dan kadang-kadang yang mungkin mean--
seperti yang kita akan lihat terutamanya

93
00:04:19,519 --> 00:04:24,120
dengan delete-- bahawa kita mempunyai beberapa
petunjuk berlebihan, tetapi itu OK.

94
00:04:24,120 --> 00:04:25,750
>> Jadi, apa yang kita mahu lakukan dahulu?

95
00:04:25,750 --> 00:04:28,290
Saya akan mengesyorkan ini
perkara yang anda perlu mungkin

96
00:04:28,290 --> 00:04:35,350
lakukan adalah untuk mengisi petunjuk daripada 12
nod sebelum anda menyentuh orang lain.

97
00:04:35,350 --> 00:04:38,640
Jadi apa yang 12 akan menunjukkan akan datang?

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

99
00:04:39,860 --> 00:04:42,430
Apa yang datang sebelum 12?

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

101
00:04:43,640 --> 00:04:46,280
Sekarang kita telah memenuhi
maklumat tambahan di 12

102
00:04:46,280 --> 00:04:49,320
jadi ia mempunyai Sebelumnya, Next, dan nilai.

103
00:04:49,320 --> 00:04:53,505
>> Sekarang kita boleh mempunyai 15-- ini tambahan
langkah kita bercakap about-- kita

104
00:04:53,505 --> 00:04:56,590
boleh mempunyai 15 titik kembali ke 12.

105
00:04:56,590 --> 00:04:59,634
Dan sekarang kita boleh bergerak ketua
senarai berkaitan juga menjadi 12.

106
00:04:59,634 --> 00:05:02,550
Jadi ia agak sama dengan apa yang kita
lakukan dengan senarai secara tunggal GLC

107
00:05:02,550 --> 00:05:06,940
kecuali untuk langkah tambahan sebanyak
menghubungkan kepala lama dalam senarai

108
00:05:06,940 --> 00:05:09,810
belakang untuk ketua baru senarai.

109
00:05:09,810 --> 00:05:12,170
>> Sekarang mari kita akhirnya memadam
nod dari senarai berpaut.

110
00:05:12,170 --> 00:05:14,350
Jadi katakan kita ada
beberapa fungsi lain yang

111
00:05:14,350 --> 00:05:18,080
adalah mencari nod kita mahu memadam
dan telah memberikan kita penunjuk untuk betul-betul

112
00:05:18,080 --> 00:05:19,710
nod yang kita mahu padamkan.

113
00:05:19,710 --> 00:05:22,360
Kita tidak need-- mengatakan
kepala masih di peringkat global diisytiharkan.

114
00:05:22,360 --> 00:05:23,590
Kita tidak perlu kepala di sini.

115
00:05:23,590 --> 00:05:26,830
Semua fungsi ini lakukan adalah kami telah
mendapati penunjuk kepada yang betul-betul kita nod

116
00:05:26,830 --> 00:05:28,090
mahu menghilangkan.

117
00:05:28,090 --> 00:05:28,940
Mari kita membuangnya.

118
00:05:28,940 --> 00:05:31,859
Ia adalah lebih mudah dengan
duanya adalah terpakai berkaitan senarai.

119
00:05:31,859 --> 00:05:33,650
First-- ia sebenarnya
hanya beberapa perkara.

120
00:05:33,650 --> 00:05:38,760
Kita hanya perlu untuk menetapkan sekitarnya
petunjuk nod 'supaya mereka melangkau lebih

121
00:05:38,760 --> 00:05:40,240
nod yang kita mahu padamkan.

122
00:05:40,240 --> 00:05:43,484
Dan kemudian kita boleh memadam nod tersebut.

123
00:05:43,484 --> 00:05:45,150
Jadi sekali lagi, kami hanya akan melalui sini.

124
00:05:45,150 --> 00:05:49,625
Kami nampaknya memutuskan bahawa
kami mahu memadam X. nod

125
00:05:49,625 --> 00:05:51,500
Dan sekali lagi, apa yang saya
melakukan sini-- oleh way-- yang

126
00:05:51,500 --> 00:05:54,580
adalah kes umum untuk
nod yang ada di tengah-tengah.

127
00:05:54,580 --> 00:05:56,547
Terdapat beberapa
kaveat tambahan yang anda

128
00:05:56,547 --> 00:05:59,380
perlu mengambil kira apabila anda memotong
awal-awal senarai

129
00:05:59,380 --> 00:06:01,040
atau akhir sangat senarai.

130
00:06:01,040 --> 00:06:03,730
Ada beberapa khas
kes sudut menangani sana.

131
00:06:03,730 --> 00:06:07,960
>> Jadi ini berfungsi untuk memotong mana-mana nod
di tengah-tengah yang list-- yang

132
00:06:07,960 --> 00:06:11,550
mempunyai penunjuk yang sah ke hadapan
dan penunjuk yang sah ke belakang,

133
00:06:11,550 --> 00:06:14,460
sah penunjuk sebelum dan Seterusnya.

134
00:06:14,460 --> 00:06:16,530
Sekali lagi, jika anda bekerja
dengan hujung, anda

135
00:06:16,530 --> 00:06:18,500
perlu untuk mengendalikan mereka
sedikit berbeza,

136
00:06:18,500 --> 00:06:19,570
dan kami tidak akan
bercakap tentang itu sekarang.

137
00:06:19,570 --> 00:06:21,319
Tetapi anda boleh mungkin
memikirkan apa yang perlu

138
00:06:21,319 --> 00:06:24,610
yang perlu dilakukan hanya dengan menonton video ini.

139
00:06:24,610 --> 00:06:28,910
>> Jadi kami telah diasingkan X. X adalah nod
kami mahu memadam dari senarai.

140
00:06:28,910 --> 00:06:30,140
Apa yang kita lakukan?

141
00:06:30,140 --> 00:06:32,800
Pertama, kita perlu untuk menyusun semula
petunjuk luar.

142
00:06:32,800 --> 00:06:35,815
Kita perlu menyusun semula
9. berikut untuk melangkau lebih 13

143
00:06:35,815 --> 00:06:38,030
dan menunjukkan kepada 10-- yang
adalah apa yang kita baru sahaja selesai.

144
00:06:38,030 --> 00:06:41,180
Dan kita juga perlu
menyusun semula 10 yang terdahulu

145
00:06:41,180 --> 00:06:44,610
untuk menghala ke 9 dan bukan menunjuk ke 13.

146
00:06:44,610 --> 00:06:46,490
>> Jadi sekali lagi, ini adalah
gambar rajah untuk memulakan dengan.

147
00:06:46,490 --> 00:06:47,730
Ini adalah rangkaian kami.

148
00:06:47,730 --> 00:06:51,027
Kita perlu untuk melangkau lebih 13,
tetapi kita perlu juga memelihara

149
00:06:51,027 --> 00:06:52,110
integriti senarai.

150
00:06:52,110 --> 00:06:54,680
Kami tidak mahu kehilangan apa-apa
maklumat dalam arah.

151
00:06:54,680 --> 00:06:59,620
Oleh itu, kita perlu untuk menyusun semula
petunjuk dengan berhati-hati

152
00:06:59,620 --> 00:07:02,240
jadi kami tidak memecahkan rantai pada semua.

153
00:07:02,240 --> 00:07:05,710
>> Oleh itu, kita boleh mengatakan 9. penunjuk Seterusnya
menunjuk ke tempat yang sama

154
00:07:05,710 --> 00:07:08,040
yang tiga belas Next
penunjuk mata sekarang.

155
00:07:08,040 --> 00:07:10,331
Kerana kami akhirnya
akan mahu untuk melangkau lebih 13.

156
00:07:10,331 --> 00:07:13,750
Jadi di mana sahaja 13 mata seterusnya, anda
mahu sembilan untuk menunjukkan sana.

157
00:07:13,750 --> 00:07:15,200
Jadi itulah yang.

158
00:07:15,200 --> 00:07:20,370
Dan kemudian di mana sahaja 13 mata di belakang
kepada, apa sahaja yang datang sebelum 13,

159
00:07:20,370 --> 00:07:24,800
kita mahu 10 untuk menunjukkan
itu bukannya 13.

160
00:07:24,800 --> 00:07:29,290
Sekarang perhatikan, jika anda mengikuti
anak panah, kita boleh turun 13

161
00:07:29,290 --> 00:07:32,380
tanpa benar-benar kehilangan apa-apa maklumat.

162
00:07:32,380 --> 00:07:36,002
Kami terus integriti senarai,
bergerak kedua-dua ke hadapan dan ke belakang.

163
00:07:36,002 --> 00:07:38,210
Dan kemudian kita boleh hanya jenis
untuk membersihkannya sehingga sedikit

164
00:07:38,210 --> 00:07:40,930
dengan menarik senarai bersama-sama.

165
00:07:40,930 --> 00:07:43,270
Oleh itu, kita disusun semula itu
petunjuk mana pihak.

166
00:07:43,270 --> 00:07:46,231
Dan kemudian kita dibebaskan X
nod yang mengandungi 13,

167
00:07:46,231 --> 00:07:47,480
dan kami tidak mematahkan rantai.

168
00:07:47,480 --> 00:07:50,980
Oleh itu, kita telah berbuat baik.

169
00:07:50,980 --> 00:07:53,000
>> Nota terakhir di sini pada senarai berkaitan.

170
00:07:53,000 --> 00:07:55,990
Jadi kedua-dua singly- dan dua kali ganda berkaitan
senarai, seperti yang kita lihat,

171
00:07:55,990 --> 00:07:58,959
sokongan sisipan benar-benar berkesan
dan penghapusan unsur-unsur.

172
00:07:58,959 --> 00:08:00,750
Anda cukup banyak boleh lakukan
dalam masa yang berterusan.

173
00:08:00,750 --> 00:08:03,333
Apa yang kita perlu lakukan untuk memadam
elemen sesaat yang lalu?

174
00:08:03,333 --> 00:08:04,440
Kami berpindah satu penunjuk.

175
00:08:04,440 --> 00:08:05,920
Kami berpindah penunjuk lain.

176
00:08:05,920 --> 00:08:07,915
Kami dibebaskan X-- mengambil masa tiga operasi.

177
00:08:07,915 --> 00:08:14,500
Ia sentiasa mengambil masa tiga operasi untuk
memadam node-- bahawa untuk membebaskan nod.

178
00:08:14,500 --> 00:08:15,280
>> Bagaimana kita memasukkan?

179
00:08:15,280 --> 00:08:17,280
Well, kami hanya sentiasa
tacking pada mulanya

180
00:08:17,280 --> 00:08:19,400
jika kita memasukkan cekap.

181
00:08:19,400 --> 00:08:21,964
Oleh itu, kita perlu rearrange--
bergantung kepada jika ia

182
00:08:21,964 --> 00:08:24,380
yang singly- atau dua kali ganda berkaitan
senarai, kita mungkin perlu melakukan tiga

183
00:08:24,380 --> 00:08:26,824
atau empat operasi max.

184
00:08:26,824 --> 00:08:28,365
Tetapi sekali lagi, ia sentiasa tiga atau empat.

185
00:08:28,365 --> 00:08:30,531
Tidak kira berapa banyak
elemen dalam senarai kami,

186
00:08:30,531 --> 00:08:33,549
ia sentiasa tiga atau empat operations--
seperti penghapusan sentiasa

187
00:08:33,549 --> 00:08:35,320
tiga atau empat operasi.

188
00:08:35,320 --> 00:08:36,919
Ia adalah masa yang berterusan.

189
00:08:36,919 --> 00:08:38,169
Jadi, itu benar-benar hebat.

190
00:08:38,169 --> 00:08:40,620
>> Dengan tatasusunan, kita telah melakukan
sesuatu seperti jenis kemasukan.

191
00:08:40,620 --> 00:08:44,739
Anda mungkin ingat sisipan yang
jenis bukan algoritma masa yang berterusan.

192
00:08:44,739 --> 00:08:46,030
Ia sebenarnya cukup mahal.

193
00:08:46,030 --> 00:08:48,840
Jadi ini adalah lebih baik untuk memasukkan.

194
00:08:48,840 --> 00:08:51,840
Tetapi seperti yang saya nyatakan di
secara tunggal berkaitan senarai video,

195
00:08:51,840 --> 00:08:54,030
kami mempunyai Kelemahan di sini juga, kan?

196
00:08:54,030 --> 00:08:57,580
Kami telah kehilangan keupayaan untuk
rawak mengakses elemen.

197
00:08:57,580 --> 00:09:02,310
Kita tidak boleh mengatakan, saya mahu beberapa elemen empat
atau unsur nombor 10 dalam senarai berpaut

198
00:09:02,310 --> 00:09:04,990
dengan cara yang sama yang kita boleh
berbuat demikian dengan array

199
00:09:04,990 --> 00:09:08,630
atau kita boleh hanya terus indeks
ke dalam elemen array kita.

200
00:09:08,630 --> 00:09:10,930
>> Dan sebagainya cuba untuk mencari
elemen dalam list-- berpaut

201
00:09:10,930 --> 00:09:15,880
jika pencarian adalah important--
sekarang mungkin mengambil masa linear.

202
00:09:15,880 --> 00:09:18,330
Seperti senarai mendapat lebih lama, ia
mungkin mengambil satu langkah tambahan

203
00:09:18,330 --> 00:09:22,644
untuk setiap elemen tunggal dalam senarai dalam
untuk mencari apa yang kita cari.

204
00:09:22,644 --> 00:09:23,560
Jadi ada keseimbangan perdagangan.

205
00:09:23,560 --> 00:09:25,780
Ada sedikit pro
dan con unsur di sini.

206
00:09:25,780 --> 00:09:29,110
>> Dan senarai duanya adalah terpakai berkaitan tidak adalah
jenis terakhir gabungan struktur data

207
00:09:29,110 --> 00:09:32,840
yang kita akan bercakap tentang,
mengambil semua binaan asas

208
00:09:32,840 --> 00:09:34,865
blok C yang meletakkan bersama-sama.

209
00:09:34,865 --> 00:09:37,900
Kerana sebenarnya, kita boleh
malah menjadi lebih baik daripada ini

210
00:09:37,900 --> 00:09:41,970
untuk mewujudkan satu struktur data yang
anda mungkin boleh untuk mencari melalui

211
00:09:41,970 --> 00:09:43,360
dalam masa yang berterusan juga.

212
00:09:43,360 --> 00:09:46,080
Tetapi lebih kepada yang dalam video lain.

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

214
00:09:47,150 --> 00:09:49,050
Ini adalah CS50.

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