PHP의 연결리스트에 대한 자세한 설명

연결된 목록의 작업은 순차 목록의 작업보다 훨씬 복잡합니다. PHP는 실제로 우리를 위해 많은 배열 연산 문제를 해결해 주었기 때문에 배열을 매우 편리하게 연산할 수 있으며 배열에 대해 많은 논리 연산을 정의할 필요가 없습니다. 예를 들어 C에서는 배열의 길이 제한이 있지만 PHP에서는 이 문제를 고려하지 않습니다.

연쇄 구조의 정의

우선 선형 목록에 대한 이전 첫 번째 기사에서 연결 목록의 정의에 대해 이야기했습니다. 여기서는 연결 목록에 대한 이전 다이어그램을 검토하여 자세한 내용을 살펴보겠습니다. 연결리스트의 개념을 확실히 이해하세요.

그림의 노드를 클래스로 표현합니다:

/**
 * 链表结构
 */
class LinkedList
{
    public $data;
    public $next;
}

링크드 리스트 클래스는 두 개의 콘텐츠를 포함하며 데이터는 데이터를 나타내고 next는 다음 노드를 나타냅니다. .포인터. 하나의 링크가 다른 링크 안에 있는 체인과 마찬가지로 이것은 전설적인 링크드 리스트 구조입니다.

연결된 목록 생성 및 작업 초기화

/**
 * 生成链表
 */
function createLinkedList()
{
    $list = new LinkedList();
    $list->data = null;
    $list->next = 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;
        $r = $link;
    }
    return $list;
}

$link = Init(range(1, 10));

print_r($link);
// LinkedList Object
// (
//     [data] =>
//     [next] => LinkedList Object
//         (
//             [data] => 1
//             [next] => LinkedList Object
//                 (
//                     [data] => 2
//                     [next] => LinkedList Object
//                         (
//                             [data] => 3
//                             [next] => LinkedList Object
//                                 (
//                                     [data] => 4
//                                     [next] => LinkedList Object
//                                         (
//                                             [data] => 5
//                                             [next] => LinkedList Object
//                                                 (
//                                                     [data] => 6
//                                                     [next] => LinkedList Object
//                                                         (
//                                                             [data] => 7
//                                                             [next] => LinkedList Object
//                                                                 (
//                                                                     [data] => 8
//                                                                     [next] => LinkedList Object
//                                                                         (
//                                                                             [data] => 9
//                                                                             [next] => LinkedList Object
//                                                                                 (
//                                                                                     [data] => 10
//                                                                                     [next] =>
//                                                                                 )

//                                                                         )

//                                                                 )

//                                                         )

//                                                 )

//                                         )

//                                 )

//                         )

//                 )

//         )

// )

연결된 목록을 사용할 때 일반적으로 첫 번째 노드에 데이터가 포함되지 않도록 만들고, 데이터가 있는 첫 번째 노드를 가리키는 빈 노드 역할만 합니다. 이런 종류의 노드를 헤드 노드라고 부를 수 있습니다. 연결 리스트가 비어 있는지 여부를 판단해야 한다면 첫 번째 노드의 다음 노드가 비어 있는지 여부만 판단하면 됩니다. 위 코드에서 createLinkedList() 함수는 실제로 이러한 헤드 노드를 생성합니다.

그런 다음 Init() 초기화 함수를 통해 이 연결 목록을 구성합니다. 구성 과정은 상대적으로 간단합니다. 여기서는 배열을 전달하고 배열 구조에 따라 연결 목록을 구성합니다. 물론 실제 응용 프로그램에서는 연결 목록을 구성하는 데 어떤 데이터든 사용할 수 있습니다. 구성 과정은 복잡하지 않습니다. 현재 노드를 r 변수에 할당한 다음 새 노드를 만들고 r->next를 새로 만든 노드와 동일하게 만듭니다. 구성된 연결리스트에서 직접 출력되는 구조가 주석의 형태입니다.

연결된 목록 탐색

function IteratorLinkedList(LinkedList $link)
{
    while (($link = $link->next) != null) {
        echo $link->data, ',';
    }
    echo PHP_EOL;
}

연결된 목록의 탐색은 일부 데이터베이스의 커서 작업이나 반복자 모드의 작업과 매우 유사합니까? 맞습니다. 사실 커서와 반복자의 구조는 연결리스트의 형태입니다. 다음 노드가 없을 때까지 $next를 계속 찾아 연결 목록 순회를 완료합니다. 이 과정의 시간복잡도는 O(n)임을 알 수 있다.

삽입과 삭제

/**
 * 链表指定位置插入元素
 * @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;
    // 将 i-1 节点的下一跳节点指向 s ，完成将 s 插入指定的 i 位置，并让原来的 i 位置元素变成 i+1 位置
    $item->next = $s;

    return true;
}

/**
 * 删除链表指定位置元素
 * @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;

    return true;
}

// 插入
Insert($link, 5, 55);
// 遍历链表
IteratorLinkedList($link); // 1,2,3,4,55,5,6,7,8,9,10,

// 删除
Delete($link, 7);
// 遍历链表
IteratorLinkedList($link); // 1,2,3,4,55,5,7,8,9,10,

연결된 목록의 삽입과 삭제는 사실 매우 유사합니다. 둘 다 삽입 또는 삭제 위치에서 이전 요소, 즉 i-1번째 위치의 요소를 찾아야 합니다. 그런 다음 연결된 목록 요소의 삽입 및 삭제는 이 요소의 다음 포인터에 대한 연산을 통해 구현됩니다.

순회 및 위치 판단의 두 기능에 대한 코드는 실제로 동일합니다. 차이점은 생성할 때 새 노드를 생성한 다음 이 노드의 다음이 이전 i의 다음을 가리키도록 해야 한다는 것입니다. 1 위치 요소 그런 다음 위치 i-1에 있는 요소의 다음 요소를 새로 생성된 노드를 가리킵니다. 삭제 작업은 삭제할 i 위치의 노드를 임시 변수에 저장한 후, i-1 위치에 있는 요소의 다음 요소를 삭제된 위치 i의 다음 요소로 지정하는 것입니다.

위의 설명은 코드와 연계하여 차근차근 살펴보아야 합니다. 물론 아래 그림과 연계하여 학습할 수도 있습니다. 삽입 및 삭제 작업은 연결리스트 작업의 핵심이자 가장 복잡한 부분이므로 많은 이해와 숙달이 필요합니다.

위치 기반 검색, 데이터 기반 검색

/**
 * 根据位置查找元素位置
 * @param LinkedList $list 链表数据
 * @param int $i 位置
 */
function GetElem(LinkedList &$list, int $i)
{
    $item = $list;
    $j = 1; // 从第一个开始查找，0是头结点 
    while ($item && $j <= $i) {
        $item = $item->next;
        $j++;
    }

    if (!$item || $j > $i + 1) {
        return false;
    }
    return $item->data;

}

/**
 * 根据数据查找数据元素所在位置
 * @param LinkedList $list 链表数据
 * @param mixed $data 数据
 */
function LocateElem(LinkedList &$list, $data)
{
    $item = $list;
    $j = 1; // 从第一个开始查找，0是头结点 
    while (($item = $item->next)!=null) {
        if($item->data == $data){
            return $j;
        }
        $j++;
    }

    return false;
}

// 获取指定位置的元素内容
var_dump(GetElem($link, 5)); // int(55)

// 获取指定元素所在的位置
var_dump(LocateElem($link, 55)); // int(5)

연결 목록에는 두 가지 형태의 검색이 있습니다. 하나는 위치를 지정하는 것입니다. 요소는 배열 인덱스와 마찬가지로 지정된 위치를 기준으로 검색됩니다. 그러나 연결리스트의 인덱스는 0부터 시작한다는 점에 유의해야 합니다. 왜냐하면 0의 위치가 우리의 헤드 노드이기 때문입니다. 물론 U-turn 노드를 무시하고 배열과 일치하도록 코드를 변경할 수도 있지만, 이 경우 연결리스트의 특성이 명확하지 않으므로 테스트 코드에서는 여전히 1부터 시작합니다. 여기.

또 다른 종류의 검색은 데이터 콘텐츠를 제공하고 연결된 목록에서 해당 위치를 찾는 것입니다. 실제로 두 알고리즘 모두 전체 연결 목록을 순회하며 본질적으로 차이가 없습니다. 연결된 목록에는 배열처럼 첨자를 쓸 수 있는 기능이 없으므로 검색 작업의 시간 복잡도는 O(n)입니다.

요약

어때요, 난이도가 점점 높아지네요. 연결된 목록의 작업은 훨씬 더 복잡해집니다. 이것은 단지 전채요리일 뿐입니다. 나중에 배우게 될 내용은 기본적으로 순차 목록(배열)과 연결 목록의 두 가지 형태를 중심으로 진행됩니다. 그리고 연결 목록에 대한 연구는 아직 끝나지 않았습니다. 다음 기사에서는 이중 연결 목록, 순환 연결 목록 및 이중 순환 연결 목록과 같은 다른 형태의 연결 목록을 더 자세히 살펴보겠습니다.

테스트 코드:

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2.线性表/source/2.3%20链表的相关逻辑操作.php

추천 학습: php 비디오 튜토리얼

위 내용은 PHP의 연결리스트에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!