data structure(자료 구조) - Singly Linked List(단일 연결 리스트)의 노드 정의, 탐색 연산 구현::FBTT

지난번 글에서는 연결 리스트의 의미에 대해서 써보았습니다.

 

아래의 글을 보고 오신다면 이번 글에 대해 더 깊은 이해가 가능할 것 같습니다.

 

https://readytoearndon.tistory.com/30

data structure(자료 구조) - Linked list(연결 리스트)::FBTT

이번에는 연결 리스트 중 한 종류인 단일 연결 리스트에 대해 알아보겠습니다.

 

오늘은 노드를 정의하고 탐색을 간단하게 구현해보겠습니다.

 

 

 

노드의 정의

연결 리스트를 구현하기 전 노드에 대해서 정의해주어야 합니다.

 

저번 글에서 연결리스트는 자신의 data와 다음 자료의 주소를 가지는 link를 함께 저장한다고 했습니다.

 

그것을 node(노드)라고 합니다.

 

그렇다면 노드라는 자료는 정보와 다음 정보가 존재하는 위치를 함께 가지고 있어야합니다.

 

그래서 노드를 정의할 때 C에서는 struct, C++, JAVA등 에서는 class를 이용합니다.

typedef struct Node {
    int data;
    struct Node* next;
}node;

포인터를 이용하여 자신의 다음 노드를 가리킵니다.

 

 

 

탐색

기본적으로 사용하는 알고리즘의 idea는 배열에서 사용한 것과 동일합니다.

 

아래글에는 선형 탐색과 이진 탐색의 의미와 배열에서의 알고리즘 구현이 설명되어 있습니다.

 

https://readytoearndon.tistory.com/25

data structure(자료 구조) - Array(배열)와 search(탐색)연산::FBTT

단일 연결 리스트에서도 배열에서 사용한 탐색 연산 알고리즘을 이용할 것입니다.

 

그러나 연결 리스트에서는 배열에서 사용한 이진 탐색을 사용할 수 없습니다.

 

어째서 선형 탐색보다 성능이 좋았던 이진 탐색을 사용할 수 없는 것일까요?

 

이진 탐색은 주어진 자료 중 가운데에 있는 자료에 접근해야 합니다.

 

그런데 배열은 random access라고 했었죠. 그래서 중간 자료에 접근하는 것이 시간적인 측면에서 부담이 없었지만

 

연결 리스트는 sequential access라고 했었습니다. 중간에 있는 자료가 어디에 있는지는 중간 하나 전 자료만이 알고 있고 또 그 자료가 어디 있는지는 그 자료 전만이 알고 있기에 결국 중간에 있는 자료에 접근하기 위해서는 항상 처음부터 탐색해나가야 하기 때문에 비효율적입니다.

 

그래서 연결 리스트에서는 선형 탐색에 대해서만 알아보겠습니다.

 

선형 탐색은 처음부터 하나하나 확인하며 탐색하는 방법입니다.

typedef struct Node {
    int data;
    struct Node* next;
}node;
 
node* init = NULL;
 
node* linear_search(int key)
{
    node* current = init;
 
    while (current != NULL)
    {
        if (current->data == key)
            return current;
        current = current->next;
    }
 
    return NULL;
}

init은 자료를 저장하지는 않지만 리스트의 첫 번째 노드에 접근하는, 첫 번째 노드를 가리키는 포인터입니다.

 

함수 linear_search를 보면 처음 current라는 포인터는 현재 노드를 가리키는 포인터를 의미합니다.

 

다음 반복문을 보면 '현재 가리키는 노드가 있는가?'에 대해 물어봅니다.

 

있으면 현재 노드의 data에 접근해서 우리가 찾으려는 자료와 같은지에 대해서 알아봅니다.

 

같으면 현재 노드를 반환하고 아니면 다음 문장을 실행합니다.

 

다음 문장이 핵심이죠. 16번째 줄은 현재 노드를 현재 노드의 다음 노드를 가리키게 하는 문장입니다.

 

만약 반복문의 조건을 충족시키지 못하면, 그러니까 init이 가리키는 것이 없거나 current가 리스트의 끝까지 돌아 마지막 노드를 가리킬 때 NULL을 반환합니다.

 

init이 가리키는 것이 없는 경우는 리스트가 비어있는 경우이고 current가 마지막까지 돌았는데 key가 없다는 것은 리스트에 찾고자 하는 자료가 없는 경우입니다.

 

이 알고리즘은 배열에서 구현한 선형 탐색과 함께 비교해가며 보셨으면 좋겠습니다.

 

 

 

이번 글에서는 단일 연결 리스트의 노드 정의와 탐색에 대해 간단히 구현해보았습니다.

다음 글에서는 본격적으로 노드의 추가, 삭제 연산을 구현해보면서 링크를 어떤 식으로 연결해주어야 하는지 알아보겠습니다.