Тип данных list это односвязный список: Алгоритмы и структуры данных для начинающих: связный список

Что такое связанный список?

Связанный список — это линейная структура данных, которая выглядит как цепочка узлов, где каждый узел представляет собой отдельный элемент. В отличие от массивов, элементы связанного списка не хранятся в непрерывном месте.

В основном это цепочки узлов, каждый узел содержит такую ​​информацию, как данные и указатель на следующий узел в цепочке. В связанном списке есть указатель head, который указывает на первый элемент связанного списка, и если список пуст, то он просто указывает на null или ничего.

Учебное пособие по связанным спискам

Содержание

1. Зачем нужна структура данных связанного списка
2. Типы связанных списков
3. 1. Односвязный список
4. 2. Двусвязный список
5. 3. Круговые связанные списки
6. Преимущества связанных списков
7. Недостатки связанных списков
8. Приложения связанного списка
9. Применение связанных списков в реальном мире
10. Часто задаваемые вопросы (FAQ) о связанном списке
11. Что такое структура данных связанного списка?
12. Что такое пример связанного списка?
13. Зачем нам нужна структура данных связанного списка??
14. Для чего используются связанные списки?
15. В чем разница между массивом и связанным списком?
16. Почему связный список предпочтительнее массива?
17. Что лучше: массив или связанный список?
18. Каковы ограничения связанного списка?
19. Почему вставка/удаление быстрее в связанном списке?
20. Заключение

Зачем нужна структура данных связанного списка

Вот несколько преимуществ связанного списка, который указан ниже, это поможет вам понять, почему это необходимо знать.

• Динамическая структура данных: размер памяти может быть выделен или освобожден во время выполнения в зависимости от операции вставки или удаления.
• Простота вставки/удаления: вставка и удаление элементов проще, чем массивы, поскольку после вставки и удаления не нужно сдвигать элементы, нужно только обновить адрес.
• Эффективное использование памяти. Как мы знаем, связанный список — это динамическая структура данных, размер которой увеличивается или уменьшается в соответствии с требованиями, что позволяет избежать потери памяти.
• Реализация: различные расширенные структуры данных могут быть реализованы с использованием связанного списка, такого как стек, очередь, граф, хэш-карты и т. д.

В основном существует три типа связанных списков:

1. Односвязный список
2. Двойной связанный список
3. Круговой связанный список

1. Односвязный список

Обход элементов может выполняться в прямом направлении только благодаря привязке каждого узла к следующему узлу.

Односвязный список

Представление односвязного списка:

Создание узла:

С++

classNode {

public:

    intdata;

    Node* next;

};

С

structNode {

    intdata;

    structNode* next;

};

Java

classLinkedList {

    Node head;

 

    

    classNode {

        intdata;

        Node next;

 

        

        Node(intd)

        {

            data = d;

            next = null;

        }

    }

}

Python3

classNode:

 

    

    def__init__(self, data):

        self. data =data 

        self.next=None 

 

 

 

classLinkedList:

 

    

    def__init__(self):

        self.head =None

С#

publicclassNode {

    publicintdata;

    publicNode next;

    publicNode(intd)

    {

        data = d;

        next = null;

    }

Javascript

<script>

    varhead;

 

    

    class Node {

 

        

        constructor(d) {

            this. data = d;

            this.next = null;

        }

    }

 

</script>

Часто используемые операции с односвязным списком:

Следующие операции выполняются над одним связанным списком.

• Вставка: Операция вставки может быть выполнена тремя способами. Они следующие…
  • Вставка в начало списка
  • Вставка в конец списка
  • Вставка в определенное место в списке
• Удаление: операцию удаления можно выполнить тремя способами. Они следующие…
  • Удаление с начала списка
  • Удаление из конца списка
  • Удаление определенного узла
• Поиск: это процесс определения и извлечения определенного узла либо с начала, с конца, либо из любого места в списке.
• Отображение: этот процесс отображает элементы односвязного списка.

2. Двусвязный список

Обход элементов может выполняться как в прямом, так и в обратном направлении, поскольку каждый узел содержит дополнительный указатель prev, указывающий на предыдущий узел.

Двусвязный список

Представление двусвязного списка:

Создание узла:

С++

classNode {

public:

    intdata;

    Node* next;

    Node* prev;

};

С

structNode {

    intdata;

    structNode* next;

    structNode* prev;

};

Java

publicclassDLL {

    Node head;

 

    

    classNode {

        intdata;

        Node prev;

        Node next;

 

        

        

        Node(intd) { data = d; }

    }

}

Python3

classNode:

    def__init__(self, next=None, prev=None, data=None):

        self. next=next 

        self.prev =prev 

        self.data =data

С#

publicclassDLL {

    Node head;

 

    

    publicclassNode {

        publicintdata;

        publicNode prev;

        publicNode next;

 

        

        

        Node(intd) { data = d; }

    }

}

Javascript

<script>

    varhead;

 

    

     class Node {

        

            

            constructor(val) {

                this. data = val;

                this.prev = null;

                this.next = null;

            }

        }

         

</script>

Часто используемые операции над двусвязным списком:

В двусвязном списке мы выполняем следующие операции…

• Вставка: Операция вставки может быть выполнена тремя способами:
  • Вставка в начало списка
  • Вставка после заданного узла.
  • Вставка в конце.
  • Вставка перед данным узлом
• Удаление: Операция удаления может быть выполнена тремя способами:
  • Удаление с начала списка
  • Удаление из конца списка
  • Удаление определенного узла
• Отображение: этот процесс отображает элементы двусвязного списка.

3. Круговые связанные списки

Круговой связанный список — это тип связанного списка, в котором первый и последний узлы также связаны друг с другом, образуя круг, в конце которого нет NULL.

Круговой связанный список

Часто используемые операции с циклическим связанным списком:

Следующие операции выполняются над циклическим связанным списком.

• Вставка: Операция вставки может быть выполнена тремя способами:
  • Вставка в пустой список
  • Вставка в начало списка
  • Вставка в конец списка
  • Вставка между узлами
• Удаление: Операция удаления может быть выполнена тремя способами:
  • Удаление с начала списка
  • Удаление из конца списка
  • Удаление определенного узла
• Отображение: этот процесс отображает элементы кругового связанного списка.

Преимущества связанных списков

• Динамический характер: связанные списки используются для динамического выделения памяти.
• Эффективность памяти: потребление памяти связным списком эффективно, поскольку его размер может динамически увеличиваться или уменьшаться в соответствии с нашими требованиями, что означает эффективное использование памяти, следовательно, отсутствие потери памяти.
• Простота вставки и удаления: вставка и удаление узлов легко реализуются в связанном списке в любой позиции.
• Реализация: для реализации стеков и очередей, а также для представления деревьев и графов.
• Связанный список может быть расширен за постоянное время.

• Использование памяти: использование указателей больше в связанных списках, следовательно, сложно и требует больше памяти.
• Доступ к узлу: произвольный доступ невозможен из-за динамического выделения памяти.
• Дорогостоящая операция поиска: поиск элемента является дорогостоящим и требует O (n) временной сложности.
• Обход в обратном порядке: Обход требует больше времени, а обратный обход невозможен в односвязных списках.

Приложения связанного списка

Вот некоторые из приложений связанного списка:

• Линейные структуры данных, такие как стек, очередь, и нелинейные структуры данных, такие как хэш-карты и графики, могут быть реализованы с использованием связанных списков.
• Динамическое выделение памяти: мы используем связанный список свободных блоков.
• Реализация графов. Представление графов списком смежности является наиболее популярным, поскольку оно использует связанные списки для хранения смежных вершин.
• В веб-браузерах и редакторах двусвязные списки можно использовать для создания кнопки навигации вперед и назад.
• Циклический двусвязный список также можно использовать для реализации таких структур данных, как кучи Фибоначчи.

Применение связанных списков в реальном мире

• Список песен в музыкальном проигрывателе связан с предыдущей и следующей песнями.
• В веб-браузере URL-адреса предыдущей и следующей веб-страницы связаны с помощью кнопок «Предыдущая» и «Далее».
• В средстве просмотра изображений предыдущее и следующее изображения связаны с помощью кнопок «предыдущее» и «следующее».
• Переключение между двумя приложениями осуществляется с помощью «alt+tab» в windows и » cmd+tab » в Для этого требуется функциональность кругового связанного списка.
• В мобильных телефонах мы сохраняем контакты людей. Новые введенные контактные данные будут размещены в правильном алфавитном порядке.
• Это может быть достигнуто с помощью связанного списка, чтобы установить контакт в правильном алфавитном положении.
• Модификации, которые мы внесли в документы, на самом деле созданы как узлы в двусвязном списке. Мы можем просто использовать опцию отмены, нажав Ctrl+Z, чтобы изменить содержимое. Это делается с помощью функциональности связанного списка.

Часто задаваемые вопросы (FAQ) о связанном списке

Связанные списки чаще всего используются для обработки динамических элементов данных. Связанный список состоит из узлов, а узел состоит из двух полей, одно для хранения данных, а другое для хранения ссылки на следующий узел.

Связанный список можно представить как гирлянду из цветов. Точно так же связанный список состоит из узлов. Каждый цветок в этой конкретной гирлянде называется узлом. Кроме того, каждый узел указывает на следующий узел в этом списке и содержит данные (в данном случае тип цветка).

Есть несколько важных преимуществ использования связанных списков по сравнению с другими линейными структурами данных. Это не похоже на массивы, так как их размер можно изменять во время выполнения. Кроме того, их можно легко вставлять и удалять.

Связный список — это линейная структура данных, которая хранит данные в узлах. эти узлы содержат как данные, так и ссылку на следующий узел в списке. Связанные очень эффективны при добавлении и удалении узлов из-за их простой структуры.

Между ними есть следующие отличия:

• Массивы — это структуры данных, содержащие похожие элементы данных, тогда как связанные списки — это не примитивные структуры данных, содержащие неупорядоченные связанные элементы.
• В массиве элементы индексируются, а в связном списке узлы не индексируются.
• Доступ к массиву элементов выполняется быстро, если мы знаем положение элемента в массиве, в то время как в связанном списке это занимает линейное время, поэтому связанный список немного медленнее.
• Такие операции, как вставка и удаление в массивах, занимают много времени. Принимая во внимание, что производительность этих операций выше в связанных списках.
• Массивы имеют фиксированный размер, и их размер является статическим, но связанные списки являются динамическими и гибкими и могут увеличивать и уменьшать свой размер.

Ниже приведены причины, по которым связанные списки предпочтительнее массивов.

• Узлы в связанном массиве, вставки и удаления могут выполняться в любой точке списка в постоянное время.
• Массивы имеют фиксированный размер, и их размер является статическим, но связанные списки являются динамическими и гибкими и могут увеличивать и уменьшать свой размер.
• Связанные списки обеспечивают эффективный способ хранения связанных данных и выполнения основных операций, таких как вставка, удаление и обновление информации, за счет дополнительного пространства, необходимого для хранения адреса.
• Операции вставки и удаления в связанном списке выполняются быстрее по сравнению с массивом.

В чем разница между односвязным и двусвязным списком?

Односвязный список (SLL)	Двусвязный список (DLL)
Узлы SLL содержат 2 поля данных и поле следующей ссылки.	Узлы DLL содержат 3 поля: поле данных, поле предыдущей ссылки и поле следующей ссылки.
В SLL обход может быть выполнен только с использованием ссылки на следующий узел. Таким образом, обход возможен только в одном направлении.	В DLL обход может выполняться по ссылке на предыдущий узел или по ссылке на следующий узел. Таким образом, перемещение возможно в обоих направлениях (вперед и назад).
SLL занимает меньше памяти, чем DLL, так как имеет только 2 поля.	DLL занимает больше памяти, чем SLL, так как имеет 3 поля.
Сложность вставки и удаления в данной позиции составляет O(n).	Сложность вставки и удаления в заданной позиции составляет O(n/2) = O(n), потому что обход можно выполнять как с начала, так и с конца.
Сложность удаления с данным узлом составляет O (n), потому что предыдущий узел должен быть известен, а обход занимает O (n)	Сложность удаления с данным узлом составляет O (1), потому что к предыдущему узлу можно легко получить доступ.
Односвязный список потребляет меньше памяти по сравнению с двусвязным списком.	Двусвязный список потребляет больше памяти по сравнению с односвязным списком.

Что лучше: массив или связанный список?

Как у массивов, так и у связанных списков есть некоторые преимущества и недостатки, когда речь идет о хранении линейных данных схожих типов.

Преимущества связного списка перед массивом:

• Динамический размер: связанные списки являются динамическими и гибкими и могут расширяться и уменьшаться в размере.
• Простота вставки/удаления: операции вставки и удаления в связанном списке выполняются быстрее по сравнению с массивом.

Недостатки связанного списка перед массивами:

• Если массив отсортирован, мы можем применить бинарный поиск для поиска любого элемента, который занимает время O (log (n)). Но даже если связанный список отсортирован, мы не можем применить бинарный поиск, а сложность поиска элементов в связанном списке составляет O(n).
• Связанный список занимает больше памяти по сравнению с массивом, потому что для указателя с каждым элементом в связанном списке требуется дополнительное место в памяти.

Каковы ограничения связанного списка?

Ниже приведены некоторые ограничения связанного списка:

• Использование указателей больше в связанных списках, следовательно, сложно и требует больше памяти.
• Произвольный доступ невозможен из-за динамического выделения памяти.
• Обход требует больше времени, а обратный обход невозможен в односвязных списках.
• Поиск элемента является дорогостоящим и требует O(n)временной сложности.

Почему вставка/удаление быстрее в связанном списке?

Если какой-либо элемент вставляется/удаляется из массива, все остальные элементы после него будут смещены в памяти, это занимает много времени, тогда как манипуляции в связанном списке выполняются быстрее, потому что нам просто нужно манипулировать адресами узлов, поэтому без смещения битов требуется в памяти, и это не займет много времени.

Заключение

Есть много преимуществ связного списка по сравнению с массивом, несмотря на то, что они решают ту же проблему, что и массивы, мы также обсудили преимущества, недостатки и его применение, и мы пришли к выводу, что мы можем использовать связанный список, если нам нужен динамический размер хранилища, и список хорош для быстрого добавления и удаления элементов или для задач, требующих последовательности, но не подходит для запроса или поиска элементов в большом наборе данных.

Таким образом, становится важным, чтобы мы всегда помнили о положительных и отрицательных аспектах структуры данных и о том, как они связаны с проблемой, которую вы пытаетесь решить.

Введение в связанные списки

Связный список — это линейная структура данных, состоящая из группы узлов, где каждый узел указывает на следующий узел через указатель. Каждый узел состоит из данных и ссылки (другими словами, ссылки) на следующий узел в последовательности.

 
Связанные списки являются одними из самых простых и распространенных структур данных. Основные преимущества связанного списка по сравнению с обычным массивом:

• Элементы списка могут быть легко вставлены или удалены без перераспределения или реорганизации всей структуры, поскольку элементы данных не должны храниться в памяти непрерывно. В то же время массив должен быть объявлен в исходном коде перед компиляцией и запуском программы.
• Связанные списки позволяют вставлять и удалять узлы в любой точке списка. Они могут сделать это с постоянным числом операций, если ссылка на предыдущий узел сохраняется во время обхода списка.

С другой стороны, простые связанные списки сами по себе не допускают произвольного доступа к данным или какой-либо формы эффективного индексирования. Таким образом, многие базовые операции, такие как получение последнего узла списка, поиск узла, содержащего заданные данные, или определение места, куда должен быть вставлен новый узел, могут потребовать последовательного сканирования большинства или всех элементов списка.

Распространенные типы связанных списков

Односвязные списки содержат узлы с полем данных и next поле, которое указывает на следующий узел в строке узлов. Операции, которые можно выполнять над односвязными списками, включают вставку, удаление и обход.

В двусвязном списке каждый узел содержит, кроме ссылки на следующий узел, второе поле ссылки, указывающее на prev узел в последовательности.

Ан Техника XOR-связывания позволяет реализовать двусвязный список с использованием одного поля ссылки в каждом узле.

В последнем узле списка поле ссылки часто содержит нулевую ссылку, для обозначения отсутствия дальнейших узлов используется специальное значение. В кольцевом двусвязном списке “хвост” связан с “головой”. Основным преимуществом круговых списков является их способность проходить весь список, начиная с любого заданного узла.

Применение связанных списков

Связанные списки — это динамическая структура данных, которая может увеличиваться и сокращаться, выделяя и освобождая память во время работы программы.

• Динамические структуры данных, такие как stacks а также queues может быть реализован с использованием связанного списка и нескольких других распространенных абстрактных типов данных, включая списки и ассоциативные массивы.
• Многие современные операционные системы используют двусвязные списки для поддержки ссылок на активные процессы, потоки и другие динамические объекты.
• А хеш-таблица может использовать связанные списки для хранения цепочек элементов, которые хешируются в одну и ту же позицию в хеш-таблице.
• А бинарное дерево можно рассматривать как тип связанного списка, где элементы сами по себе являются связанными списками той же природы. В результате каждый узел может включать ссылку на первый узел одного или двух других связанных списков, которые вместе со своим содержимым образуют поддеревья ниже этого узла.

Примечание. Если прямо не указано иное, односвязный список будет называться списком или связанным списком на нашем веб-сайте.

 
Также см:

Реализация связанного списка в C

Связанный список – вставка в конце | Реализация C, Java и Python

 
Источник: https://en. wikipedia.org/wiki/Linked_list

Оценить этот пост

Средний рейтинг 4.87/5. Подсчет голосов: 290

Голосов пока нет! Будьте первым, кто оценит этот пост.

Сожалеем, что этот пост не оказался для вас полезным!

Расскажите, как мы можем улучшить этот пост?

Односвязные списки :: CC 310 Textbook

Чтобы устранить недостатки массивов, нам нужна структура данных, позволяющая вставлять и удалять элементы в упорядоченной коллекции за постоянное время, независимо от количества элементов в структуре данных.

Решение заключается в создании собственной специализированной структуры данных, где каждый узел содержит интересующие данные, а также ссылку или указатель на следующий узел в списке. Конечно, нам также потребуется указатель на первый узел в списке, который мы называем 9-м.0007 голова

На рисунке ниже показано, как мы можем построить структуру данных связанного списка. Объект head , показанный на рисунке, представляет собой переменную, содержащую указатель на первый узел в списке, в данном случае узел, содержащий -2 . Каждый узел в списке — это объект, состоящий из двух основных частей: данных, которые он содержит, и указателя на следующий элемент в списке.

Представление класса односвязного списка

Список представлен специальной переменной head , которая содержит указатель на первый элемент в списке. Если head равно null (равно 0 ), то у нас есть пустой список, то есть список без элементов.

Однако, если у нас есть элементы в списке, head будет указывать на узел, как показано на рисунке ниже. Этот узел имеет некоторые данные (в данном случае -2 ) и собственный указатель, указывающий на следующий узел в списке. Как мы видим в нашем примере, head указывает на последовательность из пяти узлов, составляющих наш список. Узел с данными 67 является последним элементом в списке, так как его указатель равен null . Мы часто называем это состояние наличием нуля 9.0008 указатель.

Хотя мы не будем показывать их явно в этом модуле, каждый указатель на самом деле является адресом в памяти. Если у нас есть указатель на узел

 Класс SingleLinkedList
    Головка узла
    Целочисленный размер = 0
 

структура узла
{
целое значение;
узел* следующий;
};
 

Узел *head = nullptr;