Linked Sorted List

전반적으로 Linked Unsorted List와 비슷하다. 다른 몇 가지만 살펴보자.

 

Linked SortedType

 

sortedList 에서 RetrieveItem() 할 때는 binary Search를 썼었다.

근데 Linked에서는 동적배열이니 midPoint를 찾는게 더 복잡하다.

따라서 그냥  맨 앞에서부터 하나씩 비교하면서 찾는다. 

 

void RetrieveItem(ItemType &item, bool found)

item이 location의 info보다 작으면 다음 것을 조사, 같으면 ok. 그런데 item이 location의 info보다 커지면 그 후로부터는 더 이상 조사할 필요가 없다. 이후 노드의 info는 전부 item보다 클 것이기 때문.

template <class ItemType>
void RetrieveItem(ItemType &item, bool found){
	NodeType<ItemType>* location;
    location = listData;
    found = false;
    bool moreToSearch = (location != NULL);
    
    while(!found && moreToSearch){
    	if(item < location -> info){
        	location = location -> next;
            }
        else if(item == location -> info){
        	found = true;
        	item = location -> info;
            }
        else{
        	location = NULL;
        	}	
        }
    }

 

InsertItem(ItemType newItem)

링크드 unsorted 에서 insert 할 때는 그냥 맨 뒤에 붙여주기만 하면 됐었다. 이번에는 newItem이 들어갈 자리를 찾아줘야한다.

그런데 포인터를 하나만 이용하면 몇 가지 문제점이 발생한다. 

- 각 노드는 자신의 다음 노드만 알고 있다.

- 새로운 노드를 추가하면 이전 노드의 next가 새로운 노드를 가리키게, 새로운 노드의 next가 원래 이전노드의 다음노드를 가리키게 해야함.

- 그래서 (location -> info) 가 아니라 (location -> next -> info)를 봐야함. 

- item이 마지막에 들어가면 참조 오류가 발생한다! : location -> next = NULL이니까 info를 알 수 없음.

 

해결 : predLoc이라는 포인터를 하나 더 설정하자.

 

 

newNode는 새로운 값을 저장하는 노드, predLoc은 현 위치의 바로 이전 노드를 가리킨다.

sortedList이기 때문에 newItem이 location->info 보다 작은 노드 바로 앞!!에 insert한다.

template <class ItemType>
void SortedType<ItemType>::InsertItem(ItemType newItem){
    NodeType<ItemType>* newNode;
    NodeType<ItemType>* preLoc;
    NodeType<ItemType>* location;
    bool moreToSearch;

    location = listData;
    preLoc = NULL;
    moreToSearch = (location != NULL);

    while(moreToSearch){
        if(newItem > location -> info){
            preLoc = location;
            location = location -> next;
            moreToSearch = (location != NULL);
        }
        else{
            moreToSearch = false;
        }

        newNode = new NodeType<ItemType>;
        newNode -> info = newItem;
        if(preLoc == NULL){
            newNode -> next = listData;
            listData = newNode;
        }
        else{
            newNode -> next = location;
            preLoc -> next = newNode;
        }
        length++;
    }
}

 

 

시간복잡도

SortedList의 시간복잡도