집 >백엔드 개발 >PHP 튜토리얼 >PHP 데이터 구조 기본: 이중 연결 리스트

PHP 데이터 구조 기본: 이중 연결 리스트

不言원래의: 2018-07-06 17:29:101660검색

이 글에서는 PHP 데이터 구조의 기본이 되는 이중 연결 리스트를 중심으로 소개하고 있으며, 이는 특정 참조 값을 가지고 있습니다. 이제 도움이 필요한 친구들이 참고할 수 있습니다.

이중 연결 목록이란 무엇입니까?

실용적인 PHP 데이터 구조의 기본에 대한 이전 기사 - 단일 연결 목록

단일 연결 목록은 하나씩 노드인 개체로 구성됩니다. 다음 노드의 포인터, 마지막 노드의 포인터 필드는 null을 가리킵니다. 각 노드는 모든 데이터 유형을 저장할 수 있습니다.

이중 연결 리스트의 각 노드에는 각각 선행 노드와 후속 노드를 가리키는 두 개의 포인터 필드가 있습니다. 단일 연결 리스트는 단방향, 이중 연결 리스트는 양방향입니다.

공통 작업

이중 연결 목록에 대한 일반적인 작업은 다음과 같습니다.

insert
# 🎜🎜#
insertBefore
insertAfter
insertAt # 🎜🎜 #
...
PHP 언어 구현
먼저 기반을 구현합니다. 이중 연결 목록의 ListNode 클래스 정의에 대해 설명합니다.
```
class ListNode
{
    public $data = null;
    public $next = null;
    public $prev = null;

    public function __construct(string $data)
    {
        $this->data = $data;
    }
}
```
링크드 리스트 클래스를 보면 먼저 3개의 프라이빗 속성, 즉 헤드 노드, 테일 노드, 길이가 필요합니다.

class DoubleLinkedList
{
    private $head = null;
    private $last = null;
    private $length = 0;
}

다음 단계는 이전 규칙을 따르고 일반적으로 사용되는 첫 번째 삽입을 구현하는 방법을 직접 살펴보는 것입니다. 이는 평균 시간 복잡도가 O(n)인 작업입니다.

/**
 * 插入一个节点
 * @param string|null $data
 * @return bool
 * complexity O(n)
 */
public function insert(string $data = null)
{
    $newNode = new ListNode($data);
    if ($this->head) {
        $currentNode = $this->head;
        while ($currentNode) {
            if ($currentNode->next === null) {
                $currentNode->next = $newNode;
                $newNode->prev = $currentNode;
                $this->last = $newNode;
                $this->length++;
                return true;
            }

            $currentNode = $currentNode->next;
        }
    } else {
        $this->head = &$newNode;
        $this->last = $newNode;
        $this->length++;
        return true;
    }

}

노드 삭제 방법을 살펴보겠습니다.

/**
 * 删除一个节点
 * @param string $data
 * @return bool|ListNode
 * complexity O(n)
 */
public function delete(string $query = null)
{
if ($this->head) {
    $currentNode = $this->head;
    $prevNode = null;

    while ($currentNode) {
        if ($currentNode->data === $query) {
            if ($nextNode = $currentNode->next) {
                if ($prevNode) {
                    $prevNode->next = $nextNode;
                    $nextNode->prev = $prevNode;
                } else {
                    $this->head = $nextNode;
                    $nextNode->prev = null;
                }

                unset($currentNode);
            } else {
                if ($prevNode) {
                    $this->last = $prevNode;
                    $prevNode->next = null;
                    unset($currentNode);
                } else {
                    $this->head = null;
                    $this->last = null;
                }
            }

            $this->length--;
            return true;
        }

        $prevNode = $currentNode;
        $currentNode = $currentNode->next;
    }
}

    return false;
}

이중 연결 목록을 뒤집는 것도 그리 복잡하지 않습니다.

public function reverse()
{
    if ($this->head !== null) {

        if ($this->head->next !== null) {
            $reversedList = null;
            $currentNode = $this->head;

            while ($currentNode !== null) {
                $next = $currentNode->next;
                $currentNode->next = $reversedList;
                $currentNode->prev = $next;

                $reversedList = $currentNode;
                $currentNode = $next;

            }

            $this->last = $this->head;
            $this->head = $reversedList;
        }
    }
}

이중 연결 목록의 다른 작업에 대한 자세한 구현은 여기를 참조하세요.

이중 연결 목록은 단일 연결 목록에 비해 연결 목록 액세스 데이터 구조의 특별한 부분입니다. 또한 연결 목록 구조에는 단일 연결 목록, 순환 연결 목록 및 다중 연결 목록이 포함됩니다.

특수 시리즈

PHP 기본 데이터 구조 특수 시리즈 디렉터리 주소: https://github.com/... 주로 PHP 구문을 사용하여 기본 데이터 구조와 알고리즘을 요약합니다. 또한 일상적인 PHP 개발에서 쉽게 간과하기 쉬운 기본 지식과 현대 PHP 개발의 표준화, 배포 및 최적화에 대한 몇 가지 실용적인 제안도 포함되어 있으며 Javascript 언어의 특성에 대한 심층적인 연구도 포함되어 있습니다.

위 내용은 모두의 학습에 도움이 되기를 바랍니다. 더 많은 관련 내용은 PHP 중국어 홈페이지를 주목해주세요!

PHP 데이터 구조 기본: 이중 연결 리스트

이중 연결 목록이란 무엇입니까?

공통 작업

관련 기사