[Powered by Google Translate] У програмуванні, ми часто повинні представляти списки значень, такі як імена студентів в розділі або їх результати на останній вікторини. 

У мові C, заявив масиви можуть бути використані для зберігання списків. Легко перерахувати елементи списку зберігаються в масиві, і якщо вам потрібно отримати доступ або змінити го елементу списку для деякого довільного індексу I, що може бути зроблено в постійному часу, але масиви мають недоліки. 

Коли ми оголосимо їх, ми зобов'язані сказати, фронт, як вони великі, тобто, скільки елементів вони можуть зберігати і наскільки великий ці елементи, які визначаються їх типом. Наприклад, внутр обр (10) може зберігати 10 пунктів , Які є розмір Int. 

Ми не можемо змінити розмір масиву після декларації. Ми повинні створити новий масив, якщо ми хочемо зберегти кілька елементів. Причина цього обмеження в тому, що існує наша Програма зберігає весь масив як безперервний шматок пам'яті. Кажуть, що це буфер, де ми зберігали в нашому масиві. Там можуть бути й інші змінні розташований в безпосередній близькості до масиву в пам'яті, тому ми не можемо просто зробити масиву більше. 

Іноді ми хотіли б торгувати швидкий доступ до даних масиву швидкості для трохи більше гнучкості. Введіть зв'язаний список, інша основна структура даних Ви може бути не так добре знайомі. На високому рівні, Зв'язаний список зберігає дані в послідовність вузлів , Які пов'язані один з одним посиланнями, звідси і назва «зв'язаний список. Як ми побачимо, ця різниця в дизайні призводить до різних переваги і недоліки ніж масив. 

Ось код C з дуже простої зв'язаний список цілих чисел. Ви бачите, що ми представляємо кожному вузлу У списку, як структура, яка містить 2 речі, ціле для зберігання під назвою «Вал» і посилання на наступний вузол в списку , Які ми представляємо в якості покажчика називається "Далі". Таким чином, ми можемо відстежити весь список за допомогою всього одного покажчика на вузлі 1, і тоді ми зможемо виконати наступні покажчики на 2-й вузол, до 3-го вузлу, до 4-му вузлу, і так далі, поки ми не отримаємо до кінця списку. 

Ви могли б дивитися 1 Перевага цього є на статичну структуру масиву - з пов'язаного списку, нам не потрібно великий шматок пам'яті в цілому. Перший вузол списку могли б жити на цьому місці в пам'яті, і 2-го вузла може бути на всьому шляху сюди. Ми можемо дістатися до всіх вузлів, незалежно від того, де в пам'яті вони є, тому що, починаючи з першого вузла, наступного покажчика кожного вузла говорить нам точно, куди йти далі. 

Крім того, ми не повинні говорити фронт наскільки великий зв'язаний список буде так, як ми робимо з статичні масиви, так як ми можемо продовжувати додавати вузли в список тих пір, поки є вільне місце десь у пам'яті для нових вузлів. Тому, пов'язаних списків можна легко змінити розмір динамічно. Скажімо, пізніше в програмі, нам потрібно додати кілька вузлів в нашому списку. Для вставки нового вузла в нашому списку на льоту, все, що нам потрібно зробити, це виділити пам'ять для цього вузла, хлопнути в значенні даних, , А потім помістити його там, де ми хочемо шляхом коригування відповідних покажчиків. 

Наприклад, якщо ми хочемо розмістити вузол між 2-й і 3-й вузли списку,  Ми не повинні були б рухатися 2-й або 3-й вузли на всіх. Сказати, що ми червоні вставки цих вузлів. Все, що ми повинні були б зробити, це встановити наступний покажчик нового вузла вказувати на 3-му вузлі , А потім перемонтувати наступний покажчик 2-го вузла вказують на нашому новому вузлі. Таким чином, ми можемо змінити розмір наших списків на льоту З нашого комп'ютера не покладатися на індексацію, а на зв'язку за допомогою покажчиків для їх зберігання. 

Тим не менш, недолік зв'язані списки є те, що, на відміну від статичного масиву, Комп'ютер не може просто стрибнути в середину списку. Так як комп'ютер повинен відвідати кожен вузол у зв'язаному списку щоб дістатися до наступного, це займе більше часу, щоб знайти конкретний вузол ніж це було б в масиві. Щоб пройти весь список займає час, пропорційне до довжини списку, або O (N) в асимптотичних позначень. У середньому, досягнувши будь-якого вузла також займає час, пропорційне до н. 

Тепер, давайте насправді написати код , Який працює зі зв'язаними списками. Скажімо, ми хочемо зв'язаний список цілих чисел. Ми можемо уявити вузол в наш список ще раз як структура з 2 полями, Ціле число називається "Вал" і наступний покажчик на наступний вузол списку. Ну, здається досить простим. 

Скажімо, ми хочемо написати функцію, який проходить по списку і виводить Значення, яке зберігається в останній вузол списку. Ну, значить, ми повинні будемо пройти всі вузли в списку щоб знайти останнього, але так як ми не додаємо або видаляючи, ми не хочемо змінити Внутрішня структура наступного покажчика в списку. 

Отже, нам знадобиться покажчик спеціально для обходу який ми називаємо «гусеничні». Вона буде сканувати через всі елементи списку , Виконавши наступний ланцюжок покажчиків. Все, що ми зберегли це покажчик на вузол 1, або «голови» списку. Керівник вказує на перший вузол. Це типу покажчик-на-вузла. 

Щоб отримати фактичний перший вузол у списку, ми повинні разименованія цього покажчика, але перш ніж ми зможемо разименовать це, нам потрібно перевірити якщо покажчик є нульовим першим. Якщо він порожній, список порожній, і ми повинні надрукувати повідомлення, що, оскільки список порожній, немає останнього вузла. Але, скажімо, в список не порожній. Якщо це не так, то ми повинні повзти через весь список поки ми не отримаємо на останній вузол списку, і як ми можемо сказати, якщо ми дивимося на останній вузол у списку? 

Ну, якщо наступний покажчик вузла є нульовим, Ми знаємо, що ми знаходимося в кінці З останнім наступний покажчик матиме наступний вузол в списку, щоб вказувати. Це гарна практика, щоб завжди мати наступний покажчик останнього вузла ініціалізований до нуля мати стандартизований майно, яке попереджає нас, коли ми досягли кінця списку. 

Таким чином, якщо гусеничних → наступний порожній, пам'ятайте, що стрілка синтаксис ярлик для разименованія покажчик на структуру, то доступ свого наступного поля еквівалентні ніяково: (* Гусеничні). Наступний. Як тільки ми виявили, що останній вузол, ми хочемо надрукувати гусеничних → Вал, значення в поточному вузлі який ми знаємо, це останній. В іншому випадку, якщо ми ще не в останню вузла в списку, ми повинні перейти до наступного вузла в списку і переконайтеся, що це остання. Щоб зробити це, ми просто встановити наш сканер покажчик , Щоб вказати на наступне значення поточного вузла, , Тобто на наступний вузол в списку. Це робиться шляхом установки Гусеничний = гусеничних → Далі. Тоді ми повторюємо цей процес, з петлею наприклад, поки ми не знайдемо останній вузол. Так, наприклад, якщо гусеничних вказував на голову, Покладемо гусеничних вказують на гусеничному → наступному, який так само, як у наступному полі 1-го вузла. Отже, тепер наш сканер вказує на другому вузлі, і, знову ж таки, ми повторюємо це з петлею, поки ми не знайшли останнього вузла, тобто, де наступний покажчик вузла вказує на нуль. І у нас це є, ми знайшли останнього вузла в списку, а щоб надрукувати його значення, ми просто використовуємо гусеничних → знач. 

Переміщення не так вже погано, але те, що про установку? Припустимо, ми хочемо, щоб вставити число в 4-й позиції У цілого списку. Тобто між поточним 3 і 4 вузлів. Знову ж таки, у нас є для перегляду списку тільки дістатися до 3-го елемента, один ми вставка після. Таким чином, ми створюємо гусеничних покажчик знову пройти списку, перевірити, якщо наша голова покажчик є нульовим, і якщо це не так, вказати наш сканер покажчик на головному вузлі. Отже, ми на 1-м елементом. Ми повинні йти вперед ще 2 елементи перш ніж ми зможемо вставити, тому ми можемо використовувати для циклу Int я = 1; I <3, Я + + і в кожній ітерації циклу, просувати наш сканер покажчик вперед на 1 вузол , Перевіряючи, якщо наступне поле поточного вузла є нульовим, і якщо це не так, перемістіть наш сканер покажчик на наступний вузол , Встановивши його рівним наступний покажчик поточного вузла. Таким чином, оскільки наш цикл говорить, щоб зробити це в два рази, ми досягли 3-го вузла, і як тільки наш сканер покажчик досяг вузол після який ми хочемо вставити наш новий ціле число, Як ми насправді вставка? 

Ну, наше нове ціле повинен бути вставлений в список як частину своєї власної структури вузла, так як це дійсно послідовність вузлів. Отже, давайте зробимо новий покажчик на вузол називається "new_node" і встановити його, щоб вказати на пам'ять, що ми зараз виділити в купі для самого вузла, пам'яті і скільки нам потрібно виділити? Ну, розмір вузла, і ми хочемо встановити його вал поле число, яке ми хочемо вставити. Скажімо, 6. Тепер вузол містить наш ціле значення. Це також гарна практика для ініціалізації наступного поля нового вузла вказують на нуль, Але що тепер? 

Ми повинні змінити внутрішню структуру списку і на наступний покажчиків, що містяться в існуючих списку 3 і 4 вузлів. З наступного покажчика визначають порядок списку, і так як ми вставки нашого нового вузла прямо в середині списку, вона може бути трохи складніше. Це тому, що пам'ятаю, наш комп'ютер тільки знає розташування вузлів в списку через чергового покажчики зберігаються в попередніх вузлах. Таким чином, якщо ми коли-небудь втратив будь-яку з цих місць, кажуть, змінивши одну з наступних покажчиків в нашому списку Наприклад, сказати, що ми змінилися Наступні 3-го вузла поля вказати на деякі вузла сюди. Ми були б не пощастило, тому що ми не хочемо є ідеї, де знайти інші частини списку, і це, очевидно, дуже погано. Таким чином, ми повинні бути дуже обережні, про порядок , В якій ми маніпулювати нашим наступним покажчиків під час установки. 

Таким чином, щоб спростити це, давайте скажемо, що наші перші 4 вузлів називаються A, B, C, і D, зі стрілками, що представляє ланцюжок покажчиків , Які з'єднують вузли. Отже, нам потрібно вставити наш новий вузол між вузлами C і D. Дуже важливо робити це в правильному порядку, і я покажу вам, чому. 

Давайте подивимося на неправильний спосіб зробити це першим. Гей, ми знаємо, що новий вузол повинен прийти відразу після C, так що давайте встановити наступний покажчик Сі вказують на new_node. Ладно, здається, все в порядку, ми просто повинні закінчити зараз, робить наступний пункт покажчик на новий вузол в D, Але почекайте, як ми можемо це зробити? Єдине, що може сказати нам, де D був, був наступний покажчик Раніше зберігається в C, але ми просто переписали, що покажчик щоб вона вказувала на новий вузол, таким чином, ми більше не мають поняття, де D знаходиться в пам'яті, і ми втратили іншу частину списку. Не годиться. 

Отже, як ми робимо це правильно? По-перше, вказати наступний покажчик на новий вузол за адресою D. Тепер, як новий вузол і C в наступному покажчики вказують на той же вузол, D, але це нормально. Тепер ми можемо відзначити наступний покажчик C на новому вузлі. Таким чином, ми зробили це без втрати даних. У коді З поточного вузла що обхід покажчик гусеничних вказує на, і D представляє вузол, на який вказує наступне поле поточного вузла, або гусеничному → Далі. Таким чином, ми спочатку встановити наступний покажчик нового вузла вказують на гусеничному → наступному, Точно так само ми сказали, наступний покажчик повинен new_node вказують на D на малюнку. Тоді, ми можемо встановити наступний покажчик поточного вузла на нашому новому вузлі, так само, як ми повинні були чекати до точки С, щоб new_node на кресленні. Тепер все в порядку, і ми не втратили відстеження будь-яких даних, і ми змогли просто дотримуватися нашого нового вузла в середині списку без перебудови все це або навіть переміщення будь-яких елементів то, як ми повинні були б з фіксованою довжиною масиву. 

Отже, зв'язані списки є основними, але важливо, динамічні структури даних які мають як переваги, так і недоліки в порівнянні з масивів та інших структур даних, і, як це часто буває в комп'ютерній науці, важливо знати, коли використовувати кожен інструмент, так що ви можете вибрати правильний інструмент для правильної роботи. 

Для отримання додаткової практикою, спробувати написати функцій видалити вузли із зв'язаного списку - не забувайте бути обережними про порядок, в якому ви переставити Ваш наступний покажчик, щоб не втратити шматок вашого списку - або функція для підрахунку вузли у зв'язаному списку, або весело один, щоб змінити порядок всі вузли у зв'язаному списку. 

Мене звуть Джексон Steinkamp, ​​це CS50.