PHP에서 이중 연결 목록을 구현하기 위한 예제 코드

/**
 * **이중 연결 목록
 * @author zhiyuan12@
 * @modified 2012-10-25
 * @site: bbs.it-home.org
*/
/**
 * 연결리스트 요소 노드 클래스
*/
class Node_Element {
 public $pre = NULL; // 선행자
 public $next = NULL; // 후임자
 public $key = NULL; // 요소 키 값
 public $data = NULL; > function __Construct($key, $data) {
 $this->key = $key
 $this->data = $data;
 }
/ * *
 * 이중 연결 리스트 클래스
*/
class DoubleLinkedList {
 private $head; // 헤드 포인터
 private $tail; // 테일 포인터
 private $current; // 현재 포인터 len; // 연결 리스트 길이
 function __Construct() {
 $this->head = self::_getNode ( null, null )
 $this->curelement = $this-> head;
 $this->tail = $this->head;
 $len = 0
 }
 /**
 * @ desc: 연결리스트의 모든 노드 읽기
*/
 공용 함수 readAll() {
 $tmp = $this->head;
 while ( $tmp->next !== null ) {
 $tmp = $tmp->next
 var_dump ( $ tmp->key, $tmp->data );
 }
 }
 공개 함수 move($pos1, $pos2) {
 $pos1Node = $this->findPosition ( $ pos1 ); $pos2Node = $this->findPosition ( $pos2 )
 if ($pos1Node !== null && $pos2Node !== null) {
 $tmpKey = $pos1Node-> ;key;
 $tmpData = $pos1Node->data;
 $pos1Node->key = $pos2Node->key
 $pos1Node->data;
 $pos2Node->key = $tmpKey;
 $pos2Node->data = $tmpData
 return true
 }
 return false; **
 * @desc: 지정된 키워드의 노드 삭제
 *
 * @param: $key
 * 지정된 위치의 연결리스트 요소 키
*/
 공개 함수 delete($key) {
 $pos = $this->find ( $key )
 if ($pos !== null) {
 $tmp = $pos;
 $last = null;
 $first = true
 while ( $tmp->next !== null && $tmp->next->key = == $key ) {
 $tmp = $tmp->next;
 if (! $first) {
 $this->delNode ( $last ) } else {
 $first = false;
 }
 $last = $tmp;
 }
 if ($tmp->next !== null) {
 $pos->pre ->next = $tmp->next;
 $tmp->next->pre = $pos->pre
 } else {
 $pos->pre-> ;next = null;
 }
 $this->delNode ( $pos )
 $this->delNode ( $tmp ); *
 * @desc: 지정된 위치의 노드 삭제
 *
 * @param: $key
 * 지정된 위치의 연결리스트 요소 키
*/
 공용 함수 deletePosition($pos) {
 $tmp = $this->findPosition ( $pos )
 if ($tmp === null) {
 return true
 }
 if ($tmp === $this->getTail ()) {
 $tmp->pre->next =
 $this-> ;delNode ( $tmp );
 true를 반환합니다.
 }
 $tmp->pre->next = $tmp->next-> pre = $tmp->pre;
 $this->delNode ( $tmp )
 }
 /**
 * @desc: 지정된 키 값 앞에 노드를 삽입합니다.
 *
 * @param : $key
 * //지정된 위치에 연결된 목록 요소 키
 * @param: $data
 * //삽입할 연결리스트 요소 데이터
 * @param: $flag
 * //삽입 위치를 순차적으로 검색할지 여부
*/
 공개 함수 insert($key, $data , $flag = true) {
 $newNode = self::_getNode ( $key, $data )
 $tmp = $this->find ( $key, $flag )
 if ( $tmp !== null) {
 $newNode->pre = $tmp->pre
 $newNode->next = $tmp->pre = $newNode ;
 $newNode->pre->next = $newNode
 }else {
 $newNode->pre = $this->tail;
 $this->tail->next = $newNode;
 $this->tail = $newNode;
 }
 $this->len ;
 }
 /**
 * @desc: 지정된 위치 앞에 노드 삽입
 *
 * @param : $pos
 * 연결리스트에 삽입할 위치 지정
 * @param : $key
 * 해당 위치의 연결리스트 요소 키 지정
 * @param: $data
 * 삽입할 연결리스트 요소 데이터
*/
 공개 함수 insertPosition($pos, $key, $data) {
 $newNode = self::_getNode ( $key, $data );
 $tmp = $this->findPosition ( $pos );
 if ($tmp !== null) {
 $newNode->pre = $tmp->pre;
 $newNode->next = $tmp;
 $tmp->pre = $newNode;
 $newNode->pre->next = $newNode;
 } else {
 $newNode->pre = $this->tail;
 $this->tail->next = $newNode;
 $this->tail = $newNode;
 }
 $this->len ;
 true를 반환합니다.
 }
 /**
 * @desc: 키 값에 따라 지정된 위치 데이터를 쿼리
 *
 * @param: $key
 * //지정된 위치의 연결 리스트 요소 키
 * @ param: $flag
 * //순서대로 검색할지 여부
*/
 공개 함수 find($key, $flag = true) {
 if ($flag) {
 $tmp = $this-> ;머리;
 while ( $tmp->next !== null ) {
 $tmp = $tmp->next;
 if ($tmp->key === $key) {
 return $tmp;
 }
 }
 } else {
 $tmp = $this->getTail ();
 while ( $tmp->pre !== null ) {
 if ($tmp->key === $key) {
 return $tmp;
 }
 $tmp = $tmp->pre;
 }
 }
 null 반환;
 }
 /**
 * @desc: 위치를 기준으로 지정된 위치 데이터를 쿼리합니다.
 *
 * @param: $pos
 * //지정된 위치의 연결 리스트 요소 키
*/
 공개 함수 findPosition($pos) {
 if ($pos <= 0 || $pos > $this->len)
 null을 반환합니다.
 if ($pos < ($this->len / 2 1)) {
 $tmp = $this->head;
 $개수 = 0;
 while ( $tmp->next !== null ) {
 $tmp = $tmp->next;
 $개수 ;
 if ($count === $pos) {
 return $tmp;
 }
 }
 } else {
 $tmp = $this->tail;
 $pos = $this->len - $pos 1;
 $count = 1;
 while ( $tmp->pre !== null ) {
 if ($count === $pos) {
 return $tmp;
 }
 $tmp = $tmp->pre;
 $개수 ;
 }
 }
 null 반환;
 }
 /**
 * @desc: 연결리스트의 헤드 노드를 반환
*/
 공개 함수 getHead() {
 return $this->head->next;
 }
 /**
 * @desc: 연결리스트의 꼬리 노드를 반환합니다
*/
 공개 함수 getTail() {
 return $this->tail;
 }
 /**
 * @ desc: 연결리스트 노드 개수 쿼리
*/
 공개 함수 getLength() {
 return $this->len;
 }
 개인 정적 함수 _getNode($key, $data) {
 $newNode = new Node_Element ( $key, $data );
 if ($newNode === null) {
 echo "새 노드 실패!";
 }
 $newNode 반환;
 }
 비공개 함수 delNode($node) {
 unset( $node );
 $this->len --;
 }
}
// $myList = new DoubleLinkedList ();
// $myList->insert ( 1, "test1" );
// $myList->insert ( 2, "test2" );
// $myList->insert ( "2b", "test2-b" );
// $myList->insert ( 2, "test2-c" );
// $myList->insert ( 3, "test3" );
// $myList->insertPosition ( 5, "t", "testt" );
// $myList->readAll ();
// 에코 " ";
// $myList->deletePosition(0);
// $myList->readAll ();
// 에코 "..." . $myList->getLength ();
// var_dump ( $myList->findPosition ( 3 )->data );
?>