PHP 연결리스트 구현 방법

藏色散人

풀어 주다： 2023-03-06 21:32:02

원래의

2303명이 탐색했습니다.

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

PHP 연결리스트 구현 방법

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"로 간주될 수 있습니다. 이러한 목록은 목록에 하나의 개체가 있고 다른 모든 개체를 비특정 배열로 반복하려는 경우 데이터 저장소 캐시를 절약하는 데 유용합니다. 전체 목록에 대한 포인터를 액세스 포인터라고 부를 수 있습니다.