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
>> [Música tocando]

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

3
00:00:04,604 --> 00:00:05,520
Doug LLOYD: Todo ben.

4
00:00:05,520 --> 00:00:07,860
Entón, se acaba de rematar que
vídeo en listas individualmente ligados pesaroso

5
00:00:07,860 --> 00:00:09,568
Eu deixei vostede fóra nun
pouco dun cliffhanger.

6
00:00:09,568 --> 00:00:12,790
Pero eu estou feliz que está aquí para rematar
a historia de listas dobremente ligadas.

7
00:00:12,790 --> 00:00:15,250
>> Entón, se lembrar de
que o vídeo, falamos

8
00:00:15,250 --> 00:00:18,500
sobre como individualmente conectado
Listas de facer participar a nosa capacidade

9
00:00:18,500 --> 00:00:22,090
para xestionar información
en que o número de elementos

10
00:00:22,090 --> 00:00:24,442
ou o número de elementos nas
unha lista pode aumentar ou diminuír.

11
00:00:24,442 --> 00:00:26,400
Agora podemos xestionar
algo así como que, cando

12
00:00:26,400 --> 00:00:28,310
non poderiamos tratar con isto con matrices.

13
00:00:28,310 --> 00:00:30,560
>> Pero padecen unha
limitación crítica que

14
00:00:30,560 --> 00:00:33,790
é que, cun conectado illadamente
lista, só podemos mover

15
00:00:33,790 --> 00:00:36,200
nunha única dirección a través da lista.

16
00:00:36,200 --> 00:00:39,010
E a única situación real
onde que pode chegar a ser un problema

17
00:00:39,010 --> 00:00:41,250
foi cando estabamos intentando
eliminar un único elemento.

18
00:00:41,250 --> 00:00:46,000
E nós nin sequera discutir como facelo
nunha lista illadamente ligada en pseudocódigo.

19
00:00:46,000 --> 00:00:48,797
É certamente factible, pero
pode ser un pouco de un problema.

20
00:00:48,797 --> 00:00:50,630
Entón, se atopa-se
nunha situación onde

21
00:00:50,630 --> 00:00:53,175
estás eliminar
elementos únicos da lista

22
00:00:53,175 --> 00:00:55,430
ou que vai ser esixido
que vai ser a exclusión

23
00:00:55,430 --> 00:00:57,970
elementos únicos de
a lista, pode querer

24
00:00:57,970 --> 00:01:02,090
considerar o uso dun conectado dobremente
lista en lugar dunha lista illadamente conectado.

25
00:01:02,090 --> 00:01:06,320
Como as listas dobremente vinculadas permiten que
para mover ambos adiante e cara atrás

26
00:01:06,320 --> 00:01:09,340
a través da lista no canto de
só para adiante a través da lista--

27
00:01:09,340 --> 00:01:13,950
só engadindo un elemento extra
a nosa definición de estrutura

28
00:01:13,950 --> 00:01:16,690
ao nó de lista dobremente vinculada.

29
00:01:16,690 --> 00:01:19,770
>> De novo, se non está indo a
ser exclusión elementos únicos

30
00:01:19,770 --> 00:01:24,810
do lista-- porque estamos engadindo
un campo extra para a nosa estrutura

31
00:01:24,810 --> 00:01:28,340
definición, os propios nós
para listas dobremente ligadas

32
00:01:28,340 --> 00:01:29,550
será maior.

33
00:01:29,550 --> 00:01:31,600
Eles van leva
Se máis bytes de memoria.

34
00:01:31,600 --> 00:01:34,160
E por iso, se iso non é algo
vai ter facer,

35
00:01:34,160 --> 00:01:36,300
pode decidir que é
Non paga a pena o trade off

36
00:01:36,300 --> 00:01:39,360
ter que pasar o extra
bytes de memoria

37
00:01:39,360 --> 00:01:43,940
Para obter unha lista dobremente vinculada se non está
será apagando elementos individuais.

38
00:01:43,940 --> 00:01:46,760
Pero tamén é legal
para outras cousas tamén.

39
00:01:46,760 --> 00:01:51,260
>> Entón, como dixen, nós só temos que engadir
un único campo para a nosa estrutura

40
00:01:51,260 --> 00:01:55,360
definition-- esta noción
dun punteiro anterior.

41
00:01:55,360 --> 00:01:58,620
Así, con unha lista illadamente conectado, nós
ten o valor eo punteiro Logo

42
00:01:58,620 --> 00:02:02,850
así que a lista dobremente vinculada só ten
un xeito de moverse cara atrás tamén.

43
00:02:02,850 --> 00:02:04,960
>> Agora, no individualmente conectado
lista de vídeos, falamos

44
00:02:04,960 --> 00:02:07,210
sobre estes son cinco dos
principais cousas que ten que estar

45
00:02:07,210 --> 00:02:09,449
capaz de facer para traballar con listas ligadas.

46
00:02:09,449 --> 00:02:12,880
E para a maioría destas, o feito
que é unha lista dobremente vinculada

47
00:02:12,880 --> 00:02:14,130
non é realmente un gran salto.

48
00:02:14,130 --> 00:02:17,936
Aínda pode buscar por só
fronte do principio ao final.

49
00:02:17,936 --> 00:02:20,810
Aínda os podemos crear un nodo
aire, practicamente do mesmo xeito.

50
00:02:20,810 --> 00:02:23,591
Podemos eliminar listas fermosa
do mesmo xeito tamén.

51
00:02:23,591 --> 00:02:25,340
As únicas cousas que
son sutilmente diferentes,

52
00:02:25,340 --> 00:02:28,970
realmente, está introducindo
novos nós na lista,

53
00:02:28,970 --> 00:02:33,722
e nós imos rematar falar da exclusión
un único elemento da lista ben.

54
00:02:33,722 --> 00:02:35,430
Unha vez máis, moi bonito
os outros tres, somos

55
00:02:35,430 --> 00:02:37,888
non vai falar sobre eles
agora, porque son só

56
00:02:37,888 --> 00:02:43,920
axustes moito menores sobre as ideas discutidas
no video lista illadamente conectado.

57
00:02:43,920 --> 00:02:46,292
>> Entón, imos introducir un novo nodo
nunha lista dobremente vinculada.

58
00:02:46,292 --> 00:02:48,750
Nós falamos sobre como facelo para
listas illadamente ligada, así como,

59
00:02:48,750 --> 00:02:52,020
pero hai un par de extras
colle con listas dobremente ligadas.

60
00:02:52,020 --> 00:02:55,280
Estamos [? pasando?] na cabeza da
listar aquí e algún valor arbitrario,

61
00:02:55,280 --> 00:02:58,600
e queremos comezar o novo xefe
fóra da lista desta función.

62
00:02:58,600 --> 00:03:01,414
É por iso que amosa unha estrela dllnode.

63
00:03:01,414 --> 00:03:02,330
Entón, cales son os pasos?

64
00:03:02,330 --> 00:03:04,496
Son, de novo, moi semellante
a listas ligadas individualmente-

65
00:03:04,496 --> 00:03:05,670
con un engadido adicional.

66
00:03:05,670 --> 00:03:08,900
Queremos aloca espazo para un novo
nó e de verificación para que seguro que é válido.

67
00:03:08,900 --> 00:03:11,510
Queremos encher ese nó up
con toda a información que

68
00:03:11,510 --> 00:03:12,564
quero poñer nel.

69
00:03:12,564 --> 00:03:15,480
A última cousa que necesitamos para o fazer--
extra que necesitamos facer, rather--

70
00:03:15,480 --> 00:03:19,435
é para corrixir o punteiro Anterior
do antigo xefe da lista.

71
00:03:19,435 --> 00:03:21,310
Lembre que, debido
listas de dobremente vinculadas,

72
00:03:21,310 --> 00:03:23,110
podemos avanzar
e que backwards--

73
00:03:23,110 --> 00:03:27,080
significa que cada nodo realmente apunta
a dous outros nós no canto de só un.

74
00:03:27,080 --> 00:03:29,110
E así temos que corrixir
o antigo xefe da lista

75
00:03:29,110 --> 00:03:32,151
para apuntar cara atrás, para o novo xefe da
a lista ligada, o que era algo

76
00:03:32,151 --> 00:03:33,990
nós non temos que facer antes.

77
00:03:33,990 --> 00:03:37,420
E, como antes, nós só voltar un
Punteiro do novo cabeza da lista.

78
00:03:37,420 --> 00:03:38,220
>> Entón aquí está a lista.

79
00:03:38,220 --> 00:03:40,144
Queremos introducir 12 desta lista.

80
00:03:40,144 --> 00:03:42,060
Teña en conta que o diagrama
é un pouco diferente.

81
00:03:42,060 --> 00:03:47,710
Cada nodo contén tres fields--
de datos, e un punteiro de continuación no vermello,

82
00:03:47,710 --> 00:03:50,170
e un punteiro anterior en azul.

83
00:03:50,170 --> 00:03:54,059
Nada vén antes do nodo 15,
polo que a súa anterior punteiro é nulo.

84
00:03:54,059 --> 00:03:55,350
É o inicio da lista.

85
00:03:55,350 --> 00:03:56,560
Non hai nada antes dela.

86
00:03:56,560 --> 00:04:03,350
E nada vén despois do nodo 10, e
polo que é punteiro continuación é nula tamén.

87
00:04:03,350 --> 00:04:05,616
>> Entón, imos engadir 12 a esta lista.

88
00:04:05,616 --> 00:04:08,070
Necesitamos [inaudível] espazo para o no.

89
00:04:08,070 --> 00:04:11,480
Poñemos 12 dentro do mesmo.

90
00:04:11,480 --> 00:04:14,840
E entón, de novo, hai que ser realmente
coidado de non romper a cadea.

91
00:04:14,840 --> 00:04:17,144
Queremos reorganizar a
punteiros na orde correcta.

92
00:04:17,144 --> 00:04:19,519
E ás veces iso pode dizer--
como veremos particularmente

93
00:04:19,519 --> 00:04:24,120
con delete-- que temos algún
punteiros redundante, pero está todo OK.

94
00:04:24,120 --> 00:04:25,750
>> Entón, o que queremos facer primeiro?

95
00:04:25,750 --> 00:04:28,290
Eu recomenda o
Cousas que ten que, probablemente,

96
00:04:28,290 --> 00:04:35,350
facer son para cubrir os punteiros dos 12
nó antes de tocar en calquera outra persoa.

97
00:04:35,350 --> 00:04:38,640
Entón, o que é 12 vai apuntar ao seguinte?

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

99
00:04:39,860 --> 00:04:42,430
O que vén antes de 12?

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

101
00:04:43,640 --> 00:04:46,280
Agora nós encheu o
información extra en 12

102
00:04:46,280 --> 00:04:49,320
polo que ten Anterior, Seguinte e valor.

103
00:04:49,320 --> 00:04:53,505
>> Agora podemos ter 15-- este adicional
paso que estaban falando about-- nós

104
00:04:53,505 --> 00:04:56,590
pode ter 15 puntos ao 12.

105
00:04:56,590 --> 00:04:59,634
E agora podemos mover a cabeza de
a lista encadeada ser 12.

106
00:04:59,634 --> 00:05:02,550
Entón é moi semellante ao que
estaban facendo listas individualmente ligados,

107
00:05:02,550 --> 00:05:06,940
agás para o paso adicional de
conectando o vello cabeza de lista

108
00:05:06,940 --> 00:05:09,810
volta para a nova cabeza da lista.

109
00:05:09,810 --> 00:05:12,170
>> Agora imos finalmente borrar
un nó dunha lista ligada.

110
00:05:12,170 --> 00:05:14,350
Entón, digamos que temos
algunha outra función que

111
00:05:14,350 --> 00:05:18,080
é atopar un nó que quere eliminar
e nos deu un punteiro para exactamente

112
00:05:18,080 --> 00:05:19,710
o no que desexa eliminar.

113
00:05:19,710 --> 00:05:22,360
Nós nin sequera dicir o need--
cabeza aínda está globalmente declarado.

114
00:05:22,360 --> 00:05:23,590
Non necesitamos cabeza aquí.

115
00:05:23,590 --> 00:05:26,830
Todo esta función está a facer é que temos
atopar un punteiro para o que nó

116
00:05:26,830 --> 00:05:28,090
quere se librar de.

117
00:05:28,090 --> 00:05:28,940
Imos librar-se del.

118
00:05:28,940 --> 00:05:31,859
É moito máis doado con
listas dobremente vinculada.

119
00:05:31,859 --> 00:05:33,650
First-- é realmente
só un par de cousas.

120
00:05:33,650 --> 00:05:38,760
Nós só necesitamos corrixir torno
punteiros dos nós de xeito que xa Saltar

121
00:05:38,760 --> 00:05:40,240
o no que desexa eliminar.

122
00:05:40,240 --> 00:05:43,484
E entón podemos eliminar este nodo.

123
00:05:43,484 --> 00:05:45,150
Entón, de novo, estamos só pasando por aquí.

124
00:05:45,150 --> 00:05:49,625
Nós aparentemente decidiron que
queremos eliminar o nodo X.

125
00:05:49,625 --> 00:05:51,500
E, de novo, o que eu son
facendo aqui-- polo maneira--

126
00:05:51,500 --> 00:05:54,580
é un proceso xeral para unha
nó que está no medio.

127
00:05:54,580 --> 00:05:56,547
Hai un par de
caveats extras que

128
00:05:56,547 --> 00:05:59,380
cómpre considerar cando está excluíndo
o inicio da lista

129
00:05:59,380 --> 00:06:01,040
ou o fin da lista.

130
00:06:01,040 --> 00:06:03,730
Hai un par de especial
casos de canto ao manexar alí.

131
00:06:03,730 --> 00:06:07,960
>> Entón, iso funciona para eliminar calquera nodo
no medio do que un lista--

132
00:06:07,960 --> 00:06:11,550
ten un punteiro lexítimo para adiante
e un punteiro lexítimo para atrás,

133
00:06:11,550 --> 00:06:14,460
lexítima punteiro anterior e seguinte.

134
00:06:14,460 --> 00:06:16,530
De novo, se está a traballar
coas extremidades, vostede

135
00:06:16,530 --> 00:06:18,500
precisa para xestionar os
lixeiramente diferente,

136
00:06:18,500 --> 00:06:19,570
e nós non estamos indo a
falar sobre iso agora.

137
00:06:19,570 --> 00:06:21,319
Pero pode, probabelmente,
descubrir o que precisa

138
00:06:21,319 --> 00:06:24,610
por facer só por ver este vídeo.

139
00:06:24,610 --> 00:06:28,910
>> Entón, nós temos illado X. X é o nó
que quere eliminar da lista.

140
00:06:28,910 --> 00:06:30,140
O que imos facer?

141
00:06:30,140 --> 00:06:32,800
En primeiro lugar, necesitamos reorganizar
os punteiros fóra.

142
00:06:32,800 --> 00:06:35,815
Necesitamos reorganizar
9 do próximo para ir máis de 13

143
00:06:35,815 --> 00:06:38,030
e apuntan 10-- que
é o que acabamos de facer.

144
00:06:38,030 --> 00:06:41,180
E tamén necesitamos
reorganizar 10 Anterior

145
00:06:41,180 --> 00:06:44,610
para ligar a 9 en vez de apuntar 13.

146
00:06:44,610 --> 00:06:46,490
>> Entón, de novo, este foi o
diagrama para comezar.

147
00:06:46,490 --> 00:06:47,730
Esta foi a nosa cadea.

148
00:06:47,730 --> 00:06:51,027
Necesitamos ir máis de 13,
pero precisamos tamén preservar

149
00:06:51,027 --> 00:06:52,110
a integridade da lista.

150
00:06:52,110 --> 00:06:54,680
Non quere perder ningún
información en ambas as direccións.

151
00:06:54,680 --> 00:06:59,620
Entón, necesitamos reorganizar
os punteiros coidadosamente

152
00:06:59,620 --> 00:07:02,240
así que non romper a cadea en todo.

153
00:07:02,240 --> 00:07:05,710
>> Así, podemos dicir 9 Seguinte punteiro
apunta para o mesmo lugar

154
00:07:05,710 --> 00:07:08,040
que trece Seguinte
punteiro apunta agora.

155
00:07:08,040 --> 00:07:10,331
Porque somos eventualmente
Vai querer ir máis de 13.

156
00:07:10,331 --> 00:07:13,750
Así, onde queira 13 puntos seguinte,
quere nove para apuntar alí no seu lugar.

157
00:07:13,750 --> 00:07:15,200
Entón é iso.

158
00:07:15,200 --> 00:07:20,370
E entón onde queira que 13 puntos de volta
para o que vén antes de 13,

159
00:07:20,370 --> 00:07:24,800
queremos 10 para apuntar
para que, no canto de 13.

160
00:07:24,800 --> 00:07:29,290
Agora conta, se seguir
as frechas, podemos caer 13

161
00:07:29,290 --> 00:07:32,380
sen realmente perder calquera información.

162
00:07:32,380 --> 00:07:36,002
Nós mantivemos a integridade da lista,
movéndose para a adiante e cara atrás.

163
00:07:36,002 --> 00:07:38,210
E entón podemos só sorte
de limpa-lo un pouco

164
00:07:38,210 --> 00:07:40,930
tirando a lista xuntos.

165
00:07:40,930 --> 00:07:43,270
Entón, nós rearranjado o
punteiros en ambos os dous lados.

166
00:07:43,270 --> 00:07:46,231
E entón nós liberou o X
nó que contiña 13,

167
00:07:46,231 --> 00:07:47,480
e non romper a cadea.

168
00:07:47,480 --> 00:07:50,980
Por iso, fixemos boa.

169
00:07:50,980 --> 00:07:53,000
>> Nota final aquí en listas ligadas.

170
00:07:53,000 --> 00:07:55,990
Así, ambos singly- e dobremente ligada
listas, como vimos,

171
00:07:55,990 --> 00:07:58,959
soporte inserción realmente eficiente
e eliminación de elementos.

172
00:07:58,959 --> 00:08:00,750
Pode moi ben facer
lo en tempo constante.

173
00:08:00,750 --> 00:08:03,333
O que temos que facer para eliminar
un elemento só un segundo atrás?

174
00:08:03,333 --> 00:08:04,440
Nós cambiamos un punteiro.

175
00:08:04,440 --> 00:08:05,920
Nós nos cambiamos outro punteiro.

176
00:08:05,920 --> 00:08:07,915
Nós liberado x-- levou tres operacións.

177
00:08:07,915 --> 00:08:14,500
Sempre leva tres operacións para
eliminar que node-- para liberar un nó.

178
00:08:14,500 --> 00:08:15,280
>> Como é que imos introducir?

179
00:08:15,280 --> 00:08:17,280
Ben, nós somos só sempre
adherencia a principios

180
00:08:17,280 --> 00:08:19,400
se estamos introducindo de forma eficiente.

181
00:08:19,400 --> 00:08:21,964
Entón, necesitamos rearrange--
dependendo se é

182
00:08:21,964 --> 00:08:24,380
un singly- ou dobremente ligada
lista, nós pode ter facer tres

183
00:08:24,380 --> 00:08:26,824
ou como máximo catro operacións.

184
00:08:26,824 --> 00:08:28,365
Pero, de novo, sempre tres ou catro.

185
00:08:28,365 --> 00:08:30,531
Non importa cantas
elementos están na nosa lista,

186
00:08:30,531 --> 00:08:33,549
sempre tres ou catro operations--
así como a eliminación sempre

187
00:08:33,549 --> 00:08:35,320
tres ou catro operacións.

188
00:08:35,320 --> 00:08:36,919
É tempo constante.

189
00:08:36,919 --> 00:08:38,169
Entón, iso é realmente grande.

190
00:08:38,169 --> 00:08:40,620
>> Con matrices, que estaban facendo
algo así como ordenación por inserción.

191
00:08:40,620 --> 00:08:44,739
Probablemente recordar que a inserción
tipo non é un algoritmo de tempo constante.

192
00:08:44,739 --> 00:08:46,030
É realmente moi caro.

193
00:08:46,030 --> 00:08:48,840
Entón, iso é moito mellor para a inserción.

194
00:08:48,840 --> 00:08:51,840
Pero como eu mencionen no
illadamente conectado lista de vídeos,

195
00:08:51,840 --> 00:08:54,030
temos unha desvantaxe aquí tamén, non?

196
00:08:54,030 --> 00:08:57,580
Perdemos a capacidade de
acceder ao azar elementos.

197
00:08:57,580 --> 00:09:02,310
Non podemos dicir, quero elemento número catro
ou o número do elemento 10 dunha lista ligada

198
00:09:02,310 --> 00:09:04,990
Do mesmo xeito que podemos
facelo con unha matriz

199
00:09:04,990 --> 00:09:08,630
ou podemos só directamente índice
en elemento da nosa matriz.

200
00:09:08,630 --> 00:09:10,930
>> E así tentar atopar un
un elemento en lista-- ligada

201
00:09:10,930 --> 00:09:15,880
a investigación é importante--
pode agora ter tempo lineal.

202
00:09:15,880 --> 00:09:18,330
Como a lista está máis tempo,
pode dar un paso adicional

203
00:09:18,330 --> 00:09:22,644
para cada elemento da lista do
a fin de atopar o que estamos buscando.

204
00:09:22,644 --> 00:09:23,560
Polo tanto, hai trade-offs.

205
00:09:23,560 --> 00:09:25,780
Hai un pouco de un pro
e con elemento aquí.

206
00:09:25,780 --> 00:09:29,110
>> E listas dobremente vinculadas non o son
último tipo de combinación de estrutura de datos

207
00:09:29,110 --> 00:09:32,840
que nós imos falar sobre,
levando todo o edificio básico

208
00:09:32,840 --> 00:09:34,865
bloques de montar un C.

209
00:09:34,865 --> 00:09:37,900
Porque, en realidade, podemos
incluso facer mellor que iso

210
00:09:37,900 --> 00:09:41,970
para crear unha estrutura de datos que
pode ser capaz de buscar

211
00:09:41,970 --> 00:09:43,360
na constante de tempo demasiado.

212
00:09:43,360 --> 00:09:46,080
Pero máis sobre iso noutro vídeo.

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

214
00:09:47,150 --> 00:09:49,050
Este é CS50.

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