[리스트] 리스트의 기초와 단순 연결 리스트

게시 2023/08/01 업데이트 2024/06/01

By Yun Hyeok Nam

23 분읽는 시간

iOS의 미리알림 앱

🔍 리스트란?

우리는 일상생활에서 리스트 자료구조를 굉장히 많이 접한다. 당장 핸드폰의 전화번호부를 열어보면 알 수 있다. 전화번호부 앱에는 연락처들이 일렬로 저장된다. 또 다른 예시로는 To-Do 리스트 (할 일 리스트)가 있다. 원하는 우선순위에 따라 중요한 할 일은 위로 드래그 해서 둘 수도 있고, 이미 완료한 심부름이라면 할 일 리스트에서 제거도 할 수 있다.

이처럼 리스트는 데이터를 일렬로 (선형적으로) 저장할 수 있는 자료구조이다. 요소를 원하는 위치에 삽입하거나 제거하는 것이 자유롭다. 스택이나 큐 같은 경우는 요소를 넣고 뺄 수 있는 곳이 한정되어있다.

📖 (일반적인) 리스트의 추상자료형

  
객체:
    n개의 같은 자료형의 요소들로 구성된 순서 있는 모임.

연산:
    insert(pos, item) # pos 인덱스에 item 삽입
    delete(pos)       # pos 인덱스에 있는 요소 지우기
    clear()           # 리스트 싹 비우기

    getItem(pos)      # pos 인덱스에 있는 요소 리턴 (보통 요소의 레퍼런스, 참조를 리턴한다.)
    getIndexof(item)  # 리스트에 있는 어떤 item의 인덱스를 반환

    size()            # 리스트의 현재 길이

    isEmpty()         # 비어있는 리스트면 true 리턴
    # isFull()        # 보통의 리스트는 최대 용량 제한이 없다. 배열 리스트 같은 경우에는 
                      # isFull() 메서드가 있을 수도 있다고 볼 듯?

리스트가 가지는 추상자료형을 아주 간단하게만 보면 원하는 위치 및 리스트의 맨 앞, 뒤에 삽입-제거를 하는 연산과 각종 리스트의 속성을 리턴하는 메서드들(함수)로 구성된다고 보면 된다. 이는 말 그대로 추상자료형으로, 리스트가 어떤 코드, 알고리즘로 구현되는지는 프로그래밍 언어마다 다 다르고, 리스트를 구현한 컨테이너 (Java의 Collection, C++의 STL)도 그 종류가 각기 다르다. 예를 들면 Java의 ArrayList<>, LinkedList<>, Vector<>가 리스트의 기능을 가지는 컨테이너 템플릿들이다.

🚃🚃🚃 연결리스트란?

단순 연결리스트의 모습

연결리스트는 리스트 자료구조를 구현하는 하나의 방법이다. 연결리스트의 각 데이터는 노드라는 구조체로 구성되어있고, 이 노드들은 자신의 다음 노드를 가르키는 정보를 가지고 있다. 즉 맨 앞의 노드에서 다음 노드로, 다음 노드에서 또 다음 노드로 넘어가고 이를 반복해서 연결리스트의 끝에 도착할 수 있다. C언어에서는가르키는 정보 를 표현하기위해 포인터를 사용한다.

연결리스트는 노드간의 연결형태에 따라 크게 3가지로 나누어 볼 수 있다.

단순 연결리스트 (Singly linked list) : 앞에서 맨 뒤로 한 방향으로만 탐색가능. 리스트의 맨 끝은 NULL을 가르켜야한다.
원형 연결리스트 (Circular linked list) : 맨 뒤의 다음이 맨 앞으로 연결되어 있어 맨 뒤에 도달했어도 다시 맨 앞으로 이동할 수 있다.
이중 연결리스트 (Doubly linked list) : 노드가 자신의 앞, 뒤 노드로 연결되어있어 앞으로도, 뒤로도 이동하며 탐색가능하다.

💡 단순 연결리스트(Singly linked list)의 구현

리스트의 노드

  
typedef int element; // 노드에 담을 데이터의 자료형

typedef struct _LinkedNode
{
    element data; // 노드에 담을 데이터
    struct _LinkedNode* next; // 자기 참조 (자신을 다시 멤버로 가진다)
} LinkedNode;

우선 연결리스트에 사용할 노드의 구조체를 만든다. 여기서 노드는 자신의 다음 노드의 주소를 가지고있어야한다. 이를 구조체에 표현하기 위해 자기 참조를 사용한다. 이 경우에는 익명 구조체 (typedef struct (생략) {...} 구조체_별명; 형식)는 안되고 반드시 typedef struct 뒤에 구조체의 이름을 먼저 명시해야 한다.

그러고 구조체의 멤버로, 다음 노드의 주소를 담을 노드 구조체의 포인터 변수를 추가한다. 구조체의 멤버를 선언하는 동안에는 아직 struct 구조체명을 하나의 단어로 묶어쓸 수 없다. 따라서 struct _LinkedNode* next;의 형식으로 적어주는 것이다.

리스트의 헤더

리스트의 맨 앞은 Head 라고 하고, 맨 끝은 Tail 이라고 한다. (여기서 맨 끝은 맨 마지막 노드를 말한다. 맨 마지막 노드가 가르키는 NULL을 말하는 것이 아니다.)

리스트는 여러개의 노드로 구성된다. 특히 포인터로 구성되기 떄문에 노드의 주소 하나라도 잃어버리면 영 좋지 못한 결과가 일어날 것이다. 특히 단순 연결리스트의 맨 앞 노드의 주소를 잃어버리면 그 뒤에 딸린 노드는 영원히 찾을 수 없게 된다.

  
LinkedNode* head = NULL; // 리스트의 맨 앞은 head! 아직은 아무것도 없습니다.

위처럼 포인터 변수를 만들어 관리한다. 첫번째 노드 n1을 만들었다면, head = n1;의 코드를 통해 첫번째 노드를 리스트의 헤드노드로 표시한다. 아니면 헤더(Header) 구조체를 하나 만들어서 그 안에 리스트의 헤드 노드의 주소, 추가적으론 담긴 자료의 개수 등을 관리할 수도 있다.

헤더 구조체의 예시

  
typedef struct _LinkedHeader
{
    LinkedNode* head;   // 맨 앞 노드의 주소
    LinkedNode* tail;   // 맨 마지막 노드의 주소
    unsigned int count; // 노드의 개수
} LinkedHeader;

// 현재 리스트는 비어있습니다.
LinkedHeader header = {NULL, NULL, 0};

헤더 구조체를 사용하면 리스트에 삽입, 제거 연산 시 head 포인터를 다시 리턴해 줄 필요가 없다. 왜냐하면 모든 연산에 헤더 구조체의 주소를 넘기면, -> 연산자로 구조체의 멤버만 수정하기 때문에 복사본을 넘기는 이슈에 대해서는 생각할 필요가 없다.

  
// 헤더 구조체는 곧 연결리스트 자체를 의미한다.
// LinkedHeader를 List로, 별명으로 부르겠다.
typedef LinkedHeader List; 

List* list;
List_InsertFirst(&list); 
// 아래는 InsertFirst의 동작
// list 인자를 직접적으로 수정하지 않고, list가 가르키는 멤버들만 수정하므로 
// 복사본 문제를 생각할 필요가 없다.
{
    LinkedNode* newNode = NULL;
    newNode = List_CreateNode(newNode, item);
    ++list->size;

    if (list->head == NULL) { /* 리스트가 비었으면 바로 삽입하고 끝*/ }

    newNode->next = list->head;
    list->head = newNode;

    // 수정한 list를 return할 필요도 없다. list를 수정하지도 않았으니깐!
}

헤더 구조체를 사용해서 리스트에 요소를 삽입하는 연산은 위와 같다. 노드 포인터를 직접 넘기는게 아니라 노드 포인터를 가지는 구조체를 넘기므로 복사본 문제를 생각할 필요도 없다. 그냥 우리가 평소에 변수의 주소를 넘겨 call by reference를 사용하는 것과 똑같다.

노드의 생성

연결리스트에 새로 삽입되는 요소들은 프로그램이 돌아가는 동안에 이루어진다. 개발자는 유저가 얼마나 많은 데이터를 리스트에 삽입할 지 모른다. 즉, 코드를 짜면서 노드를 만들어두는 것이 아니라 동적 할당을 통해 런타임 시간에 노드를 만들어야한다. 이때문에 malloc(), free() 함수를 잘 활용해야한다.

  
#include <stdlib.h> // malloc, free() 함수 사용

LinkedNode* n1;
n1 = (LinkedNode*) malloc(sizeof(LinkedNode)); // 노드를 동적할당

n1->data = 10;   // 노드 n1의 데이터는 10
n1->next = NULL; // 노드 n1의 다음 노드는 아직 없습니다.

LinkedNode* head = n1; // 리스트의 맨 앞 노드, 헤드 노드는 n1입니다.

위처럼 malloc() 함수를 통해 노드 구조체 크기만큼을 할당받아야 한다. 그러고나서 노드에 원하는 데이터를 담을 수 있다.

  
// 값 e를 가지는 노드를 만들어주는 Wrapper 함수
Node* List_NewNode(Node* n, element e)
{
    // 넘겨받은 포인터 변수는 복사본, 현재 복사본 자체를 수정 중
    // 즉 원본에는 동적 할당받은 곳의 주소가 없다. 복사본 변수 n에는 들어있다.
    n = (LinkedNode*) malloc(sizeof(LinkedNode));
    if (n == NULL) { /* NULL 포인터 예외처리 */ }

    // 복사본이 가르키는 곳은 원본과 똑같음. 이는 정상적으로 수정된다.
    n->data = e;

    // 복사본을 다시 리턴해줘서, 원본의 내용물을 바꿔주어야 한다.
    // 즉 이 함수 안에서 할당받은 주소를 원본에 넣어주어야 한다.
    return n;
}

/* Do sth...*/

LinkedNode* n1; // 노드 n1의 주소를 담을 포인터 변수

// n1을 복사해서 넘겨주고, 공간을 할당받아 그 노드에 10을 넣는다.
// 그러고 수정된 복사본을 다시 리턴받아, 원본의 내용물과 대치시키면 
// 변수 n1에는 이제 노드 크기만큼 할당받은 곳의 주소가 들어있다.
n1 = List_NewNode(n1, 10); 

아니면 위처럼 노드 생성 함수를 만들어서, 노드를 생성해주는 작업을 함수로 처리한다. 다만, 포인터 변수 자체를 수정하기때문에,

포인터 변수의 (헤드 노드의 주소를 담고있는 변수의 주소??!) 주소를 넘겨 call-by-reference를 흉내내던가
아님 수정한 포인터 변수를 다시 리턴해주는 방법을 쓴다.

1번 방법대로 포인터의 주소를 넘기면 이는 곧 이중포인터가 되버려 코드가 좀 더러워진다.

  
void List_NewNode(Node** node, element item) {
    // ...
    (*node)->data = item; 
}

이중포인터를 쓰면 이런 괴상한 문법이 된다.

리스트에 삽입

삽입 과정

노드를 원하는 자리에 삽입하려면, 원하는 자리 이전의 노드를 알아야한다.

원하는 자리의 노드 이전 노드까지, 헤드 노드로부터 각 노드가 가르키는 다음 노드를 따라간다. 이때 개수를 세며 원하는 자리의 이전 노드까지 탐색해 나간다.
이전 노드에 도착했다.
현재 머물고 있는 ‘이전 노드’의 다음 노드의 주소를 알아내서, 삽입할 노드의 다음 노드로 지정한다.
현재 머물고 있는 ‘이전 노드’에서, 내 다음 노드를 삽입할 노드로 지정하면 끝이다.

이렇게 생각해보면, 리스트가 현재 지니고 있는 요소의 개수를 추적할 필요가 있을 것 같다. 왜냐하면 리스트에 몇개가 있는지도 모르는데 어떤 위치에 넣을 수 있을까? 교재에서는 삽입할 인덱스가 아니라, 삽입할 위치 이전의 노드를 인자로 넘긴다. 인덱스 값을 줘서 삽입을 하고 싶다면 반복문을 돌려 원하는 자리까지 노드를 따라 탐색하면 된다. 스스로 구현해보자.

  
LinkedNode* List_InsertFirst(LinkedNode* head, element item)
{
    // item 데이터를 가지는 새 노드 생성
    LinkedNode* newNode = NULL;
    newNode = List_NewNode(newNode, item);

    // 빈 리스트라면 헤드를 새노드로 지정하고 바로 리턴
    if (head == NULL)
    {
        head = newNode;
        return head;
    }

    // 새 노드의 다음 노드 = (현재 첫번째 노드가 가르키는) 두번째 노드
    newNode->next = head->next;

    // 리스트의 맨 앞은 이제 새 노드
    head = newNode;

    return head; // 수정한 복사본 head를 다시 리턴
}

리스트의 맨 앞에 삽입하는 함수의 코드는 이렇다.

리스트에서 제거

노드의 제거 동작

리스트에서 노드를 제거하는 동작도 연결만 잘하면 된다.

제거할 노드의 이전 노드를 알아낸다.
이전노드의 다음 노드를, 제거할 노드의 다음 노드로 연결한다. 즉 제거할 노드를 건너뛰게끔 연결한다.
(선택사항) 제거할 노드의 다음 노드를 NULL 주소로 연결한다.
제거할 노드의 데이터를 임시저장하고 (만약 pop()연산 종류라면 노드의 데이터를 반환하기 위해 임시저장한다.), 노드를 메모리에 반환한다. free() 함수를 쓴다.
(선택사항) 노드의 데이터를 리턴한다.

  
LinkedNode* List_RemoveFirst(LinkedNode* head)
{
    if (head == NULL) { /* 빈 리스트를 지울 수 없으므로 예외처리*/ }

    // 첫번째 노드인 head를 지우겠다
    LinkedNode* removed = head; 

    // 리스트의 첫번째 노드를, 현재의 두번째 노드로 변경
    // 즉 head 포인터 변수를 수정한다.
    head = removed->next;

    // 노드를 메모리에 반환
    free(removed);

    // 수정된 head를 리턴
    return head;
}

제거도 마찬가지로 맨 앞의 노드를 제거하는 코드를 예시로 들겠다. 원하는 자리의 노드를 지우고 싶다면 리스트의 맨 앞부터 차례대로 탐색해나가며 원하는 자리에서 똑같은 동작으로 노드를 제거하면 된다.

리스트 출력

리스트의 출력 또한 노드에서 노드를 따라가는 탐색을 사용한다. 이 출력 함수를 바탕으로 원하는 위치에 삽입, 제거 연산을 구현해 볼 수 있겠다.

  
void List_Print(LinkedNode* head)
{
    for (LinkedNode* i = head; // 시작 i = head 노드
         i != NULL;            // i가 NULL이 아닌 동안, 즉 리스트의 끝이 아닌 동안
         i = i->next)          // 노드 i의 다음 노드로 넘어가면서 반복.
        printf("%2d ->", i->data); // 노드 i의 데이터 출력

    printf("NULL\n"); // 리스트의 맨 끝은 NULL 출력
}

리스트의 탐색은 반복문을 사용하면 된다. 배열을 반복문 돌리듯이, 리스트의 맨 앞부터 리스트의 끝이 아닌동안 노드를 따라 하나씩 다음 노드로 이동하며 반복문을 돈다.

💻 코드 전체

pastebin 보러가기

실행결과

코드 예제에서는 헤더 구조체를 사용하는 방법을 채택했다.

⭐정리

리스트 자료구조에 대해 알아보았다.
리스트를 구현하는 방법인 연결리스트에는 크게 3가지 종류가 있다.
단순 연결리스트를 구현하는 방법에 대해 알아보았다.

참고서적 : C언어로 쉽게 풀어쓴 자료구조 (개정 3판), 천인국·공용해·하상호, 생능출판 - Yes24바로가기

Data structure with C

c data structure