[자료구조] PHP로 단순 연결 리스트 구현

 

---

 

1. Node 클래스

class Node 
{
    public $data; // 노드에 저장될 데이터
    public $next; // 다음 노드를 가리킴

    public function __construct($data) 
    {
        $this->data = $data;
        $this->next = null; // 초기에는 다음 노드가 없으므로 null
    }
}

 

2. LinkedList 클래스

class LinkedList 
{
    private $head;   // 리스트의 첫 번째 노드 (헤드)
    private $length; // 리스트의 길이 (노드의 개수)

    public function __construct() 
    {
        $this->head = null; // 초기에는 리스트가 비어있으므로 헤드는 null
        $this->length = 0;  // 초기 길이는 0
    }
    
    // 길이 반환
    public function getLength() 
    {
        return $this->length;
    }
    
    // 비어있는지 확인
    public function isEmpty() 
    {
    	return $this->length === 0;
    }
    
}

 

3. getNode()

public function getNode($index) 
{
    if ($index < 0 || $index >= $this->length) {
        return null;
    }
    $current = $this->head; // 헤드 노드에서 시작
    for ($i = 0; $i < $index; $i++) {
        $current = $current->next; // 찾는 노드를 찾을 때까지 순회
    }
    return $current;
}

 

4. getEntry()

public function getEntry($index) 
{
    $node = $this->getNode($index); // 해당 인덱스의 노드 객체를 가져옴
    if ($node !== null) {
        return $node->data; // 노드 객체가 존재하면 데이터 반환
    }
    return null; // 노드를 찾지 못했거나 인덱스가 유효하지 않으면 null 반환
}

 

5. insert()

/**
 * p번째 위치에 data 값을 갖는 노드 삽입
 * @param int $position 삽입할 위치 (0부터 시작)
 * @param mixed $data 삽입할 데이터
 * @return bool 삽입 성공 시 true, 실패 시 false
 */
public function insert(int $position, $data): bool 
{
    // 1. 새 노드 생성
    $newNode = new Node($data);
    $before = $this->getNode($position-1);
    // 2. 맨 처음에 삽입하는 경우
    if ($before == null) {
        $newNode->next = $this->head; // 새 노드의 다음을 현재 head로 설정
        $this->head = $newNode;       // head를 새 노드로 변경
    } 
    // 3. 중간 또는 맨 끝에 삽입하는 경우
    else {
        $newNode->next = $before->next; // 새 노드의 다음을 current의 다음 노드로 설정
        $before->next = $newNode;       // current의 다음을 새 노드로 설정
    }

    $this->length++; // 리스트 길이 증가
    return true;
}

 

6. delete()

public function delete($position) 
{
    if ($position > $this->length || $this->isEmpty()) {
        return null; // 유효하지 않은 위치 또는 빈 리스트
    }
    
    if ($position == 0) {
    	$this->head = $this->head->next; // 제일 처음 노드를 삭제하는 경우
    } else {
        $before = $this->getNode($position - 1);
        $current = $this->getNode($position);
        $before->next = $cuurent->next; // 앞 노드에 현재 이후 노드 링크 추가
        $this->length--; // 리스트 길이 감소
    }
}

 

7. search()

// data 값이 들어있는 첫번째 노드의 위치 반환
public function search($data)
{
    $current = $this->head;
    for ($i = 0; $i <= $this->length - 1; $i++) {
    	if ($data == $current->data) {
            return $i;
        }
        $current = $current->next;
    }
    return false;
}