PHP 연결리스트 구현 방법

PHP 연결 목록 구현 방법: 먼저 PHP 샘플 파일을 만든 다음 헤드 노드를 초기화한 다음 특정 위치에 노드의 데이터를 설정하고 특정 위치에 노드를 삭제합니다. 위치.

추천: "PHP Video Tutorial"

Linked List

Linked List는 일반적인 기본 데이터 구조인 선형 테이블이지만 선형 순서로 데이터를 저장하지 않지만 포인터( 포인터) 각 노드의 다음 노드에 대한 포인터입니다.

연결된 목록 구조를 사용하면 데이터 크기를 미리 알아야 하는 배열 연결 목록의 단점을 극복할 수 있습니다. 연결 목록 구조는 컴퓨터 메모리 공간을 최대한 활용하고 유연한 동적 메모리 관리를 달성할 수 있습니다. 그러나 연결리스트는 배열을 무작위로 읽는 장점을 상실하며, 동시에 노드의 포인터 필드의 증가로 인해 연결리스트의 공간 오버헤드가 상대적으로 크다.

연결 목록에는 단방향 연결 목록, 이중 연결 목록, 순환 연결 목록 등 다양한 유형이 있습니다.

단방향 연결 목록

가장 간단한 유형의 연결 목록은 정보 필드와 포인터 필드라는 두 개의 필드를 포함하는 단방향 연결 목록입니다. 이 링크는 목록의 다음 노드를 가리키고 마지막 노드는 null 값을 가리킵니다.

PHP는 간단한 단방향 연결 목록을 구현합니다.

<?php

class Node
{
    private $Data;//节点数据
    private $Next;//存储下个点对象

    public function __construct($data, $next)
    {        $this->Data = $data;        $this->Next = $next;
    }

    public function __set($name, $value)
    {        if (isset($this->$name))            $this->$name = $value;
    }

    public function __get($name)
    {        if (isset($this->$name))            return $this->$name;        else
            return NULL;
    }
}

class LinkList
{
    private $head;//头节点
    private $len;

    /**
     * 初始化头节点
     */
    public function __construct()
    {        $this->init();
    }

    public function setHead(Node $val)
    {        $this->head = $val;
    }

    public function getHead()
    {        return $this->head;
    }

    public function getLen()
    {        return $this->len;
    }

    public function init()
    {        $this->setHead(new Node(NULL, NULL));        $this->len = 0;
    }

    /**
     * 设置某位置节点的数据
     * @param int $index
     * @param $data
     * @return bool
     */
    public function set(int $index, $data)
    {        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL && $i <= $index) {            $node = $node->Next;            $i++;
        }        $node->Data = $data;        return TRUE;
    }

    /**
     * 获取某位置节点的数据
     * @param int $index
     * @return mixed
     */
    public function get(int $index)
    {        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL && $i <= $index) {            $node = $node->Next;            $i++;
        }        return $node->Data;
    }

    /**
     * 在某位置处插入节点
     * @param $data
     * @param int $index
     * @return bool
     */
    public function insert($data, int $index = 0)
    {        if ($index <= 0 || $index > $this->getLen())            return FALSE;        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL) {            if ($index === $i) break;            $node = $node->Next;            $i++;
        }        $node->Next = new Node($data, $node->Next);        $this->len++;        return TRUE;
    }

    /**
     * 删除某位置的节点
     * @param int $index
     * @return bool
     */
    public function delete(int $index)
    {        if ($index <= 0 || $index > $this->getLen())            return FALSE;        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL) {            if ($index === $i) break;            $node = $node->Next;            $i++;
        }        $node->Next = $node->Next->Next;        $this->len--;        return TRUE;
    }
}

양방향 연결 목록더 복잡한 연결 목록은 "양면 연결 목록" 또는 "양면 연결 목록"입니다. . 각 노드에는 두 개의 연결이 있습니다. 하나는 이전 노드를 가리키고(이 "연결"이 첫 번째 "연결"인 경우 null 값 또는 빈 목록을 가리킴) 다른 하나는 다음 노드를 가리킵니다(이 "연결"인 경우). "는 첫 번째 "연결"이며 null 값 또는 빈 목록을 가리킵니다.); "마지막 "연결"인 경우 null 값 또는 빈 목록을 가리킵니다.)

원형 Linked List원형 연결 리스트에서는 첫 번째 노드와 마지막 노드가 함께 연결됩니다. 이 방법은 단방향 및 양방향 연결 목록 모두에서 구현될 수 있습니다. 순환 연결 목록을 변환하려면 임의의 노드에서 시작하여 시작 노드로 돌아올 때까지 어느 방향으로든 목록을 따라갑니다. 다른 방법을 살펴보면 순환 연결 리스트는 "headless and tailless"로 간주될 수 있습니다. 이러한 목록은 목록에 하나의 개체가 있고 다른 모든 개체를 비특정 배열로 반복하려는 경우 데이터 저장소 캐시를 절약하는 데 유용합니다. 전체 목록에 대한 포인터를 액세스 포인터라고 부를 수 있습니다.

기본 아이디어는 계속 업데이트할 시간이 거의 다가왔습니다

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