Вступление
Связанный список — это структура данных, в которой элементы упорядочены линейно. Хотя современные языки программирования поддерживают очень гибкие и богатые библиотеки, которые работают с массивами, которые используют массивы для представления списков, принципы построения связанного списка остаются очень важными. Реализация связанных списков осуществляется на уровне земли для построения более сложных структур данных, таких как деревья.
Это правда, что почти каждая операция, которую мы можем выполнить над связанным списком, может быть выполнена с массивом. Также верно, что некоторые операции могут выполняться быстрее над массивами по сравнению со связанными списками.
Однако понимание того, как реализовать основные операции связанного списка, такие как INSERT, DELETE, INSERT_AFTER, PRINT и т. Д., Крайне важно для реализации структур данных, таких как корневые деревья, B-деревья, красно-черные деревья и т. Д.
обзор
В отличие от массивов, в которых у нас нет указателей на следующий и предыдущий элемент, связанный список предназначен для поддержки таких указателей. В некоторых реализациях имеется только один указатель, указывающий на преемника элемента. Такого рода структуры данных называются односвязными списками. В этом случае последний элемент не имеет преемника, поэтому указатель на его следующий элемент обычно равен NULL. Однако наиболее реализованная версия связанного списка поддерживает два указателя. Это так называемые двусвязные списки.
Элементы массивов определяются их индексами, в то время как связанный элемент списка содержит указатель на своего предшественника и его преемника!
Давайте посмотрим на некоторые примеры. Вот массив:
A[2, 'hello', 'world', 13, 31]
Мы знаем, что A [0] содержит число 2, а A [1] содержит слово (строка) «привет». Это базовое представление массива, где индексы являются последовательными и начинаются с 0.
В этом случае мы знаем, что если мы смотрим на элемент с индексом i , его следующий элемент имеет индекс i + 1 , а индекс его предшественника — i-1 . Таким образом, мы можем легко перебирать элементы. Однако, если у нас есть массив только с 5 элементами, A [5] не существует, и в большинстве случаев это NULL. Другими словами, элементы массива определяются своими индексами и могут быть доступны напрямую с помощью их индекса.
С другой стороны, большинство языков программирования поддерживают ассоциативные массивы, также называемые хэш-картами.
Ассоциативный массив в PHP может быть примерно таким.
$a = array( 'hello' => 'world', 31 => 12, 'b7' => 144, );
Теперь, поскольку индексы не являются последовательными целыми числами, мы не знаем преемника и предшественника текущего элемента. Да, есть некоторый внутренний указатель, который может дать нам ссылку на предыдущий и следующий элемент, но явно мы не можем ссылаться на них.
Конечно, некоторые библиотеки могут иметь функции, которые могут указывать нам на следующий элемент, такая функция — next () в PHP .
Как мы видим, массивы могут заменить типичное указательное представление связанного списка, но, как я уже сказал, эта структура данных имеет решающее значение для понимания более сложных структур данных.
Обычно связанный список реализуется двумя классами. Первый описывает элемент, а второй содержит основные операции списка, такие как поиск, вставка, удаление и т. Д.
Первый класс, обычно называемый Item, является обычным классом, содержащим различную информацию об элементе. Например, с точки зрения лиц, этот класс может содержать имя и фамилию человека, его адрес, телефон и т. Д. Однако очень важно, чтобы этот класс содержал указатели на свой предыдущий и следующие объекты.
В наших терминах каждый объект класса Person будет содержать указатель на следующий объект того же класса Person.
class Person
{
public $next = null;
public $prev = null;
protected $_firstName = '';
protected $_lastName = '';
protected $_phone = '';
public function __construct($firstName, $lastName, $phone)
{
$this->_firstName = $firstName;
$this->_lastName = $lastName;
$this->_phone = $phone;
}
public function __toString()
{
return 'First name: ' . $this->_firstName
. ', Last name: ' . $this->_lastName
. ', Phone: ' . $this->_phone;
}
}
Поэтому мы должны сначала спроектировать структуру предмета.
Следующее, что нужно сделать, это определить связанный список как абстракцию над списком реального мира, точно так же как стек и очередь. Мы можем реализовать различные операции для связанного списка, такие как вставка , удаление , insertBefore , insertAfter , сортировка , поиск , insertSorted и т. Д. Разработчик должен решить, какие операции он хочет использовать. И конечно это зависит от приложения.
Реализация
операции
Мы можем выполнять и определять столько операций, сколько нам нужно. Например, мы можем закодировать связанный список только базовыми вставками, удалить и распечатать, но мы также можем перейти к insertBefore, insertAfter, deleteBefore, deleteAfter, insertSorted, которые описаны на диаграммах ниже.
Вставить
Вставка в начало списка выглядит как вставка в очередь. В этом случае новый элемент становится главой списка, а его преемник — предыдущим главой списка.
Вставка в начале списка
class LList
{
public $head;
public $tail;
public function insert($item)
{
$item->next = $this->head;
if ($this->head != null) {
$this->head->prev = $item;
}
$this->head = $item;
}
public function __toString()
{
$cur = $this->head;
$output = '';
while ($cur) {
$output .= $cur . ' ';
$cur = $cur->next;
}
return $output . "\n";
}
}
$ll = new LList();
$a = new Person('John', 'Smith', '555 9401');
$b = new Person('James', 'Johnes', '555 2454');
$ll->insert($a);
$ll->insert($b);
// James Johnes 555 2454
// John Smith 555 9401
echo $ll;
Удалить
Удаление заголовка списка очень похоже на удаление элемента из очереди. Однако мы можем реализовать также удаление пользовательского элемента, который находится внутри списка.
Удаление элемента из списка!
class LList
{
public $head;
public $tail;
public function insert($item)
{
$item->next = $this->head;
if ($this->head != null) {
$this->head->prev = $item;
}
$this->head = $item;
}
public function delete($item)
{
$cur = $this->head;
while ($cur) {
if ($cur == $item) {
$prev = $cur->prev;
$next = $cur->next;
if ($prev != null) {
$prev->next = $next;
} else {
// because head points to the first item
$this->head = $next;
}
if ($next != null) {
$next->prev = $prev;
}
return $cur;
}
$cur = $cur->next;
}
}
public function __toString()
{
$cur = $this->head;
$output = '';
while ($cur) {
$output .= $cur . ' ';
$cur = $cur->next;
}
return $output . "\n";
}
}
$ll = new LList();
$a = new Person('John', 'Smith', '555 9401');
$b = new Person('James', 'Johnes', '555 2454');
$c = new Person('Jeanne', 'Francois', '333 2323');
$ll->insert($a);
$ll->insert($b);
$ll->insert($c);
// prints objects $c, $b, $a:
// Jeanne Francois 333 2323
// James Johnes 555 2454
// John Smith 555 9401
echo $ll;
$ll->delete($b);
// prints objects $c, $a:
// Jeanne Francois 333 2323
// John Smith 555 9401
echo $ll;
Вставить до и вставить после
Для вставки до и после нужна ссылка на уже существующий элемент списка. После этого новый объект вставляется в нужное место, как показано на изображениях ниже.
Вставить после разбивает список после указанного элемента и вставляет туда новый объект!
class LList
{
public $head;
public $tail;
public function insert($item)
{
$item->next = $this->head;
if ($this->head != null) {
$this->head->prev = $item;
}
$this->head = $item;
}
public function insertAfter($newItem, $item)
{
$cur = $this->head;
while ($cur) {
if ($cur == $item) {
$next = $cur->next;
$cur->next = $newItem;
$newItem->prev = $cur;
if ($next != null) {
$newItem->next = $next;
$next->prev = $newItem;
}
return;
}
$cur = $cur->next;
}
$this->head = $this->tail = $item;
}
public function __toString()
{
$cur = $this->head;
$output = '';
while ($cur) {
$output .= $cur . ' ';
$cur = $cur->next;
}
return $output . "\n";
}
}
$ll = new LList();
$a = new Person('John', 'Smith', '555 9401');
$b = new Person('James', 'Johnes', '555 2454');
$c = new Person('Jeanne', 'Francois', '333 2323');
$ll->insert($a);
$ll->insert($c);
// inserts $b after $a
$ll->insertAfter($b, $c);
// Jeanne Francois 333 2323
// James Johnes 555 2454
// John Smith 555 9401
echo $ll;
Вставить новый объект до того, как элемент будет таким же, как вставка после, но вместо того, чтобы разбивать список после данного элемента, мы разделяем его перед ним.
Вставьте до и вставьте после очень похожие операции!
Поиск
Поиск в списке может быть изменен в зависимости от потребностей приложения. Здесь мы просто сравниваем искомый объект с элементом списка.
class LList
{
public $head;
public $tail;
public function insert($item)
{
$item->next = $this->head;
if ($this->head != null) {
$this->head->prev = $item;
}
$this->head = $item;
}
public function insertAfter($item, $key)
{
$cur = $this->head;
while ($cur) {
if ($cur->data == $key) {
$next = $cur->next;
$cur->next = $item;
$item->prev = $cur;
if ($next != null) {
$item->next = $next;
$next->prev = $item;
}
return;
}
$cur = $cur->next;
}
$this->head = $this->tail = $item;
}
public function search($item)
{
$cur = $this->head;
while ($cur) {
if ($cur == $item) {
return 1;
}
$cur = $cur->next;
}
return 0;
}
public function __toString()
{
$cur = $this->head;
$output = '';
while ($cur) {
$output .= $cur . ' ';
$cur = $cur->next;
}
return $output . "\n";
}
}
$ll = new LList();
$a = new Person('John', 'Smith', '555 9401');
$b = new Person('James', 'Johnes', '555 2454');
$c = new Person('Jeanne', 'Francois', '333 2323');
$ll->insert($a);
$ll->insert($b);
// 1, because $b is in the list
echo $ll->search($b);
// 0, cause $c isn't in the list
echo $ll->search($c);
Операции здесь представляют собой только один поднабор всех возможных операций, которые вы можете выполнить в связанном списке. Все зависит от наших потребностей. Однако принципы важны, поэтому мы можем реализовать более сложные структуры данных.
заявка
Это правда, что связанный список — это очень простая структура данных. Кто-то может задаться вопросом, почему мы должны кодировать и реализовывать связанный список, поскольку мы можем делать то же самое (почти со всеми современными языками программирования / библиотеками) с массивами. Ответ заключается в том, что структуры данных в виде деревьев сложно реализовать с помощью массивов, поэтому их легко кодировать с помощью указателей. Таким образом, связанные списки являются базовым уровнем для их понимания. Действительно, каждый связанный список представляет собой дерево только с одной ветвью, как показано на рисунке ниже.
Каждый связанный список — это одно дерево веток!