Связанный список - это линейная структура данных, которая содержит структуру узлов, и каждый узел содержит два элемента. Часть данных, которая хранит значение в этом узле, и следующая часть, которая хранит ссылку на следующий узел, как показано на изображении ниже:
Первый узел, также известный как HEAD, обычно используется для просмотра связанного списка. Последний узел (следующая часть последнего узла) указывает на NULL. Список можно представить в виде цепочки узлов, где каждый узел указывает на следующий узел.
В PHP односвязный список может быть представлен как класс, а узел - как отдельный класс. Класс связанного списка содержит ссылку типа класса Node.
// структура узла
class Node {
public $ data;
public $ next;
}
class LinkedList {
public $ head;
// конструктор для создания пустого списка LinkedList
public function __construct () {
$ this- ›head = null;
}
};
Давайте создадим простой связанный список, содержащий три узла данных.
‹? Php
// структура узла
class Node {
public $ data;
public $ next;
}
class LinkedList {
public $ head;
// конструктор для создания пустого списка LinkedList
public function __construct () {
$ this- ›head = null;
}
};
// тестируем код
// создаем пустой LinkedList
$ MyList = new LinkedList ();
// Добавляем первый узел.
$ first = new Node ();
$ first- ›data = 10;
$ first-› next = null;
// связывание с головной узел
$ MyList- ›head = $ first;
// Добавляем второй узел.
$ second = new Node ();
$ second- ›data = 20;
$ second-› next = null;
// связывание с первый узел
$ first- ›next = $ second;
// Добавляем третий узел.
$ third = new Node ();
$ third- ›data = 30;
$ third-› next = null;
// связывание с второй узел
$ second- ›next = $ третий;
?›
Перемещаться по связному списку очень просто. Это требует создания временного узла, указывающего на начало списка. Если временный узел не равен нулю, отобразите его содержимое и перейдите к следующему узлу, используя команду temp next. Повторяйте процесс, пока временный узел не станет нулевым. Если временный узел вначале пуст, то список не содержит элементов.
Для этого создается функция PrintList. Это трехэтапный процесс.
публичная функция PrintList () {
// 1. создать временный узел, указывающий на голову
$ temp = new Node ();
$ temp = $ this- ›head;
// 2. если временный узел не равен нулю, продолжить
// отображение содержимого и переход к
// следующему узлу, пока временный узел не станет нулевым
if ($ temp! = null) {
echo «\ nСписок содержит:«;
while ($ temp! = null) {
echo $ temp- ›data.» «;
$ temp = $ temp-› next;
}
} else {
// 3. Если временный узел вначале равен нулю,
// список пуст
echo «\ nСписок пуст.»;
}
}
Добавить новый узел в конец связанного списка
В этом методе новый узел вставляется в конец связанного списка. Например, если задан список 10- ›20-› 30 и в конце добавлен новый элемент 100, то связанный список станет 10- ›20-› 30- ›100.
Вставить новый узел в конец связного списка очень просто. Сначала создается новый узел с заданным элементом. Затем он добавляется в конец списка путем связывания последнего узла с новым узлом.
Для этого создана функция push_back. Это 6-этапный процесс.
публичная функция push_back ($ newElement) {
// 1. выделить узел
$ newNode = new Node ();
// 2. присвоить элемент данных
$ newNode- ›data = $ newElement;
// 3. присвоить null следующему новому узлу
$ newNode- ›next = null;
// 4. Убедитесь, что связанный список пуст или нет,
// если он пуст, сделать новый узел заголовком
if ($ this- ›head == null) {
$ this-› head = $ newNode;
} else {
// 5. В противном случае перейти к последнему узлу
$ temp = new Node ();
$ temp = $ this- ›head;
while ($ temp-› next! = Null) {
$ temp = $ temp- ›next;
}
// 6. Замените следующий или последний узел на новый
$ temp- ›next = $ newNode;
}
}
Ниже представлена полная программа, в которой используются все рассмотренные выше концепции связного списка.
‹? Php
// структура узла
class Node {
public $ data;
public $ next;
}
class LinkedList {
public $ head;
public function __construct () {
$ this- ›head = null;
}
// Добавить новый элемент в конец списка
public function push_back ( $ newElement) {
$ newNode = new Node ();
$ newNode- ›data = $ newElement;
$ newNode-› next = null;
if ($ this- ›head == null) {
$ this-› head = $ newNode;
} else {
$ temp = new Node ();
$ temp = $ this- ›head;
while ($ temp-› next! = null) {
$ temp = $ temp- ›next;
}
$ temp- ›next = $ newNode;
}
}
// отображаем содержимое списка
public function PrintList () {
$ temp = new Node ();
$ temp = $ this- ›head;
if ($ temp! = null) {
echo «\ nСписок содержит:«;
while ($ temp! = null) {
echo $ temp- ›data.» «;
$ temp = $ temp-› next;
}
} else {
echo «\ nСписок пуст.»;
}
}
};
// тестируем код
$ MyList = new LinkedList ();
// Добавляем три элемента в конец списка.
$ MyList- ›push_back (10);
$ MyList-› push_back (20);
$ MyList- ›push_back (30) ;
$ MyList- ›PrintList ();
?›
Результатом приведенного выше кода будет:
В списке: 10 20 30
