연결리스트 구현(C언어로)

연결 리스트

연결리스트는 기본적인 자료구조이지만 구현하는것이 쉽지 않다.

특히 C에서는 이중 포인터를 사용해야 하기 때문에 많이 어려워

면접에서도 많이 물어보는 질문이다.

구현

메인함수

int main(void) {
  node_t* head = NULL;

  inser_front(&head, 3); // 맨 앞에서 삽입하는 함수
  inser_front(&head, 1);
  insert_mid(&head, 4); // 중간 삽입 함수
  insert_mid(&head, 2);
  delete_node(&head, 2); // 삭제 함수
  print_node(head); // 출력함수
}

이중포인터

이중 포인터를 사용하는 것이 핵심이다.

이중포인터를 왜 사용해야 하는가는 https://chanywa.com/343 이 글에서 잘 설명되어 있다.

이 함수를 호출한 후의 의도가 중요한데, 함수를 호출했을 때 해당 함수에서 외부 함수의 데이터에 접근하여 값을 변경하려면 이중포인터가 필요하다.

int global_val = 30;

void call_by_value(int *val)
{
	    printf("%p\n", *val); // 0xa 
	
        val = &global_val;
        printf("%p\n", val); // 0x7ffcf0db118c
        printf("%d\n", *val); // 30
}

void call_by_refer(int **ref)
{
        *ref = &global_val;
        printf("%p\n",*ref); // 0x601030
}


int main()
{
        int local_val = 10;
        int *value = &local_val; 
        int *refer = &local_val; 
        
        printf("before : *value=%d, *refer=%d\n", *value, *refer);
        // before : *value=10, *refer=10
        
        call_by_value(value); 
        printf("%p\n",value); //0x601030

        call_by_refer(&refer); 
        printf("after  : *value=%d, *refer=%d\n", *value, *refer);
        //after  : *value=10, *refer=30
}
 

위 예시를 보면 알겠지만, call_by_value 함수에서 포인터 변수로 메모리 공간을 전달하려고 하면, val 변수는 메모리 주소를 값으로 저장하는 지역변수로만 선언이 되게 된다. 즉 함수 바깥의
변수에 접근을 할 방법을 잃는다. 이 변수에 특정 메모리 주소를 덮어씌워버리면 그 메모리 주소는 날아가 버리고 전역변수의 주소가 덮어씌워지지만, 이 변수는 로컬 함수에서만 사용되고 사라지는 변수이므로 바깥의 변수에 접근할 수 있는 방법이 사라지는 것이다.

즉, 변수를 지역함수에 넘기고 지역함수에서도 바깥 함수의 변수에 접근하고 싶다면 포인터로 주소값을 전달.
포인터 변수를 지역함수에 넘기고 지역함수에서도 바깥 함수의 포인터 변수에 접근하고 싶다면 이중 포인터로 포인터 변수의 주소값을 전달.

이를 해결하기 위한 방법은 이중 포인터를 사용하거나 파라미터로 넘어온 주소값을 새로운 포인터 변수에 저장해서 그 변수를 이용해 주소값을 활용하는 방법이 있다.

맨 앞에 노드 삽입

void insert_front(node_t** phead, int var){
  node_t* new_node;
  new_node = malloc(sizeof(node_t));
  new_node->value = var;
  new_node->next = *phead;

  *phead = new_node;

}

위에서 포인터 변수를 지역변수로 전달한 후에도 외부 함수의 포인터변수에 접근하기 위해서는 이중 포인터 변수를 사용해야 한다 했다. 때문에 이중 포인터로 헤드의 노드를 가리키는 포인터 변수의 주소를 받아왔다. 이렇게 해야 이 포인터 변수에 접근할 수 있으니깐.

새로운 노드를 동적할당 해주고, head가 가리키던 곳(*phead)을 new_node구조체의 next에 할당한다. 그리고 head를 앞으로 당겨줘야 하므로, 헤드에 저장된 포인터변수를 new_node로 수정해준다.

중간에 노드 삽입

오름차순으로 노드를 삽입하는 경우

void insert_mid(node_t** phead, int value){
  node_t* new_node; // 새로운 노드 포인터
  node_t** pp= phead; // 헤드를 가리키는 포인터변수의 주소값을 똑같이 만들어줌
			// 이 변수는 노드를 옮겨다니면서 현재 pointer를 저장할 예정

  new_node = malloc(sizeof(node_t));
  new_node -> value = value;

  while(*pp != NULL){ // pp는 노드가 NULL이 나올때까지 순회
    if((*pp)-> value >= value){ // 뉴 노드의 벨류가 가져온 벨류보다 크면
      break;   // 직전 노드와 지금 가리키는 노드 사이에 삽입되어야 함
    }
    pp = &((*pp)->next); // pp에는 현재 가리키고 있는 노드의 next의 주소값이 담김
    			// next의 주소값이 담기므로 *pp는 next가 가리키는 노드가 됨

  }
  new_node->next = *pp; // 새로운 노드의 next값을 현재 pp가 가리키고 있던 노드의 주소를 대입 = 새로운 노드가 다음 노드를 가리키게 됨
  *pp = new_node; // 현재 pp가 가리키고 있는 노드의 next의 값이 새로운 노드를 가리키게 함
}

10번은 보고 써보고 해야 이해될 거 같다. 간신히 이해했다.
이 함수에서 pp가 이중 포인터로 쓰이는 이유와 phead가 이중 포인터로 쓰이는 이유가 다르다. 이걸 구분해내면 이중 포인터에 대해 이해했다고 할 수 있을듯...

먼저 phead가 이중 포인터로 쓰인 이유는 위에 서술한, 외부 함수의 포인터 변수에 접근하기 위한 것이고, pp는 포인터 변수의 주소를 저장하기 위해서이다.

pp = &(*pp) -> next; 이 부분이 그 부분이다.

pp가 가리키는 노드의 next는 포인터 변수이다. 해당 포인터 변수의 주소값을 저장한다는 것은, next가 가리키는 주소값을 pp라는 변수가 가리키기 위해서이다. pp는 next를 통해 다음 노드를 가리키고 있다. 때문에 pp는 현재 가리키고 있는 노드의 value 값 확인과 다음 노드를 포인팅하는 것을 동시에 할 수 있다.

노드 삭제

void delete_node(node_t** phead, int value){
  node_t** pp = phead; // 

  while(*pp!=NULL){ // pp가 가리키는 노드가 없을 때까지
    if((*pp)->value == value){ // 현재 가리키는 노드의 값이 그 값이라면
      node_t* tmp = *pp; // 현재 가리키는 노드를 임시로 하나 가리키는 포인터 변수를 생성(free 시키기 위해서 필요함, pp를 옮겨버리면 접근이 불가능해지니까)
      *pp = (*pp)->next; // pp가 가리키는 next 포인터변수가 다음 노드를 가리키게 함
      free(tmp); // 메모리 해제
      break;
    }
    pp = &(*pp)->next; // 노드를 가리키는 포인터 변수를 다음 노드로 옮김
  }

}

*pp == next 포인터변수라는 것을 반드시 생각해야 한다. pp는 이 next 포인터 변수의 주소값을 저장하고 있다. 그러므로 *pp 는 next 가 가리키고 있는 노드의 주소값을 가지고 있다.

노드 출력

void print_node(const node_t* head){
  node_t* p;

  p = head;
  while(p != NULL){
    printf("%d", p->value);
    p = p-> next;
  }
}

노드 출력은 외부 함수에 접근할 필요가 없다. 그러므로 head 의 주소값을 복사해서 사용하고 폐기해야 한다. 오히려 외부 함수의 head 값을 건드리게 되면 head값이 마지막 노드를 가르키고 함수가 종료되어 버리기 때문에, 버그를 만들어낼 확률이 있다.

머리터지는 과정이었다...