Связный список — это линейная динамическая структура данных для хранения элементов данных. В отличие от массивов, связный список не хранит элементы данных в смежных ячейках памяти.
Связный список состоит из элементов, называемых “узлами”, которые состоят из двух частей. В первой части хранятся фактические данные, а во второй части находится указатель, который указывает на следующий узел. Эта структура обычно называется “Односвязный список”.
В этой статье мы подробно рассмотрим структуру односвязного списка.
На следующей схеме показана структура односвязного списка:
Как показано выше, первый узел связанного списка называется “head” (голова), а последний узел называется “Tail» (хвост). Как вы можете видеть, последний узел связанного списка будет иметь свой следующий указатель как null (ноль), поскольку на него не будет указан какой-либо адрес памяти.
Поскольку каждый узел имеет указатель на следующий узел, элементы данных в связном списке не обязательно должны храниться в смежных местах. Узлы могут быть разбросаны в памяти. Мы можем получить доступ к узлам в любое время, поскольку каждый узел будет иметь адрес следующего узла.
Мы можем добавлять элементы данных в связный список, а также легко удалять элементы из списка. Таким образом, можно динамически увеличивать или уменьшать связный список. Не существует верхнего предела количества элементов данных, которые могут находиться в связном списке. Таким образом, пока доступна память, мы можем добавить в связный список как можно больше элементов данных.
Помимо простой вставки и удаления, связный список также не тратит впустую пространство памяти, поскольку нам не нужно заранее указывать, сколько элементов нам нужно в связном списке. Единственное пространство, занимаемое связным списком, предназначено для хранения указателя на следующий узел, что добавляет немного времени на работу.
Далее мы обсудим различные операции, которые могут быть выполнены со связным списком.
Операции
Так же, как и в других структурах данных, мы можем выполнять различные операции и для связного списка. Но в отличие от массивов, в которых мы можем получить доступ к элементу, используя нижний индекс напрямую, даже если он находится где-то посередине, мы не можем выполнить тот же произвольный доступ со связным списком.
Чтобы получить доступ к любому узлу, нам нужно пройти по связному списку с самого начала, и только тогда мы сможем получить доступ к нужному узлу. Следовательно, случайный доступ к данным из связного списка оказывается небезопасным.
Мы можем выполнять различные операции со связным списком, они указаны ниже:
Вставка
Операция вставки добавляет элемент в связный список. Всякий раз, когда элемент данных добавляется в связный список, нам нужно будет изменять следующие указатели предыдущего и следующего узлов нового элемента, который мы вставили.
Следующее, что мы должны учитывать, это место, куда должен быть добавлен новый элемент данных.
В связном списке есть три позиции, в которые можно добавить элемент данных:
1) В начало связного списка
Связный список показан ниже 2->4->6->8->10. Если мы хотим добавить новый узел 1 в качестве первого узла списка, то заголовок, указывающий на узел 2, теперь будет указывать на 1, а следующий указатель узла 1 будет иметь адрес памяти узла 2, как показано на схеме ниже:
Таким образом, новый связный список становится 1->2->4->6->8->10.
2) После заданного узла
Допустим, указан узел, и мы должны добавить новый узел после данного узла. В приведенном ниже связном списке a->b-> c-> d -> e, если мы хотим добавить узел f после узла c, тогда связный список будет выглядеть следующим образом:
Таким образом, на приведенной выше схеме мы проверяем, присутствует ли данный узел. Если он присутствует, мы создаем новый узел f. Затем мы указываем следующий указатель узла c, чтобы указать на новый узел f. Следующий указатель узла f теперь указывает на узел d.
3) В конце связного списка
В третьем случае мы добавляем новый узел в конец связного списка. Допустим, что у нас есть тот же связный список a-> b-> c-> d-> e, и нам нужно добавить узел f в конец списка. После добавления узла связный список будет выглядеть так, как показано ниже:
Таким образом, мы создаем новый узел f. Затем указатель хвоста, указывающий на null, указывает на f, а следующий указатель узла f указывает на null. Мы реализовали все три типа функций вставки в приведенной ниже программе на C ++.
В C ++ мы можем объявить связный список как структуру или как класс. Объявление связного списка как структуры является традиционным объявлением в стиле C. Связный список как класс используется в современном C ++, в основном при использовании стандартной библиотеки шаблонов.
В следующей программе мы использовали структуру для объявления и создания связного списка. В качестве его членов будут данные и указатель на следующий элемент:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
#include <iostream> using namespace std; // Узел связного списка struct Node { int data; struct Node *next; }; //вставить новый узел перед списком void push(struct Node** head, int node_data) { /* 1. создайте и выделите узел */ struct Node* newNode = new Node; /* 2. назначьте данные узлу */ newNode->data = node_data; /* 3. установите следующий из нового узла в качестве заголовка */ newNode->next = (*head); /* 4. переместите головку так, чтобы она указывала на новый узел */ (*head) = newNode; } //вставить новый узел после заданного узла void insertAfter(struct Node* prev_node, int node_data) { /*1. проверьте, является ли данный prev_node NULL */ if (prev_node == NULL) { cout<<"данный предыдущий узел, не может быть нулевым"; return; } /* 2. создайте и выделите новый узел */ struct Node* newNode =new Node; /* 3. назначьте данные узлу */ newNode->data = node_data; /* 4. Сделайте следующий из нового узла следующим из prev_node */ newNode->next = prev_node->next; /* 5. переместите следующий из prev_node в качестве new_node */ prev_node->next = newNode; } /* вставить новый узел в конец связанного списка */ void append(struct Node** head, int node_data) { /* 1. создайте и выделите узел */ struct Node* newNode = new Node; struct Node *last = *head; /* used in step 5*/ /* 2. назначьте данные узлу */ newNode->data = node_data; /* 3. установите для следующего указателя нового узла значение null в качестве последнего узла */ newNode->next = NULL; /* 4. если список пуст, новый узел становится первым узлом */ if (*head == NULL) { *head = newNode; return; } /* 5. В противном случае пройдите до последнего узла */ while (last->next != NULL) last = last->next; /* 6. Измените предпоследний узел */ last->next = newNode; return; } // отображение содержимого связного списка void displayList(struct Node *node) { //пройдите по списку, чтобы отобразить каждый узел while (node != NULL) { cout<<node->data<<"-->"; node = node->next; } if(node== NULL) cout<<"null"; } /* основная программа для связного списка*/ int main() { /* eпустой список */ struct Node* head = NULL; // Вставить 10. append(&head, 10); // Вставьте 20 в начале. push(&head, 20); // Вставьте 30 в начале. push(&head, 30); // Вставьте 40 в конце. append(&head, 40); // Insert 50, after 20. insertAfter(head->next, 50); cout<<"Final linked list: "<<endl; displayList(head); return 0; } |
Вывод данных:
| Окончательный связный список: 30–>20–>50–>10–>40–> нулевой |
Далее мы реализуем операцию вставки связного списка в Java. На языке Java связный список реализован как класс. Приведенная ниже программа похожа по логике на программу на C ++, единственное отличие состоит в том, что мы используем в ней класс для связного списка.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
class LinkedList { Node head; // головной список //объявление узла связанного списка class Node { int data; Node next; Node(int d) {data = d; next = null; } } /* Вставьте новый узел в начало списка */ public void push(int new_data) { //выделять и назначать данные узлу Node newNode = new Node(new_data); //новый узел становится головой связанного списка newNode.next = head; //указывает на новый узел head = newNode; } // Учитывая узел, prev_node вставляет узел после prev_node public void insertAfter(Node prev_node, int new_data) { //проверить, имеет ли значение prev_node значение null. if (prev_node == null) { System.out.println("The given node is required and cannot be null"); return; } //выделить узел и назначить ему данные Node newNode = new Node(new_data); //следующий за новым узлом следующий за prev_node newNode.next = prev_node.next; //prev_node->следующий - это новый узел. prev_node.next = newNode; } //вставляет новый узел в конец списка public void append(intnew_data) { //выделить узел и назначить данные Node newNode = new Node(new_data); //если связанный список пуст, то новый узел будет головным if (head == null) { head = new Node(new_data); return; } //установить для следующего нового узла значение null, так как это последний узел newNode.next = null; // если нет головного узла, пройти по списку и добавить его к последнему Node last = head; while (last.next != null) last = last.next; //следующий из последних становится новым узлом last.next = newNode; return; } //отображение содержимого связного списка public void displayList() { Node pnode = head; while (pnode != null) { System.out.print(pnode.data+"-->"); pnode = pnode.next; } if(pnode == null) System.out.print("null"); } } //Основной класс для вызова функций класса связного списка и построения связного списка class Main{ public static void main(String[] args) { /* создать пустой список */ LinkedList lList = new LinkedList(); // Вставка 40. lList.append(40); // Вставить 20 в начало. lList.push(20); // Вставить 10 в начало. lList.push(10); // Вставить 50 в конец. lList.append(50); // Вставить 30, после 20. lList.insertAfter(lList.head.next, 30); System.out.println("\nFinal linked list: "); lList. displayList (); } } |
Вывод данных:
| Окончательный связный список: 10–>20–>30–>40–>50–> null |
В приведенной выше программе, как и в C ++, так и в Java, есть отдельные функции для добавления узла перед списком, в конце списка и между списками, заданными в узле. В конце мы печатаем содержимое списка, созданного с использованием всех трех методов.
2) Удаление
Как и вставка, удаление узла из связного списка также включает в себя различные позиции, из которых узел может быть удален. Мы можем удалить первый узел, последний узел или случайный k узел из связного списка. После удаления нам нужно соответствующим образом настроить следующий указатель и другие указатели в связном списке, чтобы сохранить связный список неповрежденным.
В следующей реализации C ++ мы предоставили два метода удаления, т.е. удаление первого узла в списке и удаление последнего узла в списке. Сначала мы создаем список, добавляя узлы в заголовок. Затем мы показываем содержимое списка после вставки и каждого удаления:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <iostream> using namespace std; /* Узел списка */ struct Node { int data; struct Node* next; }; //удалить первый узел в связном списке Node* deleteFirstNode(struct Node* head) { if (head == NULL) return NULL; // Переместить указатель head на следующий узел Node* tempNode = head; head = head->next; delete tempNode; return head; } //удалить последний узел из связного списка Node* removeLastNode(struct Node* head) { if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // сначала найти второй последний узел Node* second_last = head; while (second_last->next->next != NULL) second_last = second_last->next; // Удалить последний узел delete (second_last->next); // установить следующее значение second_last равным null second_last->next = NULL; return head; } // создать связный список, добавив узлы в начало void push(struct Node** head, int new_data) { struct Node* newNode = new Node; newNode->data = new_data; newNode->next = (*head); (*head) = newNode; } // основная функция int main() { /* Начать с пустого списка */ Node* head = NULL; // создать связный список push(&head, 2); push(&head, 4); push(&head, 6); push(&head, 8); push(&head, 10); Node* temp; cout<<"Linked list created "<<endl; for (temp = head; temp != NULL; temp = temp->next) cout << temp->data << "-->"; if(temp == NULL) cout<<"NULL"<<endl; //удалить первый узел head = deleteFirstNode(head); cout<<"Linked list after deleting head node"<<endl; for (temp = head; temp != NULL; temp = temp->next) cout << temp->data << "-->"; if(temp == NULL) cout<<"NULL"<<endl; //удалить последний узел head = removeLastNode(head); cout<<"Linked list after deleting last node"<<endl; for (temp = head; temp != NULL; temp = temp->next) cout << temp->data << "-->"; if(temp == NULL) cout<<"NULL"; return 0; } |
Вывод данных:
| Созданный связный список 10–>8–>6–>4–>2–> NULL Связный список после удаления головного узла 8–>6–>4–>2–> NULL Связный список после удаления последнего узла 8–>6–> 4–> NULL |
Далее приведена реализация Java для удаления узлов из связного списка. Логика реализации та же, что используется в программе на C ++. Единственное отличие заключается в том, что связный список объявляется как класс:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
class Main { // Узел связного списка / static class Node { int data; Node next; }; // удалить первый узел связного списка static Node deleteFirstNode(Node head) { if (head == null) return null; // Переместите указатель head на следующий узел Node temp = head; head = head.next; return head; } // Удалить последний узел в связном списке static Node deleteLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } // поиск предпоследнего узла Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; // установить следующее значение равным null second_last.next = null; return head; } // Добавить узлы в заголовок и создать связный список static Node push(Node head, int new_data) { Node newNode = new Node(); newNode.data = new_data; newNode.next = (head); (head) = newNode; return head; } //основная функция public static void main(String args[]) { // Начать с пустого списка / Node head = null; //создать связный список head = push(head, 1); head = push(head, 3); head = push(head, 5); head = push(head, 7); head = push(head, 9); Node temp; System.out.println("Linked list created :"); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + "-->"); if(temp == null) System.out.println("null"); head = deleteFirstNode(head); System.out.println("Linked list after deleting head node :"); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + "-->"); if(temp == null) System.out.println("null"); head = deleteLastNode(head); System.out.println("Linked list after deleting last node :"); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + "-->"); if(temp == null) System.out.println("null"); } } |
Вывод данных:
| Созданный связный список : 9–>7–>5–>3–>1–> null Связный список после удаления головного узла : 7–>5–>3–>1–> null Связный список после удаления последнего узла : 7–>5–> 3–> null |
Подсчитайте количество узлов
Операция подсчета количества узлов может быть выполнена во время обхода связного списка. Мы уже показали в приведенной выше демонстрации, что всякий раз, когда нам нужно вставить или удалить узел или отобразить содержимое связного списка, нам нужно пройти связный список с самого начала.
Сохранение счетчика и его увеличение по мере прохождения каждого узла даст нам подсчет количества узлов, присутствующих в связном списке.
Массивы и связные списки
Ознакомившись с работой и реализацией связного списка, давайте сравним, насколько массивы и связный список различны по сравнению друг с другом:
| Массивы | Связные списки |
| Массивы имеют фиксированный размер | Размер связного списка является динамическим |
| Вставка нового элемента занимает много времени | Вставка / удаление проще |
| Разрешен произвольный доступ | Произвольный доступ невозможен |
| Элементы находятся в смежном расположении | Элементы имеют несмежное расположение |
| Для следующего указателя не требуется дополнительного места | Для следующего указателя требуется дополнительное пространство памяти |
Поскольку и массивы, и связные списки используются для хранения элементов и являются линейными структурами данных, обе эти структуры могут использоваться аналогичными способами для большинства применений.
Вот некоторые примеры применения связных списков:
- Связный список можно использовать для реализации стеков и очередей.
- Связный список также можно использовать для реализации графиков всякий раз, когда нам нужно представлять графики в виде списков смежности.
- Математический многочлен может быть сохранен в виде связного списка.
- В случае метода хеширования сегменты, используемые при хешировании, реализуются с использованием связных списков.
- Всякий раз, когда программе требуется динамическое выделение памяти, мы можем использовать связный список, поскольку в этом случае связные списки работают более эффективно.
Итог
Связные списки — это структуры данных, которые используются для хранения элементов данных линейным образом, но в несмежных местоположениях. Связный список — это набор узлов, которые содержат часть данных и указатель next следующий), который содержит адрес памяти следующего элемента в списке.
Последнему элементу в списке присваивается значение NULL для следующего указателя, что указывает на конец списка. Первый элемент списка называется Head . Связный список поддерживает различные операции, такие как вставка, удаление, обход и т.д. В случае динамического выделения памяти связные списки предпочтительнее массивов.
В этой статье вы узнали все о линейных связных списках. Связные списки также могут быть циклическими или двойными. В следующей статье мы подробно рассмотрим работу двусвязного списка.
С Уважением, МониторБанк