지난 글에서 우리는 이미 단순한 단방향 연결 목록 외에도 여러 가지 형태의 연결 목록이 있다고 말했습니다. 물론 이것은 매우 유연하고 편리한 연결리스트 구조의 주요 특징이기도 합니다. 간단히 생각해 보면, 마지막 노드 중 다음 노드가 다시 첫 번째 노드를 가리키는 경우 이는 순환 연결 리스트인 링을 형성하게 됩니다.
이전 노드를 가리키는 각 노드에 prev 속성을 추가하면 연결 리스트는 이중 연결 리스트가 됩니다. 양방향 연결리스트를 기반으로 마지막 노드의 다음 노드가 첫 번째 노드를 가리키고 첫 번째 노드의 이전 노드가 마지막 노드를 가리키도록 한다면 이는 양방향 순환 연결리스트가 아닐까요? 아래에서 자세히 살펴보겠습니다.
위에서 언급한 것처럼 마지막 노드가 첫 번째 노드를 가리키도록 하고 이렇게 형성된 연결 리스트는 아래 그림과 같이 순환 연결 리스트가 됩니다.
에 대하여 순환 연결 리스트의 동작 사실 자세한 설명은 하지 않겠습니다. 사실 대부분의 코드는 단방향 연결 리스트와 동일하지만, 초기화할 때 두 가지에 주의해야 합니다. 그리고 연산 삽입 시 마지막 노드의 방향, 마지막 노드의 다음 노드를 주목하세요
2. 연결리스트 순회 완료 여부를 판단하는 조건은 항목->다음 == 헤드입니다. 즉, 이 노드의 다음 노드가 헤드 노드이면 연결리스트 순회가 완료됩니다.
이중 연결 목록
// 双向链表
class LinkedList
{
public $data;
public $prev;
public $next;
}
다음으로 이중 연결 리스트를 초기화합니다.
/**
* 生成链表
*/
function createLinkedList()
{
$list = new LinkedList();
$list->data = null;
$list->next = null;
$list->prev = null; // ** 全部都初始化为 null **
return $list;
}
/**
* 初始化链表
* @param array $data 链表中要保存的数据，这里以数组为参考
* @return LinkedList 链表数据
*/
function Init(array $data)
{
// 初始化
$list = createLinkedList();
$r = $list;
foreach ($data as $key => $value) {
$link = new LinkedList();
$link->data = $value;
$link->next = null;
$r->next = $link;
$link->prev = $r; // ** 增加上级指向 **
$r = $link;
}
return $list;
}
$link = Init(range(1, 10));
var_dump($link);
var_dump($link->next->next->next->next);
// object(LinkedList)#5 (3) {
// ["data"]=>
// int(4)
// ["prev"]=>
// object(LinkedList)#4 (3) {
// ["data"]=>
// int(3)
// ["prev"]=>
// object(LinkedList)#3 (3) {
// ["data"]=>
// int(2)
// ["prev"]=>
// object(LinkedList)#2 (3) {
// ["data"]=>
// int(1)
// ["prev"]=>
// object(LinkedList)#1 (3) {
// ["data"]=>
// NULL
// ["prev"]=>
// NULL
// ["next"]=>
// *RECURSION*
// }
// ["next"]=>
// *RECURSION*
// }
// ["next"]=>
// *RECURSION*
// }
// ["next"]=>
// *RECURSION*
// }
// ["next"]=>
// object(LinkedList)#6 (3) {
// ["data"]=>
// int(5)
// ["prev"]=>
// *RECURSION*
// ["next"]=>
// object(LinkedList)#7 (3) {
// ["data"]=>
// int(6)
// ["prev"]=>
// *RECURSION*
// ["next"]=>
// object(LinkedList)#8 (3) {
// ["data"]=>
// int(7)
// ["prev"]=>
// *RECURSION*
// ["next"]=>
// object(LinkedList)#9 (3) {
// ["data"]=>
// int(8)
// ["prev"]=>
// *RECURSION*
// ["next"]=>
// object(LinkedList)#10 (3) {
// ["data"]=>
// int(9)
// ["prev"]=>
// *RECURSION*
// ["next"]=>
// object(LinkedList)#11 (3) {
// ["data"]=>
// int(10)
// ["prev"]=>
// *RECURSION*
// ["next"]=>
// NULL
// }
// }
// }
// }
// }
// }
// }
echo $link->next->next->next->next->data, PHP_EOL; // 4
echo $link->next->next->next->next->prev->data, PHP_EOL; // 3단방향 연결리스트와 다른 점은 prev 속성에 연산이 더 많다는 점을 알 수 있습니다. 여기서는 비교적 이해하기 쉽습니다. 연결된 목록을 직접 인쇄하면 PHP의 출력 보호 메커니즘인 많은 *RECURSION* 콘텐츠가 표시됩니다. 이 표시는 현재 속성 변수가 재귀 유형임을 나타냅니다.
/**
* 链表指定位置插入元素
* @param LinkedList $list 链表数据
* @param int $i 位置
* @param mixed $data 数据
*/
function Insert(LinkedList &$list, int $i, $data)
{
$j = 0;
$item = $list;
// 遍历链表，找指定位置的前一个位置
while ($j < $i - 1) {
$item = $item->next;
$j++;
}
// 如果 item 不存在或者 $i > n+1 或者 $i < 0
if ($item == null || $j > $i - 1) {
return false;
}
// 创建一个新节点
$s = new LinkedList();
$s->data = $data;
// 新创建节点的下一个节点指向原 i-1 节点的下一跳节点，也就是当前的 i 节点
$s->next = $item->next;
// ** 增加当前新创建的节点的上级指向 **
$s->prev = $item;
// 将 i-1 节点的下一跳节点指向 s ，完成将 s 插入指定的 i 位置，并让原来的 i 位置元素变成 i+1 位置
$item->next = $s;
// ** 将下级节点的 prev 指向新创建的这个节点 **
$s->next->prev = $s;
return true;
}연결된 목록을 삽입하면 실제로 두 줄의 코드가 추가됩니다. 하나는 현재 새로 생성된 노드의 상위 노드에 대한 포인터입니다. 즉, 이 새 노드의 상위 노드가 i-1 노드로 지정됩니다. 다른 하나는 원래 i 위치 노드의 상위 포인터를 새로 생성된 노드로 변경하는 것입니다.
/**
* 删除链表指定位置元素
* @param LinkedList $list 链表数据
* @param int $i 位置
*/
function Delete(LinkedList &$list, int $i)
{
$j = 0;
$item = $list;
// 遍历链表，找指定位置的前一个位置
while ($j < $i - 1) {
$item = $item->next;
$j++;
}
// 如果 item 不存在或者 $i > n+1 或者 $i < 0
if ($item == null || $j > $i - 1) {
return false;
}
// 使用一个临时节点保存当前节点信息，$item 是第 i-1 个节点，所以 $item->next 就是我们要找到的当前这个 i 节点
$temp = $item->next;
// 让当前节点，也就是目标节点的上一个节点， i-1 的这个节点的下一跳（原来的 i 位置的节点）变成原来 i 位置节点的下一跳 next 节点，让i位置的节点脱离链条
$item->next = $temp->next;
// ** 让目标下一个节点的上级指针指向当前这个节点 **
$temp->next->prev = $item;
return true;
}삽입 노드 연산과 유사하게, 삭제 노드 연산은 i-1 위치 노드의 데이터 중 다음 노드의 포인팅을 i 노드의 다음 레벨 노드 포인팅으로 변경할 뿐만 아니라, i의 다음 레벨 노드 노드의 상위 노드는 i-1 노드를 가리킨다.
사실 이중 연결 리스트의 정의와 동작은 단방향 연결 리스트와 크게 다르지 않습니다. 본질적으로 상위 노드를 가리키는 prev가 하나 더 있다는 것뿐입니다. prev 속성에 대한 추가 작업입니다. 그렇다면 이 뛰어난 포인터는 어떤 이점을 가져다 줄까요? 연결된 목록을 순회할 때 prev를 사용하여 연결 목록을 역순으로 순회하는 추가 순회 방법을 갖습니다. 특정 요소를 검색할 때 동시에 두 방향에서 검색할 수 있어 효율성이 한 번에 두 배가 됩니다. O(n)의 원래 시간 복잡도는 즉시 O(n/2) 시간 복잡도가 될 수 있습니다.
양방향 순환 연결 리스트
요약
그러니 불안하거나 당황할 필요가 없습니다. 일반적인 단방향 연결 목록을 익히면 대부분의 사람을 한 순간에 죽일 수 있습니다. 하지만 오늘 배운 내용은 어떻습니까? 숙달할 수 있으면 적어도 익숙해질 수는 있다. 인생에서 가장 중요한 것은 행복해지는 것이다. 너무 무리하면 용이 되기도 하고 벌레가 되기도 한다. 현재 상황과 능력을 인식하는 것이 가장 중요합니다.
关于线性表的内容到此为止。物理结构的存储问题就是这样了，接下来我们就要逻辑结构的世界了。也是从最简单的开始，那就是栈和队列，不要怕，它们和 树、图 比起来真的是洒洒水啦！！
测试代码：
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2.线性表/source/2.4%20链表的其它形式.php
推荐学习：php视频教程
위 내용은 연결된 목록을 표현하는 다른 형태가 있나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
