1. 연결리스트

연결리스트 

다음 연결에 대한 참조만을 갖는 기본적인 연결리스트. 첫 항목부터 순차적으로 접근하기 때문에 O(n)의 시간 복잡도를 갖는다. 기본적인 자료구조로 사용되는 배열의 경우 물리적으로 인접하여 접근 시간 단축 및 캐싱에 유리하지만, 연결리스트는 그렇지 않다. 하지만 배열에 비해 삽입이 간단하며 배열에 비해 사이즈 변경에 신경 쓸 일이 없다는 점에서 유리하다. 결론적으로 삽입은 연결리스트, 조회는 배열이 유리하다.

class Node{
	friend class linkedList;
	private:
		int value;
    		Node* link;
	public:
		Node(int v, Node* l):value(v),link(l) {}
};

class linkedList{
	private:
		Node* head;
	public:
		linkedList() {head=NULL;}
    
    	/*삽입, 삭제, 조회, 갱신 함수 구현*/
        
}

위는 C++을 이용한 기본적인 연결리스트 구현이다. 그리고 연결리스트(linkedList) 클래스에 기본 연산 함수인 삽입, 삭제, 조회, 갱신은 아래와 같다.

 

//헤드 위치에 노드를 삽입하는 방식

void insert(int value){
//새로 만든 노드에 지정한 값을 넣고 다음 링크는 현재 헤드이며 이렇게 설정한 노드 자체를 헤드로 초기화
    head = new Node(value, head);
}

위의 삽입 방식 외에도 연결리스트에 head와 더불어 tail까지 관리하여 맨 끝에 삽입, 특정 위치의 삽입 등이 가능하다.

 

//조회함수

boolean search(int value){
	for(Node* temp=head;temp;temp=temp->link){
    	if(temp->value==value)
        	return true; //조회하는 값이 존재.
    }
    
    return false; //리스트에 조회하는 값이 존재하지 않음.
}

 

//갱신함수

boolean update(int fromValue, int toValue){
	for(Node* temp=head; temp; temp=temp->link){
    		if(temp->value==fromValue){
        		temp->value=toValue;
           		return true;
        }
    }
    return false;
}

 

//삭제함수

boolean delete(int value){
    Node *deleteNode;
    Node *prevNode; //삭제할 노드의 이전 노드: 연결을 끊기 위함.
    if(head->value==value){
    	deleteNode=head;
    	head=head->link;
        free(deleteNode);
        return true;
    }else{
    	prevNode=head; 
        if(head->link) //리스트에 헤드노드 하나만 존재하는 경우를 대비하기 위한 조건문
        	deleteNode=head->link; 
        else
        	return false;
            
        //실제 탐색 후 삭제 로직
    	for(;deleteNode;deleteNode=deleteNode->link){
            if(deleteNode->value==value){
            	prevNode->link=deleteNode->link;
               	free(deleteNode);
               	return true;
            }else{
            	prevNode=prevNode->link;
            }
         }
     }
     return false;
}
            
            	

 

원형 연결리스트

마지막 노드가 첫번째 노드를 가리키는 연결리스트.

class CircularLinkedList{
	private:
		Node* tail;
	public:
		CircularlinkedList() {tail=NULL;}
    
    	/*삽입, 삭제, 조회, 갱신 함수 구현*/
        
};

기존의 연결리스트에서는 head를 사용했다. 하지만, 원형 연결리스트의 경우 마지막 노드가 head 노드를 가리키기 위한 로직을 위해 tail이라는 노드를 사용한다. 그러면 head는 어떻게 하냐? tail의 다음 노드는 head라는 것을 이용한다.

 

//마지막 노드 위치에 노드를 삽입하는 방식

void insert(int value){
	if(tail){
    	Node *new=new Node(value, tail->link); 
    	tail=tail->link=new;//tail의 다음 노드는 new로 갱신하고, new는 tail이 된다.
    }else{//리스트가 비어있을 경우
    	Node *new=new Node(value);
        new->link=new;
        tail=new;
    }
    size++;
}

//삭제함수

boolean delete(int value){
    Node *deleteNode;
    Node *prevNode; //삭제할 노드의 이전 노드: 연결을 끊기 위함.

    if(tail->value==value){
    	deleteNode=tail;
    	for(prevNode=tail; prevNode->link==tail; prevNode=prevNode->link);
        prevNode->link=tail->link;
        tail=prevNode;
        free(deleteNode);
        return true;
    }else{
    	prevNode=tail; 
        if(tail->link)
        	deleteNode=tail->link;
        else
        	return false;
        for(;deleteNode->value==value; deleteNode=deleteNode->link){
            prev=prev->link;
            if(prev==tail)
            	return false; //한 바퀴를 돌았지만 삭제할 값이 존재하지 않는 경우.
        }
        prev->link=deleteNode->link;
    	free(deleteNode);
        return true;
    }
    return false;
}
            
            	

조회와 갱신은 연결리스트와 매우 유사하여 생략

 

이중 연결리스트 

각 노드가 선행 노드와 후행 노드 모두를 가리키는 연결리스트.