Односвязный список – это тип связанного списка, в котором данные можно читать в одном направлении, от головы (первого узла) к хвосту (концу или последнему узлу). Односвязные списки похожи на массивы, но они отличаются в том смысле, что если вам нужно получить доступ к 3-му элементу массива, то вы сможете получить прямой доступ, в то время как в связанном списке вам придется обходить каждый узел, пока вы не достигнете 3-го узла. Я не слишком много понимаю о памяти и о том, как эти структуры данных хранятся в памяти, но я попытаюсь объяснить то, что знаю. В любом массиве вам нужны последовательные слоты памяти, а в связанном списке они могут храниться в любом доступном слоте памяти с указателем на следующий узел.
Поэтому, что касается памяти, кажется, что связанные списки гораздо более эффективны с точки зрения памяти, чем массивы. Добавление и удаление узлов в связанном списке перезаписывает и устанавливает новые указатели на узлы и из них. Когда вы вставляете и удаляете из массивов, вам фактически приходится сдвигать и перемещать каждый элемент после вставки или удаления. За исключением добавления в конец массива, кажется, что это единственный случай, когда по производительности он выигрывает у связного списка. Теперь, зная это, я могу понять, почему связный список более эффективен в памяти и в зависимости от случая использования может показать большую производительность, чем массив (который я сейчас использую ежедневно / постоянно). Моя цель на ближайшее будущее – начать внедрять эти новые изученные структуры данных в мою кодовую базу. Нужно ли это, скорее всего нет, будет ли это кому-то интересно, нет (я сейчас работаю единственным разработчиком в своей команде…..), но это поможет мне лучше понять и продолжить мой путь обучения, да!!!!.
Лично я никогда не сталкивался с этим на собеседовании, но я думаю, что одним из наиболее распространенных и низкоуровневых вопросов, который кто-то задаст вам в какой-то момент вашей карьеры, будет разворачивание односвязного списка. Почему это важно? То есть, если это массив, я могу сделать Array.reverse() и бам, посмотрите на меня. Идея, как я понял, заключается в том, насколько хорошо вы знаете простейшую структуру данных и можете ли вы пройти и затем сохранить все узлы и значения в обратном порядке. Так что давайте сделаем это!!!!!!!!!
Я пошел дальше и создал структуру данных javascript Singly Linked List, чтобы лучше понять их. Ее можно найти здесь вместе со всеми другими структурами данных, которые я буду создавать со временем. SinglyLinkedList. Итак, если вы посмотрите на репозиторий, то увидите, что я добавил обратную функцию, которая позаботится об утверждении выше, но мы напечатаем его еще раз здесь. Я знаю, что вы можете делать это как итеративно, так и рекурсивно. Я собираюсь сделать это стандартным итеративным способом, и если вы посмотрите на мой класс на github, я делаю это с помощью цикла for, но здесь я заменю его на цикл while, потому что почему бы и нет.
function reverse(list) {
let node = list.head;
let previous = null;
let next = null;
while(node) {
next = node.next;
node.next = previous;
previous = node;
node = next;
}
return list;
}
Итак, я надеюсь, что все это или что-то из этого поможет вам в вашем росте как разработчика. Я бы сказал, что если вы пытаетесь втиснуть кучу знаний в очень короткий промежуток времени, особенно когда имеете дело с этой конкретной темой, я бы сказал воздержаться. Не торопитесь и действительно постарайтесь понять, что происходит. Я бы сказал, что половину времени я не слушаю свои собственные советы, так что посмотрим, чем закончится это путешествие.