[Powered by Google Translate] אין פּראָגראַממינג, מיר אָפֿט דאַרפֿן צו פאָרשטעלן רשימות פון וואַלועס, אַזאַ ווי די נעמען פון סטודענטן אין אַ אָפּטיילונג אָדער זייער סקאָרז אויף די לעצט ויספרעג. 

אין די C שפּראַך, דערקלערט ערייז קענען זייַן געניצט צו קראָם רשימות. עס ס גרינג צו ינומערייט די יסודות פון אַ רשימה סטאָרד אין אַ מענגע, און אויב איר דאַרפֿן צו צוטריט אָדער מאָדיפיצירן די יטה רשימה עלעמענט פֿאַר עטלעכע אַרביטראַריש אינדעקס איך, וואָס קענען זייַן געטאן אין קעסיידערדיק צייַט, אָבער ערייז האָבן דיסאַדוואַנטידזשיז, אויך. 

ווען מיר דערקלערן זיי, מיר רע פארלאנגט צו זאָגן אַרויף פראָנט ווי גרויס זיי זענען, וואָס איז, ווי פילע יסודות זיי קענען קראָם און ווי גרויס די יסודות זענען, וואָס איז באשלאסן לויט זייער טיפּ. פֿאַר בייַשפּיל, ינט אַרר (10) קענען קראָם 10 זאכן וואָס זענען די גרייס פון אַ ינט. 

מיר קענען נישט טוישן אַ מענגע ס גרייס נאָך דערקלערונג. מיר האָבן צו מאַכן אַ נייַ מענגע אויב מיר ווילן צו קראָם מער יסודות. די סיבה דעם באַגרענעצונג יגזיסץ איז אַז אונדזער פּראָגראַם סטאָרז די גאנצע מענגע ווי אַ קאַנטיגיואַס פּייַדע פון ​​זכּרון. זאָגן דעם איז די באַפער ווו מיר סטאָרד אין אונדזער מענגע. עס זאל זייַן אנדערע וועריאַבאַלז ליגן רעכט ווייַטער צו די מענגע אין זכּרון, אַזוי מיר קענען ניט נאָר מאַכן די מענגע ביגער. 

מאל מיר 'ד ווי צו האַנדל די מענגע ס פעסט דאַטן צוטריט גיכקייַט פֿאַר אַ ביסל מער בייגיקייַט. אַרייַן די לינגקט רשימה, אן אנדער יקערדיק דאַטן סטרוקטור איר זאל ניט זייַן ווי באַקאַנט מיט. אין אַ הויך מדרגה, אַ לינגקט רשימה סטאָרז דאַטן אין אַ סיקוואַנס פון נאָודז וואָס זענען פארבונדן צו יעדער אַנדערער מיט לינקס, דערפאר די נאָמען 'לינגקט רשימה.' ווי מיר וועט זען, דעם חילוק אין פּלאַן פירט צו פאַרשידענע אַדוואַנידזשיז און דיסאַדוואַנטידזשיז ווי אַ מענגע. 

דאָ ס עטלעכע C קאָד פֿאַר אַ זייער פּשוט לינגקט רשימה פון ינטאַדזשערז. איר קענען זען אַז מיר האָבן רעפּריזענטיד יעדער נאָדע אין די רשימה ווי אַ סטרוקט וואָס כּולל 2 זאכן, אַ ינטעגער צו קראָם גערופן 'וואַל' און אַ לינק צו די ווייַטער נאָדע אין דער רשימה וואָס מיר פאָרשטעלן ווי אַ טייַטל גערופן 'ווייַטער.' דעם וועג, מיר קענען שפּור די גאנצע רשימה מיט נאָר אַ איין טייַטל צו די 1 נאָדע, און דעמאָלט מיר קענען נאָכגיין די ווייַטער פּוינטערז צו די 2 נאָדע, צו די 3 נאָדע, צו די 4 נאָדע, און אַזוי אויף, ביז מיר באַקומען צו דעם סוף פון דער רשימה. 

איר זאל זייַן ביכולת צו זען 1 מייַלע דאָס האט איבער די סטאַטיק מענגע סטרוקטור - מיט אַ לינגקט רשימה, מיר טאָן ניט דאַרפֿן אַ גרויס פּייַדע פון ​​זכּרון בעסאַכאַקל. די 1 נאָדע פון ​​דער רשימה קען לעבן אין דעם אָרט אין זכּרון, און די 2 נאָדע קען זייַן אַלע די וועג איבער דאָ. מיר קענען באַקומען צו אַלע די נאָודז קיין ענין ווו אין זכּרון זיי זענען, ווייַל סטאַרטינג אין די 1 נאָדע, יעדער נאָדע ס ווייַטער טייַטל דערציילט אונדז פּונקט ווו צו גיין ווייַטער. 

אַדדיטיאָנאַללי, מיר טאָן ניט האָבן צו זאָגן אַרויף פראָנט ווי גרויס אַ לינגקט רשימה וועט זייַן די וועג מיר טאָן מיט סטאַטיק ערייז, זינט מיר קענען האַלטן אַדינג נאָודז צו אַ רשימה ווי לאַנג ווי עס ס 'פּלאַץ ערגעץ אין זכּרון פֿאַר נייַ נאָודז. דעריבער, לינגקט רשימות זענען גרינג צו רעסיזע דינאַמיקאַללי. זאָגן, שפּעטער אין די פּראָגראַם מיר דאַרפֿן צו לייגן מער נאָודז אין אונדזער רשימה. צו אַרייַנלייגן אַ נייַ נאָדע אין אונדזער רשימה אויף די פליען, אַלע מיר האָבן צו טאָן איז אַלאַקייט זכּרון פֿאַר אַז נאָדע, פּלאַפּ אין דער דאַטע ווערט, און דעמאָלט אָרט עס ווו מיר ווילן דורך אַדזשאַסטינג די צונעמען פּוינטערז. 

פֿאַר בייַשפּיל, אויב מיר געוואלט צו שטעלן אַ נאָדע אין צווישן די 2 און 3 נאָודז פון דער רשימה,  מיר וואָלט ניט האָבן צו באַוועגן די 2 אָדער 3 נאָודז בייַ אַלע. זאָגן מיר רע ינסערטינג דעם רויט נאָדע. אַלע מיר 'ד האָבן צו טאָן איז שטעלן די נייַ נאָדע ס ווייַטער טייַטל צו פונט צו די 3 נאָדע און דעמאָלט ריווייער די 2 נאָדע ס ווייַטער טייַטל צו פונט צו אונדזער נייַ נאָדע. אַזוי, מיר קענען רעסיזע אונדזער רשימות אויף די פליען זינט אונדזער קאָמפּיוטער טוט נישט פאַרלאָזנ אויף ינדעקסינג, אָבער אלא אויף פֿאַרבינדונג ניצן פּוינטערז צו קראָם זיי. 

אבער, אַ כיסאָרן פון לינגקט רשימות איז וואָס, ניט ענלעך אַ סטאַטיק מענגע, דער קאָמפּיוטער קענען ניט נאָר שפּרינגען צו די מיטל פון דער רשימה. זינט די קאָמפּיוטער האט צו באַזוכן יעדער נאָדע אין די לינגקט רשימה צו באַקומען צו דעם ווייַטער איינער, עס ס געגאנגען צו נעמען מער צו געפֿינען אַ באַזונדער נאָדע ווי עס וואָלט אין אַ מענגע. צו דורך די גאנצע רשימה נעמט צייַט פּראַפּאָרשאַנאַל צו די לענג פון די רשימה, אָדער אָ (N) אין אַסימפּטאָטיק נאָוטיישאַן. אויף דורכשניטלעך, ריטשינג קיין נאָדע אויך נעמט צייַט פּראַפּאָרשאַנאַל צו ען. 

איצט, לאָזן ס פאקטיש שרייַבן עטלעכע קאָד וואָס אַרבעט מיט לינגקט רשימות. זאל ס זאָגן מיר ווילן אַ לינגקט רשימה פון ינטאַדזשערז. מיר קענען פאָרשטעלן אַ נאָדע אין אונדזער רשימה ווידער ווי אַ סטרוקט מיט 2 פעלדער, אַ ינטעגער ווערט גערופן 'וואַל' און אַ ווייַטער טייַטל צו דער ווייַטער נאָדע פון ​​דער רשימה. נו, מיינט פּשוט גענוג. 

זאל ס זאָגן מיר ווילן צו שרייַבן אַ פֿונקציע וואָס טראַווערסעס דער רשימה און פּרינץ אויס די ווערט סטאָרד אין די לעצטע נאָדע פון ​​דער רשימה. נו, אַז מיטל מיר וועט דאַרפֿן צו דורך אַלע די נאָודז אין דער רשימה צו געפֿינען די לעצטע איין, אָבער זינט מיר ניטאָ ניט אַדינג אָדער דיליטינג עפּעס, מיר טאָן נישט וועלן צו טוישן דער אינערלעכער סטרוקטור פון דער ווייַטער פּוינטערז אין די רשימה. 

אַזוי, מיר וועט דאַרפֿן אַ טייַטל ספּאַסיפיקלי פֿאַר טראַווערסאַל וואָס מיר וועט רופן 'קריכער.' עס וועט קריכן דורך אַלע די יסודות פון דער רשימה דורך פאלגענדע די קייט פון ווייַטער פּוינטערז. אַלע מיר האָבן סטאָרד איז אַ טייַטל צו די 1 נאָדע, אָדער 'קאָפּ' פון די רשימה. קאָפּ פונקטן צו די 1 נאָדע. עס ס פון טיפּ טייַטל-צו-נאָדע. 

צו באַקומען די פאַקטיש 1 נאָדע אין דער רשימה, מיר האָבן צו דערעפערענסע דעם טייַטל, אָבער איידער מיר קענען דערעפערענסע עס, מיר דאַרפֿן צו טשעק אויב די טייַטל איז נאַל ערשטער. אויב עס ס נאַל, די רשימה איז ליידיק, און מיר זאָל דרוקן אויס אַ אָנזאָג אַז, ווייַל די רשימה איז ליידיק, עס איז קיין לעצט נאָדע. אבער, לאָזן ס זאָגן די רשימה איז ניט ליידיק. אויב עס ס נישט, דעמאָלט מיר זאָל קריכן דורך די גאנצע רשימה ביז מיר באַקומען צו די לעצטע נאָדע פון ​​דער רשימה, און ווי קענען מיר זאָגן אויב מיר רע קוקן אין די לעצטע נאָדע אין דער רשימה? 

נו, אויב אַ נאָדע ס ווייַטער טייַטל איז נאַל, מיר וויסן מיר ניטאָ בייַ די סוף זינט די לעצטע ווייַטער טייַטל וואָלט האָבן קיין ווייַטער נאָדע אין דער רשימה צו פונט צו. עס ס גוט פיר צו שטענדיק האַלטן די לעצטע נאָדע ס ווייַטער טייַטל ינישאַלייזד צו נאַל צו האָבן אַ סטאַנדערדייזד פאַרמאָג וואָס אַלערץ אונדז ווען מיר ווע ריטשט די סוף פון די רשימה. 

אַזוי, אויב קריכער → ווייַטער איז נאַל, געדענקען אַז די פייַל סינטאַקס איז אַ דורכוועג פֿאַר דערעפערענסינג אַ טייַטל צו אַ סטרוקט, דעמאָלט אַקסעסינג זייַן ווייַטער פעלד עקוויוואַלענט צו דעם ומגעלומפּערט: (* קריכער). ווייַטער. אַמאָל מיר ווע געפונען די לעצטע נאָדע, מיר ווילן צו דרוקן קריכער → וואַל, די ווערט אין דער קראַנט נאָדע וואָס מיר וויסן איז די לעצטע איינער. אַנדערש, אויב מיר רע נישט נאָך אין די לעצטע נאָדע אין דער רשימה, מיר האָבן צו באַוועגן אויף צו דער ווייַטער נאָדע אין דער רשימה און טשעק אויב אַז ס 'די לעצטע איינער. צו טאָן דאָס, מיר נאָר שטעלן אונדזער קריכער טייַטל צו פונט צו די קראַנט נאָדע ס ווייַטער ווערט, וואָס איז, דער ווייַטער נאָדע אין די רשימה. דאס איז געטאן דורך באַשטעטיקן קריכער = קריכער → ווייַטער. דעמאָלט מיר איבערחזרן דעם פּראָצעס, מיט אַ שלייף פֿאַר בייַשפּיל, ביז מיר געפֿינען די לעצטע נאָדע. אַזוי, פֿאַר בייַשפּיל, אויב קריכער איז פּוינטינג צו קאָפּ, מיר שטעלן קריכער צו פונט צו קריכער → ווייַטער, וואָס איז די זעלבע ווי דער ווייַטער פעלד פון די 1 נאָדע. אַזוי, איצט אונדזער קריכער איז פּוינטינג צו די 2 נאָדע, און, ווידער, מיר איבערחזרן דעם מיט אַ שלייף, ביז מיר ווע געפונען די לעצטע נאָדע, וואָס איז, ווו די נאָדע ס ווייַטער טייַטל איז פּוינטינג צו נאַל. און עס מיר האָבן עס, מיר ווע געפונען די לעצטע נאָדע אין דער רשימה, און צו דרוקן זייַן ווערט, מיר נאָר נוצן קריכער → וואַל. 

טראַווערסינג איז נישט אַזוי שלעכט, אָבער וואָס וועגן ינסערטינג? לעץ זאָגן מיר ווילן צו אַרייַנלייגן אַ ינטעגער אין די 4 שטעלע אין אַ ינטעגער רשימה. וואָס איז צווישן די קראַנט 3 און 4 נאָודז. ווידער, מיר האָבן צו דורך דער רשימה נאָר צו באַקומען צו די 3 עלעמענט, די איין מיר רע ינסערטינג נאָך. אַזוי, מיר שאַפֿן אַ קריכער טייַטל ווידער צו דורך דער רשימה, טשעק אויב אונדזער קאָפּ טייַטל איז נאַל, און אויב עס ס נישט, פונט אונדזער קריכער טייַטל אין די קאָפּ נאָדע. אַזוי, מיר ניטאָ בייַ די 1 עלעמענט. מיר האָבן צו גיין פאָרויס 2 מער יסודות איידער מיר קענען אַרייַנלייגן, אַזוי מיר קענען נוצן אַ פֿאַר שלייף ינט איך = 1; איך <3; איך + + און אין יעדער יטעראַטיאָן פון די שלייף, שטייַגן אונדזער קריכער טייַטל פאָרויס דורך 1 נאָדע דורך קאָנטראָלירונג אויב די קראַנט נאָדע ס ווייַטער פעלד איז נאַל, און אויב עס ס נישט, מאַך אונדזער קריכער טייַטל צו דער ווייַטער נאָדע דורך באַשטעטיקן עס גלייַך צו די קראַנט נאָדע ס ווייַטער טייַטל. אַזוי, זינט אונדזער פֿאַר שלייף זאגט צו טאָן וואָס צוויי מאָל, מיר ווע ריטשט די 3 נאָדע, און אַמאָל אונדזער קריכער טייַטל האט ריטשט די נאָדע נאָך וואָס מיר ווילן צו אַרייַנלייגן אונדזער נייַ ינטעגער, ווי טאָן מיר פאקטיש טאָן די ינסערטינג? 

נו, אונדזער נייַ ינטעגער האט צו זייַן ינסערטאַד אין דער רשימה ווי טייל פון זייַן אייגן נאָדע סטרוקט, זינט דעם איז טאַקע אַ סיקוואַנס פון נאָודז. אַזוי, לאָזן ס מאַכן אַ נייַ טייַטל צו נאָדע גערופן 'נעוו_נאָדע,' און שטעלן אים צו פונט צו זכּרון אַז מיר איצט אַלאַקייט אויף די קופּע פֿאַר די נאָדע זיך, און ווי פיל זכּרון טאָן מיר דאַרפֿן צו אַלאַקייט? נו, די גרייס פון אַ נאָדע, און מיר וועלן צו שטעלן זייַן וואַל פעלד צו די ינטעגער אַז מיר ווילן צו אַרייַנלייגן. זאל ס זאָגן, 6. איצט, די נאָדע כּולל אונדזער ינטעגער ווערט. עס ס אויך גוט פיר צו ינישאַלייז די נייַ נאָדע ס ווייַטער פעלד צו פונט צו נאַל, אָבער איצט וואָס? 

מיר האָבן צו טוישן די ינערלעך סטרוקטור פון דער רשימה און די ווייַטער פּוינטערז קאַנטיינד אין דער רשימה ס שאַפֿן 3 און 4 נאָודז. זינט דער ווייַטער פּוינטערז באַשטימען די סדר פון די רשימה, און זינט מיר רע ינסערטינג אונדזער נייַ נאָדע רעכט אין דער מיטן פון דער רשימה, עס קען זייַן אַ ביסל טריקי. דאס איז ווייַל, געדענקען, אונדזער קאָמפּיוטער בלויז ווייסט דעם אָרט פון נאָודז אין דער רשימה ווייַל פון די ווייַטער פּוינטערז סטאָרד אין די פֿריִערדיקע נאָודז. אַזוי, אויב מיר אלץ פאַרפאַלן שפּור פון קיין פון די לאָוקיישאַנז, זאָגן דורך טשאַנגינג איינער פון די ווייַטער פּוינטערז אין אונדזער רשימה, פֿאַר בייַשפּיל, זאָגן מיר געביטן די 3 נאָדע ס ווייַטער פעלד צו פונט צו עטלעכע נאָדע איבער דאָ. מיר 'ד ווערן אויס פון גליק, ווייַל מיר וואָלט ניט האָבן קיין געדאַנק ווו צו געפֿינען די מנוחה פון דער רשימה, און אַז ס 'דאָך טאַקע שלעכט. אַזוי, מיר האָבן צו זייַן טאַקע אָפּגעהיט וועגן די סדר אין וואָס מיר מאַניפּולירן אונדזער ווייַטער פּוינטערז בעשאַס ינסערשאַן. 

אַזוי, צו פאַרפּאָשעטערן דעם, לאָזן 'ס זאָגן אַז אונדזער ערשטער 4 נאָודז זענען גערופן א, ב, C, און די, מיט די אַראָוז רעפּריזענטינג די קייט פון פּוינטערז וואָס פאַרבינדן די נאָודז. אַזוי, מיר דאַרפֿן צו אַרייַנלייגן אונדזער נייַ נאָדע אין צווישן נאָודז C און די עס ס קריטיש צו טאָן עס אין די רעכט סדר, און איך וועט ווייַזן איר וואָס. 

זאל ס קוק בייַ די אומרעכט וועג צו טאָן עס ערשטער. היי, מיר וויסן די נייַ נאָדע האט צו קומען רעכט נאָך C, אַזוי לאָזן ס שטעלן C ס ווייַטער טייַטל צו פונט צו נעוו_נאָדע. אַלע רעכט, מיינט אָוקיי, מיר נאָר האָבן צו ענדיקן זיך איצט דורך מאכן די נייַ נאָדע ס ווייַטער טייַטל פונט צו די, אָבער וואַרטן, ווי קענען מיר טאָן וואָס? דער בלויז זאַך וואָס קען דערציילן אונדז ווו די איז געווען, איז דער ווייַטער טייַטל פריער סטאָרד אין C, אָבער מיר נאָר ריראָוט אַז טייַטל צו פונט צו די נייַ נאָדע, אַזוי מיר ניט מער האָבן קיין קלו ווו די איז אין זכּרון, און מיר ווע פאַרפאַלן די מנוחה פון די רשימה. נישט גוט אין אַלע. 

אַזוי, ווי טאָן מיר טאָן דעם רעכט? ערשטער, פונט די נייַ נאָדע ס ווייַטער טייַטל אין די איצט, ביידע די נייַ נאָדע ס און C ס ווייַטער פּוינטערז זענען פּוינטינג צו דער זעלביקער נאָדע, ד, אָבער אַז ס פייַן. איצט מיר קענען פונט C ס ווייַטער טייַטל אין די נייַ נאָדע. אַזוי, מיר ווע געטאן דעם אָן לוזינג קיין דאַטן. אין קאָד, C איז די קראַנט נאָדע אַז די טראַווערסאַל טייַטל קריכער איז פּוינטינג צו, און די איז רעפּריזענטיד דורך די נאָדע שפּיציק צו דורך די קראַנט נאָדע ס ווייַטער פעלד, אָדער קריכער → ווייַטער. אַזוי, מיר ערשטער שטעלן די נייַ נאָדע ס ווייַטער טייַטל צו פונט צו קריכער → ווייַטער, די זעלבע וועג מיר געזאגט נעוו_נאָדע ס ווייַטער טייַטל זאָל פונט צו די אין דעם געמעל. דעמאָלט, מיר קענען שטעלן דעם קראַנט נאָדע ס ווייַטער טייַטל צו אונדזער נייַ נאָדע, פּונקט ווי מיר האבן צו וואַרטן צו פונט C צו נעוו_נאָדע אין די צייכענונג. איצט אַלץ ס אין סדר, און מיר האבן נישט פאַרלירן שפּור פון קיין דאַטן, און מיר זענען ביכולת צו נאָר שטעקן אונדזער נייַ נאָדע אין די מיטן פון די רשימה אָן ריבילדינג די גאנצע זאַך אָדער אַפֿילו שיפטינג קיין יסודות די וועג מיר וואָלט האָבן געהאט צו מיט אַ פאַרפעסטיקט-לענג מענגע. 

אַזוי, לינגקט רשימות זענען אַ גרונט, אָבער וויכטיק, דינאַמיש דאַטן סטרוקטור וואָס האָבן ביידע אַדוואַנידזשיז און דיסאַדוואַנטידזשיז קאַמפּערד צו ערייז און אנדערע דאַטן סטראַקטשערז, און ווי איז אָפֿט דער פאַל אין קאָמפּיוטער וויסנשאַפֿט, עס ס וויכטיק צו וויסן ווען צו נוצן יעדער געצייַג, אַזוי איר קענען קלייַבן די רעכט געצייַג פֿאַר די רעכט אַרבעט. 

פֿאַר מער פיר, פּרובירן שרייבן פאַנגקשאַנז צו אויסמעקן נאָודז פון אַ לינגקט רשימה - געדענקען צו זייַן אָפּגעהיט וועגן די סדר אין וואָס איר ריעריינדזש דיין ווייַטער פּוינטערז צו ענשור אַז איר טאָן ניט פאַרלירן אַ פּייַדע פון ​​דיין רשימה - אָדער אַ פֿונקציע צו ציילן די נאָודז אין אַ לינגקט רשימה, אָדער אַ שפּאַס איינער, צו פאַרקערט די סדר פון אַלע פון ​​די נאָודז אין אַ לינגקט רשימה. 

מייַן נאָמען איז זשעקסאן סטעינקאַמפּ, דאָס איז קס50.