[자료구조] 단순 연결 리스트(singly linked list) - 정리 및 연습문제

1. 리스트의 개념

리스트의 예

- 리스트는 배열과 달리 원소들 간의 논리적인 순서를 위한 자료구조이다.

- 원소들 간의 순서는 논리적으로(추상적으로) 지켜지며 원소가 저장되는 물리적인 위치는 상관하지 않는다.

- 배열의 순서 : 물리적 VS 리스트의 순서 : 논리적=추상적=의미적

- 배열을 이용해 리스트를 구현하면 논리적인 순서를 지키기 위해 원소의 이동이 많아진다.

- 따라서 리스트는 일반적으로 포인터 변수를 이용한 연결 리스트를 이용한다.

- 포인터 변수 : 다음 원소를 가리키는 위치 저장

- 포인터 변수와 동적 메모리 할당을 이용해 메모리 낭비를 막을 수 있다.

 

2. 배열을 이용한 리스트의 구현

자료의 삽입, 삭제가 빈번히 발생하는 상황에서 리스트를 배열로 구현하는 것은 자료 이동으로 인해 컴퓨팅 성능의 비효율을 유발한다.

4개의 원소를 가진 리스트 (1919, 1936, 1945, 1950, 1988)를 배열로 구현한다고 가정하자.

 

  배열을 이용하여 리스트를 구현하는 방법은 간단하게 리스트의 원소를 순서대로 배열에 저장하는 것이다. 간단하며 포인터를 위한 메모리가 필요없기 때문에 메모리 공간 활용 효율이 높다. 하지만 배열의 특성으로 인해 각 원소가 메모리에 순차적으로 저장될 것이다. 따라서 리스트에 삽입, 삭제와 같은 변동 발생 시 많은 시간이 걸리게 된다.

 

  리스트에 '1936'이 추가되어 (1919, 1936, 1945, 1950, 1988)이 되면 배열의 크기가 확장되어야 하며 1945, 1950, 1988은 한 칸씩 뒤로 밀려나야 한다. 이는 프로그래밍의 번거로움 뿐만 아니라 리스트와 관련된 프로그램의 실행 시간에도 큰 영향을 미친다. 만일 배열로 구현한 리스트의 원소가 2000개인데 프로그램 수행 중 리스트의 원소가 앞에서 두 번째 위치에 삽입되어야 한다고 가정해보자. 이 경우 1999개의 원소를 뒤로 한 칸씩 밀어야 한다. 삽입 뿐만 아니라 삭제 시에도 같은 상황이 발생한다. 때문에 실제 IT 서비스 환경에서 배열을 이용한 리스트의 구현은 잘 사용되지 않는다.

 

3. 포인터를 이용한 리스트의 구현

포인터를 이용해 구현된 리스트를 연결 리스트(linked list)라고 한다.

 

노드의 구조

  연결 리스트에는 노드(node) 개념을 사용한다. 노드는 데이터를 갖고있는 데이터 필드와 리스트의 다음 원소를 가리키는, 즉 다음 노드의 주소를 갖고있는 링크 필드(포인터)로 구성된다. 예시 리스트 (1919, 1936, 1945, 1950, 1988)를 표현하려면 4개의 노드가 필요하다.

 

연결 리스트의 표현

  예시 리스트는 1919 → 1945 → 1950 → 1998의 논리적인 순서를 갖는다. 이를 연결 리스트로 표현하면 위 그림과 같다. 그림은 추상화한 연결 리스트의 표현이며 각 원소가 저장된 메모리의 물리적인 주소는 순서에 상관없이 저장된다.

 

 

연결 리스트의 예시

  노드는 C언어에서 struct 데이터 타입으로 구현된다. 노드의 데이터 필드는 리스트의 원소값을 저장하기 위한 부분으로 필요에 따라 여러 필드로 이루어질 수 있다. 즉 데이터 필드에는 여러 종류의 값이나 정보가 저장될 수 있다. 링크 필드는 리스트에서 다음에 오는 리스트 원소가 저장되어 있는 노드 주소를 저장한다. 이 주소를 이용하여 다음 원소를 찾아간다. 링크 필드는 C언어에서 포인터 변수를 이용하여 구현된다.

  리스트의 head 포인터 변수는 연결 리스트의 시작 노드(리스트의 첫 번째 원소)를 가리킨다. 마지막 노드를 제외한 나머지 모든 노드의 링크는 논리적으로 바로 다음에 위치하는 노드를 가리키는 주소를 갖는다. 마지막 노드의 링크는 더 이상 가리킬 것이 없는 null 포인터로 표현한다.

 

4. 포인터 변수와 구조체 그리고 동적 메모리 할당

C언어에 대한 포스팅이 아니므로 연결 리스트를 구현하는데 필요한 정도의 내용만 다룬다.

 

4-1. 포인터 변수

포인터는 메모리 주소값을 저장하는 변수이다. 포인터 변수도 데이터 타입을 가진다.

 

  변수 a는 int 타입의 변수이며 정수 100을 저장한다. 포인터 변수 b는 int 타입 변수의 주소값을 저장할 수 있는 정수형 포인터 변수이다. 각각 ff00, ff18 주소의 메모리 공간을 할당받았다고 가정한다. 역참조 연산자 &를 사용해 변수 a의 메모리 주소 ff00을 포인터 변수 b에 할당한다.

 

int a = 100;
int *b;
b = &a;
 
printf("a is %d\n", a);        //a is 100
printf("*b is %d\n", *b);    //b is 100

  변수 a가 저장된 위치의 주소값을 ff00으로 가정하였다. 6라인에서 역참조 연산자 *를 사용하여 b의 저장 영역에서 ff00을 추출하고 추출된 ff00의 주소를 찾아가 ff00에 저장된 값 '100'을 반환한다. 따라서 출력문에서 둘 다 100이 출력된다.

 

int a;
int *p_a;
p_a = &a;    //p_a에 변수 a의 주소를 저장
a = 100        //a에 100을 저장
*p_a = 800    //p_a가 가리키고 있는 a의 주소를 찾아가서 800을 저장

역참조를 통해 값을 변경하면 지시하고 있는 변수의 값이 바뀐다. 즉 5라인은 a = 800;과 동일하다.

 

4-2. 구조체(struct)

구조체는 다양한 데이터형을 하나의 단위로 다룰 수 있다.

 

struct linked_list_node {
    int data;
    struct linked_list_node *link;
}

위 코드는 하나의 정수값과 포인터를 갖는 구조체를 정의한 것이다. int형 데이터를 갖는 연결 리스트의 노드를 이처럼 구현할 수 있다.

 

4-3. 동적 메모리 할당(malloc)

  배열처럼 실행 전에 배열 크기를 결정하면 배열이 실제 리스트 원소의 숫자보다 크면 메모리 낭비가, 작으면 실행 중 문제를 발생시킨다. 이러한 문제를 해결하기 위해 malloc() 함수를 이용해 프로그램 실행 중에 동적으로 메모리 공간을 할당받을 수 있다. 프로그램 실행 중에 메모리가 추가적으로 필요한 시점에 malloc() 함수를 사용하면 필요한 만큼 메모리 공간을 할당받고 이에 대한 주소값을 포인터 변수로 저장해 사용한다.

 

int a, *p_a;
float b, *p_b;
p_a = (int *)malloc(sizeof(int));
p_b = (float *)malloc(sizeof(float));
*p_a = 10;
*p_b = 3.14;
 
printf("a is %d, b is %f\n", *p_a, *p_b);
free(p_a);
free(p_b);

3라인: sizeof(int)는 int형 데이터의 메모리 공간 크기를 반환한다. malloc(sizeof(int))은 int형 데이터를 저장할 수 있는 크기의 메모리 공간을 할당하여 주소값을 반환한다. 이를 포인터 변수 p_a에 저장하여 p_a가 이를 가리킨다.

4라인: sizeof(float)은 float형 데이터의 메모리 공간 크기를 반환한다. malloc(sizeof(float))은 float형 데이터를 저장할 수 있는 크기의 메모리 공간을 할당하여 주소값을 반환한다. 이를 포인터 변수 p_b에 저장하여 p_a가 이를 가리킨다.

9,10라인: free() 함수로 할당받은 메모리 공간을 반환한다.

 

  프로그램을 설계할 때 필요한 메모리 공간을 정확하게 예측할 수 없기 때문에 실행 중에 메모리 공간 할당이 필요할 수 있다. 이 때 malloc() 함수와 포인터 변수의 활용이 필요하다.

 

5. 연결 리스트 노드의 삽입과 삭제

5-1. 연결 리스트 노드 삭제

연결 리스트의 노드 삭제는 삽입보다 간단하다.

연결 리스트의 초기 모습

  노드를 삭제하려면 삭제되어야 할 원소를 알려줘야 한다. 여기서 삭제되어야 할 원소를 포인터 변수 x로 가리킨다고 가정한다. x노드를 삭제하려면 x의 선행 노드인 i노드가 후행 노드인 j노드를 가리키게 해야 한다. 즉 i노드의 링크가 j를 가리키게 해야 한다.

 

연결 리스트의 노드 삭제 결과

100 → 200 → 300이었던 리스트는 이제 100 → 300 순서를 가진다.

 

연결 리스트의 노드 삭제 :
① 삭제할 노드의 선행 노드의 링크가 삭제할 노드의 후행 노드를 가리키게 한다.
② 삭제할 노드를 메모리에 반환한다.

 

5-2. 연결 리스트의 노드 삽입

연결 리스트의 초기 모습

  삽입을 하려면 삽입될 위치를 알아야 한다. 삽입될 위치는 i노드의 다음 위치로, 삽입될 노드는 x노드로 가정한다. x노드의 링크가 j노드를 가리키고 i노드의 링크가 x노드를 가리키게 한다. 연결 리스트의 삭제와 달리 삽입에서는 두 개 노드의 링크를 변경해야 한다. 이 순서를 지키지 않고 먼저 i노드의 링크가 x노드를 가리키게 하면 j노드의 주소를 잃게 되므로 삽입할 때는 신규 노드의 링크 먼저 변경해야 한다.

 

연결 리스트의 삽입 결과

 

연결 리스트의 노드 삽입(②, ③ 순서 중요) :
① 삽입할 노드를 생성한다.
② 삽입할 노드의 링크가 삽입될 위치의 후행 노드를 가리키게 한다.
③ 삽입될 위치의 선행 노드의 링크가 삽입할 노드를 가리키게 한다.

 

6. 연결 리스트의 구현 알고리즘

6-1. 연결 리스트의 생성

typedef struct listNode {        //연결 리스트의 노드 구조 정의
    int data[10];
    struct listNode* link;
} listNode;
 
typedef struct {            //리스트의 헤드 노드 구조 정의
    listNode* head;
} headNode;
 
headNode createLinkedList(void) {    //연결 리스트 생성
    headNode* H;
    H = (headNode*)malloc(sizeof(headNode*));
    H -> head = NULL;
    return head;
}

1라인: typedef struct 선언문을 사용하여 정의한다.

2라인: 노드의 데이터 필드는 int형 [10]의 공간을 할당한다.

3,4라인: struct listNode* link;

링크 필드는 다음 노드의 주소값을 저장하여 가리켜야 하기 때문에 listNode형 포인터로 정의한다. listNode형 포인터는 listNode 전체를 가리키는 포인터 변수가 된다.

6~8라인: 연결 리스트의 맨 앞은 일반적으로 '헤드 노드'라고 불리며 연결 리스트의 첫 번째 노드를 가리키는 역할을 한다. 헤드 노드는 데이터 필드가 필요 없고 첫 번째 노드를 가리키기 위한 링크 필드만 필요하므로 listNode형 포인터로 정의한다.

10라인: createLinkedList()는 헤드 노드를 하나 생성하여 반환하는 역할을 한다. (빈 연결 리스트)

11라인: 헤드 노드(headNode)를 가리키는 포인터 변수 H를 선언한다.

12라인: 헤드 노드(headNode)의 크기만큼의 메모리 영역을 할당받아 그 주소를 반환하여 H에 저장한다.

13라인: H의 링크 필드인 head에는 아직 가리킬 노드가 없으므로 null을 할당한다.

 

헤드 노드의 생성(빈 연결 리스트)

 

6-2. 연결 리스트의 마지막에 노드 삽입

void addNode(headNode* H, int x) {    //리스트의 마지막 노드에 삽입
    listNode* newNode;
    listNode* lastNode;
    newNode = (listNode*)malloc(sizeof(listNode));
    newNode -> data = x;
    newNode -> link = NULL;
 
    if(H -> head == NULL) {        //현재 리스트가 공백인 경우
        H -> head = newNode;
        return;
    }
 
    lastNode = H -> head;
    while(lastNode -> link != NULL) lastNode = lastNode -> link;
    lastNode -> link = newNode;
}

2라인: 삽입할 신규 노드를 newNode로 정의한다.

3라인: 연결 리스트에 노드가 존재하는 경우 마지막 노드를 lastNode로 정의한다.

4라인: newNode = (listNode*)malloc(sizeof(listNode));

newNode의 데이터 공간을 메모리에 할당받아 주소값을 newNode에 저장한다.

5,6라인: newNode의 데이터 필드에 x를 저장하고 링크 필드는 아직 가리키는 메모리 주소값(노드)이 없으므로 NULL을 할당한다.

한 개의 노드를 생성하여 데이터 필드에 100을 삽입한 모습. 주소값 5000은 이해를 돕기 위한 임의의 값이다.

8라인: 현재 연결 리스트가 공백인 경우 헤드 노드 H가 newNode를 가리킬 수 있도록 링크 필드에 newNode의 주소값을 저장하고 종료한다.

 

헤드 노드에서 newNode를 연결한 모습

13,14라인: 현재 연결 리스트가 공백이 아닌 경우 마지막 노드를 찾는다. 헤드 노드부터 시작하여(H -> head) 링크를 따라 다음 노드로 이동한다. 다음 노드의 링크가 NULL이 아닐 때 까지 반복(while(lastNode -> link != NULL))하여 마지막 노드를 찾는다.

15라인: 마지막 노드의 링크 필드에 newNode의 주소값을 저장하여 newNode를 가리키게 한다.

 

이 addNode 함수에 x를 각각 200, 300으로 두 번 더 호출하면 연결 리스트는 아래의 모습이 된다.

 

주소값은 이해를 돕기 위한 임의의 값이다.

 

6-3. 연결 리스트의 마지막 노드 삭제

void deleteNode(headNode* H) {        //리스트의 마지막 노드 삭제 연산
    listNode* prevNode;
    listNode* delNode;
    if(H -> head == NULL) return;    //빈 리스트인 경우 삭제할 노드가 없으므로 종료
    if(H -> head -> link == NULL) {    //리스트에 노드가 한 개인 경우
        free(H -> head);    //그 노드의 메모리 해제
        H -> head = NULL;
        return;
    }
    else {                //리스트에 노드가 2개 이상인 경우
        prevNode = H -> head;
        delNode = H -> head -> link;
        while(delNode -> link != NULL) {
            prevNode = delNode;
            delNode = delNode -> link;
        }
        free(delNode);
        prevNode -> link = NULL;
    }
}

2라인: 삭제할 노드의 선행 노드를 가리킬 변수

3라인: 삭제할 노드를 가리킬 변수

4라인: if(H -> head == NULL)

    빈 연결 리스트인 경우 삭제할 노드가 없으므로 종료

5~9라인: if(H -> head -> link == NULL)

    연결 리스트에 노드가 한 개인 경우 해당 노드를 삭제하면 된다. free() 함수로 해당 노드의 메모리를 힙 영역에 반환하고 헤드 노드의 링크 필드에 NULL 할당

10라인: 연결 리스트에 노드가 2개 이상인 경우

11라인: 삭제할 노드의 선행 노드를 첫 번째 노드로 지정

12라인: 삭제할 노드를 두 번째 노드로 지정

13~16라인: 링크 필드가 NULL이 아닐 때 까지 prevNode와 delNode를 뒤로 한 칸씩 이동

17라인: while문에서 나와 마지막 노드(삭제할 노드)를 찾으면 메모리 해제

18라인: 선행 노드의 링크 필드에 NULL 할당

 

연결 리스트의 초기 상태와 삭제 결과

  연결 리스트 초기 상태가 위와 같다면 13~16라인의 while문을 1번 돌아 prevNode와 delNode는 각각 주소가 5500인 노드, 6000인 노드가 된다. 주소가 6000인 노드가 삭제되고 5500인 노드의 링크 필드에 null이 할당되어 마지막 노드가 된다.

 

6-4. 연결 리스트의 특정 노드 뒤에 삽입

다음은 삽입할 선행 노드(prevNode)에 대한 포인터를 매개변수로 받아서 처리하는 알고리즘이다.

void addItNode(headNode* H, listNode* prevNode, int x) {
    listNode* newNode;
    newNode = (listNode*)malloc(sizeof(listNode));
    newNode -> data = x;
    newNode -> link = NULL;
 
    newNode -> link = prevNode -> link;
    prevNode -> link = newNode;
    return;
}

2~5라인: 삽입할 노드 newNode 생성

7라인: newNode가 선행 노드 prevNode의 후행 노드(prevNode -> link)를 가리키게 함

8라인: prevNode가 newNode를 가리키게 함

 

  만일 7라인, 8라인의 순서를 지키지 않으면 후행 노드(prevNode -> link)를 연결할 수 없으므로 반드시 newNode의 링크 필드 먼저 변경해야 한다.

 

① 삽입할 newNode 생성

② newNode의 링크 필드가 prevNode의 링크를 가리키도록 변경

③ prevNode의 링크필드가 newNode를 가리키도록 변경

 

6-5. 연결 리스트의 특정 노드 삭제

다음은 삭제할 노드(delNode)와 삭제할 노드의 선행 노드(prevNode)에 대한 포인터를 매개변수로 받아서 처리하는 알고리즘이다.

void deleteItNode(headNode* H, listNode* prevNode, listNode* delNode) {
    prevNode -> link = delNode -> link;
    free(delNode);
    return;
}

2라인: 삭제 전 선행 노드가 후행 노드를 가리키도록 한다. (delNode -> link : 삭제할 노드의 후행 노드)

3라인: 노드를 삭제(메모리 반환)하고 프로그램을 종료한다.

 

① 연결 리스트 초기 상태

② prevNode의 링크 필드가 delNode의 링크를 가리키도록 변경

③ delNode 메모리 반환

 

6-6. 연결 리스트의 특정 노드 검색

  헤드 노드 부터 하나 씩 따라가며 특정 노드를 검색한다. 검색하고자 하는 노드가 존재하지 않거나 빈 리스트인 경우 등을 고려해야 한다. 다음은 빈 연결 리스트가 아니며 검색하고자 하는 노드가 반드시 존재한다고 가정한 알고리즘이다.

void searchNode(headNode* H, int x) {    //데이터 필드 값이 x인 노드 검색
    listNode* tempNode;
    tempNode = H -> head;
    
    while(tempNode -> data != x) {
        tempNode = tempNode -> link;
    }
 
    printf("Search Successful.\n");
}

2라인: 노드들을 차례로 탐색할 때 사용할 노드 정의

5~7라인: 찾고자 하는 값과 현재 노드의 데이터 필드 값을 차례로 비교

9라인: 대상 노드를 찾았으면 메시지 출력

 

  상황에 따라 검색한 노드의 주소값을 반환하는 등의 변경을 할 수 있다. 특정 노드를 검색하는 알고리즘을 연결 리스트의 특정 위치에 노드를 삽입하거나 특정 노드를 삭제하는 알고리즘과 결합하여 사용할 수 있다.

 

7. 연습문제

1. 다음 중 리스트에 대한 설명으로 틀린 것은?
① '일정한 순서'의 나열
② 어떤 정의에 의해서 결정된 '논리적인 순서'의 나열
③ 리스트를 포인터로 구현할 경우에는 배열에 비해서 추가적인 메모리 공간이 필요하다.
④ 메모리 공간에서의 물리적인 위치가 논리적인 위치와 동일하다.

2. 다음 프로그램은 2개의 노드로 구성된 연결 리스트의 노드 생성과 연결에 관한 프로그램이다. [가]와 [나]에 알맞은 것은 무엇인가?

① [가] ListNode* link; [나] H = (list_pointer) list_node;
② [가] struct ListNode* link; [나]  H = (linkedList_h*)malloc(sizeof(linkedList_h*))
③ [가] struct LinkNode* link; [나] H = struct list_node;
④ [가] LinkNode* link; [나] H = list_node -> data;

3. 다음 중 연결 리스트에 대한 설명으로 틀린 것은?
① 데이터가 '논리적인 순서' 혹은 리스트에 나타나는 원소들간의 '의미적인 순서'를 유지한다.
② 원소의 순서가 메모리 공간에서의 물리적 순서를 의미한다.
③ 원소들의 물리적인 저장 순서나 위치와는 무관하게 원소들간의 논리적인 순서만 유지해주면 된다.
④ 배열을 이용하여 구현할 수 있다.

4. 10과 3.14를 출력하기 위해 [가]와 [나]에 알맞은 것은 무엇인가?

 

정답 ▼

1 : ④
2 : ②
3 : ②
4 : ④