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

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

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

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

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

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

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

Типы связанных списков

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

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

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

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

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

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

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

С++

// A Single linked list node

class Node {

public:

    int data;

    Node* next;

};

С

// A Single linked list node

struct Node {

    int data;

    struct Node* next;

};

Java

// Linked List Class

class LinkedList {

    Node head; // head of list

 

    /* Node Class */

    class Node {

        int data;

        Node next;

 

        // Constructor to create a new node

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

}

Python3

# Node class

class Node:

 

    # Function to initialize the node object

    def __init__(self, data):

        self.data = data  # Assign data

        self.next = None  # Initialize next as null

 

# Linked List class

 

 

class LinkedList:

 

    # Function to initialize the Linked List object

    def __init__(self):

        self.head = None

С#

/* A Single Linked list Node*/

public class Node {

    public int data;

    public Node next;

    public Node(int d)

    {

        data = d;

        next = null;

    }

Javascript

<script>

// Linked List Class

    var head; // head of list

 

    /* Node Class */

    class Node {

 

        // Constructor to create a new node

        constructor(d) {

            this.data = d;

            this.next = null;

        }

    }

 

</script>

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

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

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

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

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

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

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

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

С++

/* Node of a doubly linked list */

class Node {

public:

    int data;

    Node* next; // Pointer to next node in DLL

    Node* prev; // Pointer to previous node in DLL

};

С

/* Node of a doubly linked list */

struct Node {

    int data;

    struct Node* next; // Pointer to next node in DLL

    struct Node* prev; // Pointer to previous node in DLL

};

Java

// Class for Doubly Linked List

public class DLL {

    Node head; // head of list

 

    /* Doubly Linked list Node*/

    class Node {

        int data;

        Node prev;

        Node next;

 

        // Constructor to create a new node

        // next and prev is by default initialized as null

        Node(int d) { data = d; }

    }

}

Python3

# Node of a doubly linked list

class Node:

    def __init__(self, next=None, prev=None, data=None):

        self.next = next  # reference to next node in DLL

        self.prev = prev  # reference to previous node in DLL

        self.data = data

С#

// Class for Doubly Linked List

public class DLL {

    Node head; // head of list

 

    /* Doubly Linked list Node*/

    public class Node {

        public int data;

        public Node prev;

        public Node next;

 

        // Constructor to create a new node

        // next and prev is by default initialized as null

        Node(int d) { data = d; }

    }

}

Javascript

<script>

// Class for Doubly Linked List

    var head; // head of list

 

    /* Doubly Linked list Node */

     class Node {

        // Constructor to create a new node

            // next and prev is by default initialized as null

            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)временной сложности.

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

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

Заключение

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

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