[자료구조] Search element in Singly Iinked list (store in dynamic array)

linked list에서 원소를 찾아 그 원소의 위치값을 메모리동적할당된 배열에 저장하는 코드입니다. 이해를 돕기위해 아래에 코드와 함께 다이어그램을 첨부합니다.

 

아래는 singly linked list 에서 입력받은 값의 위치를 찾는 알고리즘입니다.

 

https://www.javatpoint.com/program-to-search-an-element-in-a-singly-linked-list

Program To Search An Element In A Singly Linked List - javatpoint

이곳에서 소스 참고했습니다. 원문에서는 값이 list 내에 한번 존재하는 것으로 가정하고 int 변수를 선언하여 위치를 저장하였습니다.

 

값이 list 안에 중복되서 여러번 존재할 경우 int 변수로 값을 다 수용하지 못합니다. 이 때 다른 형태의 저장공간이 필요한데요. list에서 찾은 값의 위치를 동적 메모리할당을 사용하여 배열에 하나씩 저장하는 방식으로 코드 짜봤습니다. (dynamic memory allocation, reallocation, array)

 

참고한 소스코드에서 아래의 함수부분만 변경했습니다.

void search(int a){
    struct node *temp = head;
    int i = 1;
    int j = 0;
    int *arr = (int*)malloc(sizeof(int)*i);
    
    while(temp!=NULL){
        if(a==temp->data){
            arr[i-1] = j;
            i++;
            realloc(arr,sizeof(int)*i);
        }
        j++;
        temp = temp->next;
    }
    if(i==1){
        printf("찾는 값은 배열에 존재하지 않습니다.");
    }
    else{
        printf("찾는 값의 배열 내 위치는\n");
        for(int b = 1;b<i;b++){
            printf("%d ", arr[b-1]);
        }
        printf("입니다.");
    }
    
}

i 는 배열의 인덱스이고 j는 리스트에서의 값의 위치를 의미합니다.

처음 배열에 동적할당으로 4비트 할당, if문에서 리스트에서 값을 찾을 때마다 4비트씩 추가로 할당하는 방식입니다. 

 linked list 1->3->1->3->2->4->2 에서 원소 3을 찾게한 결과입니다.

 

이해를 돕기위해 아래의 다이아그램을 만들어 봤습니다. 이해하기 힘드신 분들은 코드랑 그림 같이 보시면 됩니다.

 

이 방법이 효율적인지 아닌지는 잘 모르겠습니다. 그냥 한번 해봤습니다. 고수분계시면 피드백 부탁드립니다.