링크 와 배열 의 차이

링크 는 배열 과 마찬가지 로 데이터 구조 이다.
 
배열 은 요 소 를 메모리 에 연속 으로 저장 합 니 다. 모든 요소 가 메모 리 를 사용 하 는 것 이 같 기 때문에 아래 표 시 를 통 해 배열 의 모든 요 소 를 신속하게 방문 할 수 있 습 니 다.그러나 배열 에 요 소 를 추가 하려 면 대량의 요 소 를 이동 하고 메모리 에 요소 의 공간 을 비 운 다음 추가 할 요 소 를 넣 어야 합 니 다.같은 이치 로 원 소 를 삭제 하려 면 이동 하 는 원 소 를 채 우기 위해 대량의 원 소 를 이동 해 야 한다. 
체인 테이블 은 정반 대 이다. 체인 테이블 의 요 소 는 메모리 에 순서대로 저 장 된 것 이 아니 라 존재 하 는 요소 의 지침 을 통 해 연결된다.예 를 들 어 이전 요 소 는 다음 요 소 를 가리 키 는 지침 이 있 습 니 다. 이 를 통 해 마지막 요소 까지 유추 할 수 있 습 니 다.링크 의 한 요 소 를 방문 하려 면 첫 번 째 요소 부터 필요 한 요소 의 위 치 를 찾 아야 합 니 다.그러나 하나의 요 소 를 추가 하고 삭제 하 는 것 은 링크 데이터 구조 에 있어 매우 간단 합 니 다. 요소 의 지침 만 수정 하면 됩 니 다.
 
링크 구 조 를 사용 하면 배열 링크 는 데이터 크기 의 단점 을 미리 알 아야 한다. 링크 구 조 는 컴퓨터 메모리 공간 을 충분히 이용 하여 유연 한 메모리 동적 관 리 를 실현 할 수 있다.그러나 링크 는 배열 이 무 작위 로 읽 는 장점 을 잃 었 고 링크 는 결점 의 지침 도 메 인 을 증가 하기 때문에 공간 비용 이 비교적 크다.
 
링크 의 가장 뚜렷 한 장점 은 일반적인 배열 과 관련 된 항목 을 배열 하 는 방식 이 메모리 나 디스크 에서 의 순서 와 다 를 수 있 고 데이터 의 액세스 가 서로 다른 배열 순서 에서 전환 되 어야 한 다 는 것 이다.링크 는 같은 유형의 데 이 터 를 가리 키 는 지침 (링크) 을 포함 하기 때문에 자기 지시 데이터 형식 입 니 다.
 
위의 비 교 를 통 해 알 수 있 듯 이 데이터 에 빠르게 접근 해 야 한다 면 요 소 를 적 게 삽입 하거나 삭제 하지 않 으 면 배열 을 사용 해 야 한다.반면 요 소 를 자주 삽입 하고 삭제 하려 면 링크 데이터 구조 가 필요 하 다.
PHP 가 구현 하 는 단일 체인 시트 는 다음 과 같 습 니 다.

//   
class Node{
	private $next = NULL; //       
	private $data = NULL; //  

	public function Node($data, $next = NULL){
		$this->data = $data;
		$next && $this->next = $next;
	}
	public function getData(){
		return $this->data;
	}
	public function setData($data){
		$this->data = $data;
	}
	public function getNext(){
		return $this->next;
	}
	public function setNext($next){
		$this->next = $next;
	}
}
 
//    
class LinkList{
	private $data_list = NULL; //   
	 
	public function LinkList($data = false){
		$this->data_list = array();
		$title = new Node(NULL);
		$this->data_list[] = $title;
		 
		if($data){
			if(is_array($data)){
				$this->addMoreData($data);
			}else{
				$this->addData($data);
			}
		}
	}
	//   N     
	public function getNodeByNumber($number){
		return $this->data_list[$this->findKeyByNumber($number)]->getData();
	}
	//      
	public function addMoreData($datas){
		foreach($datas as $value){
			$this->addData($value);
		}
	}
	//        ,     
	//$number            
	public function addData($data, $number = false){
		$node = new Node($data);
		if($number === FALSE || $number == count($this->data_list)){
			$this->insertLastNode($node);
		}elseif($number > count($this->data_list)){
			return false;
		}else{
			$this->insertNode($node, $number);
		}
	}
	//         
	private function insertLastNode($node){
		$node->setNext(NULL);
		$lastKey = $this->findLastNode();
		$insert_key = $this->insertNodeIntoArray($node);
		$this->data_list[$lastKey]->setNext($insert_key);
	}
	//      
	private function insertNode($node, $number){
		$insert_number = $this->findKeyByNumber($number);
		$node->setNext($this->data_list[$insert_number]->getNext());
		$insert_key = $this->insertNodeIntoArray($node);
		$this->data_list[$insert_number]->setNext($insert_key);
	}
	//   N        key
	private function findKeyByNumber($number){
		$i = $key = 0;
		 
		while($i < $number){
			$key = $this->data_list[$key]->getNext();
			$i ++;
		}

		return $key;
	}
	//       
	private function insertNodeIntoArray($node){
		$this->data_list[] = $node;
		return $this->getLastKey();
	}
	//    
	public function deleteNode($number){
		if($number == 0  || $number > count($this->data_list)){
			return false;
		}
		 
		$pre_key = $this->findKeyByNumber($number - 1);
		$key = $this->data_list[$pre_key]->getNext();
		 
		$this->data_list[$pre_key]->setNext($this->data_list[$key]->getNext());
		unset($this->data_list[$key]);
	}
	 
	//           
	private function getPreNodeKey($key){
		foreach($this->data_list as $k=>$v){
			if($v->getNext() == $key){
				return $k;
			}
		}
		return false;
	}
	 
	//    
	public function getData_list(){
		return $this->data_list;
	}
	 
	//          
	private function getLastKey(){
		end($this->data_list);
		return key($this->data_list);
	}
	 
	//          
	private function ifExistKey($key){
		if(array_key_exists($key, $this->data_list)){
			return true;
		}
		return false;
	}
	//     
	public function findLastNode(){
		foreach($this->data_list as $key=>$value){
			if($value->getNext() === NULL){
				return $key;
			}
		}
	}
}