연결된 목록을 표현하는 다른 형태가 있나요?

지난 글에서 우리는 이미 단순한 단방향 연결 목록 외에도 여러 가지 형태의 연결 목록이 있다고 말했습니다. 물론 이것은 매우 유연하고 편리한 연결리스트 구조의 주요 특징이기도 합니다. 간단히 생각해 보면, 마지막 노드 중 다음 노드가 다시 첫 번째 노드를 가리키는 경우 이는 순환 연결 리스트인 링을 형성하게 됩니다.

이전 노드를 가리키는 각 노드에 prev 속성을 추가하면 연결 리스트는 이중 연결 리스트가 됩니다. 양방향 연결리스트를 기반으로 마지막 노드의 다음 노드가 첫 번째 노드를 가리키고 첫 번째 노드의 이전 노드가 마지막 노드를 가리키도록 한다면 이는 양방향 순환 연결리스트가 아닐까요? 아래에서 자세히 살펴보겠습니다.

순환 연결 리스트

위에서 언급한 것처럼 마지막 노드가 첫 번째 노드를 가리키도록 하고 이렇게 형성된 연결 리스트는 아래 그림과 같이 순환 연결 리스트가 됩니다.

에 대하여 순환 연결 리스트의 동작 사실 자세한 설명은 하지 않겠습니다. 사실 대부분의 코드는 단방향 연결 리스트와 동일하지만, 초기화할 때 두 가지에 주의해야 합니다. 그리고 연산 삽입 시 마지막 노드의 방향, 마지막 노드의 다음 노드를 주목하세요

2. 연결리스트 순회 완료 여부를 판단하는 조건은 항목->다음 == 헤드입니다. 즉, 이 노드의 다음 노드가 헤드 노드이면 연결리스트 순회가 완료됩니다.

이중 연결 목록

이중 연결 목록은 LinkedList 클래스에 속성을 추가하여 이전 노드를 가리킵니다.

// 双向链表
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!