[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.