[자료구조] 연결 리스트 (Linked List)

리스트란?

List가 무엇일까요? 사전을 찾아보지 말고 이번에는 일상적으로 사용하는 것들을 살펴보겠습니다.

• To-do List 코딩, 독서, 밥 먹기, 친구들과 게임, ...
• 버킷 리스트 해커톤 우승, 게이밍 컴퓨터 조립, 해외여행, ...
• 오늘 저녁에 장 볼 목록 토마토, 배추, 김치, 양파, ...

이런 식으로 리스트를 만들어 그 안에 있는 항목들을 정리할 수 있습니다.

 

데이터도 마찬가지로 이런 식으로 정리할 수 있습니다. 지금까지 스택과 큐를 살펴봤었는데, 큰 범주로 보자면 이것들도 모두 리스트에 속합니다.

 

배열

배열은 리스트를 구현하는 가장 기본적인 방법입니다. 하지만 배열 특성상 한 번 크기를 지정하면 바꿀 수 없습니다. 따라서 데이터를 추가하고 싶어도 크기가 크지 않다면 문제가 발생할 수 있습니다. 그래서 연결 리스트로 리스트를 구현해보도록 하겠습니다.

 

연결 리스트

연결 리스트는 포인터를 사용해 데이터들을 연결하는 리스트입니다.

• 장점: 원소 삽입 시 앞 뒤에 있는 데이터들을 이동할 필요 없이 포인터가 가리키는 곳만 변경하면 됨.
• 단점: 배열에 비해 구현이 어려움. 포인터도 저장해야 해서 메모리 공간을 비교적 많이 차지함. 특정 원소를 찾으려면 앞에서부터 순차적으로 접근해야 함.

 

연결 리스트의 구조

두 가지만 기억하면 됩니다. 링크(link) 멤버와 데이터(data) 멤버.

• 링크 멤버→ 다른 노드를 가리키는 포인터가 저장됨.
• 데이터 멤버 → 저장하고 싶은 데이터가 저장됨.

 

한편, 연결리스트에 접근하려면 첫 번째 노드 주소값을 알아야 합니다. 첫 번째 노드를 가리키고 있는 변수가 필요한데, 이것을 헤드 포인터(head pointer)라고 합니다. 마지막 노드 링크 멤버는 더 이상 가리키는 것이 없으므로 NULL로 설정해주면 됩니다.

 

연결 리스트의 종류

위에서 말한 구조들을 변형하면 여러 종류의 연결 리스트를 만들 수 있습니다.

• 마지막 노드 링크 멤버를 NULL로 하지 않고, 첫 번째 노드 주소 값으로 함 → 원형 연결 리스트 (circular linked list)
• 각각의 노드에 링크 멤버를 하나 더 만들어서 노드의 앞과 뒤를 가리킴 → 이중 연결 리스트 (double linked list)

 

단순 연결 리스트

연결 리스트 중 가장 단순한 형태인 단순 연결 리스트 먼저 소개하겠습니다. 단순 연결 리스트에서는 노드들이 하나의 링크 멤버를 가집니다. 마지막 링크 멤버 값은 NULL입니다. 

 

노드의 정의

노드는 자기 참조 구조체를 이용해 정의됩니다.

자기 참조 구조체란, 자기 구조체와 형(type)을 같이 하는 포인터를 포함하는 구조체입니다. 아래 코드를 보면, ListNode 구조체 구조체 안을 보면 같은 형인 struct ListNode로 포인터 *link를 포함하고 있습니다. 따라서 ListNode는 자기 참조 구조체가 되는 것입니다.

typedef int element;

typedef struct ListNode { // 노드 타입을 구조체로 정의한다.
	element data;
	struct ListNode *link;
} ListNode;

 

헤드 포인터 생성

앞서 연결 리스트에 접근하기 위해 헤드 포인터 있어야 한다고 했습니다. 일단 처음에는 NULL로 초기화한 후, 나중에 노드들을 추가하면서 head를 연결해주면 됩니다.

ListNode *head = NULL;

 

노드 생성

연결 리스트는 배열과 달리 필요할 때마다 malloc으로 원소를 추가할 수 있습니다. 그렇기 때문에 동적으로 노드를 생성합니다. 노드를 초기화할 때 link 멤버는 NULL로 해줍니다.

// 노드 생성
head = (ListNode *)malloc(sizeof(ListNode));

// 노드 초기화
head->data = 10;
head->link = NULL;

 

헤드 포인터에 생성한 노드 연결

헤드 노드에 생성한 노드를 연결해줍니다. 연결 방법은 head의 link 멤버에 생성한 노드의 포인터 주소값을 넣어주면 됩니다.

// 노드 p 생성 및 초기화
ListNode *p;
p = (ListNode *)malloc(sizeof(ListNode));
p->data = 20;
p->link = NULL;

// 헤드 포인터를 p 노드에 연결
head->link = p;

 

단순 연결 리스트 ADT

단순 연결 리스트의 추상 자료형은 아래와 같습니다.

insert_first(*head, item) ::= 헤드 포인터 뒤에 data가 item인 노드 삽입
insert(*head, *pre, item) ::= 연결 리스트 중간에 data가 item인 노드 삽입
delete_first(*head) ::= 헤드 포인터 뒤의 노드를 삭제
delete(*head, *pre) ::= 연결 리스트 중간의 노드를 삭제
print_list(*head) ::= 헤드 포인터에 연결되어 있는 노드를 link 멤버가 NULL이 나올 때 까지 모두 방문해 출력

 

*insert_first(*head, item)

헤드 포인터에 노드를 삽입하는 과정은 아래와 같습니다.

1. 새로운 노드 p를 동적으로 메모리 할당해준다.
2. p의 data 멤버에 item을 대입한다.
3. p의 link멤버에 head를 대입한다.
4. 포인터를 p에서 헤드 포인터로 변경한다.

 

이를 구현하면 아래와 같습니다.

ListNode *insert_first(ListNode *head, int value) {
    ListNode *p = (ListNode *)malloc(sizeof(ListNode)); // 1.
    p -> data = value; // 2.
    p -> link = head; // 3.
    head = p; // 4.
    return head;
}

 

insert(*head, *pre, item)

특정 위치에 노드를 삽입하는 과정은 아래와 같습니다.

1. 새로운 노드 p를 동적으로 메모리 할당해준다.
2. p의 data 멤버에 item을 대입한다.
3. p의 link 멤버에 이전 노드의 link 멤버를 대입한다.
4. 포인터를 p에서 이전 노드의 link 멤버로 변경한다.

 

이를 구현하면 아래와 같습니다.

ListNode *insert(ListNode *head, ListNode *pre, element value) {
    ListNode *p = (ListNode *)malloc(sizeof(ListNode)); // 1.
    p -> data = value; // 2.
    p -> link = pre -> link; // 3.
    pre -> link = p; // 4.
    return head;
}

 

delete_first(*head)

헤드 포인터 뒤에 있는 노드를 삭제하는 과정은 아래와 같습니다.

1. 지울 노드를 가리킬 포인터 removed를 생성합니다.
2. 헤드 포인터가 NULL이면 NULL을 반환합니다.
3. 그렇지 않으면 head 포인터를 removed 포인터 변수에 대입합니다.
4. 헤드 포인터의 값을 removed의 link 멤버로 변경합니다.
5. removed 포인터 변수(이 안에는 헤드 포인터가 들어있습니다.)를 메모리 해제합니다.

 

이를 구현하면 아래와 같습니다.

ListNode *delete_first(ListNode *head) {
    ListNode *removed; // 1.
    if (head == NULL) return NULL; // 2.
    removed = head; // 3.
    head = removed->link; // 4.
    free(removed); // 5.
    return head;
}

 

delete(*head, *pre)

특정 위치에 있는 노드를 삭제하는 과정은 아래와 같습니다.

1. 지울 노드를 가리킬 포인터 removed를 생성합니다.
2. 이전 노드의 link 멤버( == 이전 노드가 가리키고 있는 노드 ) ( == 지울 노드 ) 를 removed 포인터 변수에 대입합니다.
3. 지울 노드의 link 멤버를 이전 노드의 link 멤버로 변경합니다. 이를 통해 이전 노드는 지울 노드의 다음 노드를 가리킬 수 있게 됩니다.
4. removed 포인터 변수 (이 안에는 지울 노드가 들어있습니다.) 를 메모리 해제합니다.

 

이를 구현하면 아래와 같습니다.

ListNode *delete(ListNode *head, ListNode *pre) {
    ListNode *removed; // 1.
    removed = pre->link; // 2.
    pre->link = removed->link; // 3.
    free(removed); // 4.
    return head;
}

 

print_list(*head)

헤드 포인터에는 하나의 연결 리스트가 link 변수에 연결되어 있습니다. 따라서 link가 NULL이 나올 때까지 노드들을 방문해 노드의 data를 출력할 수 있습니다.

이를 구현하면 아래와 같습니다.

void print_list(ListNode *head) {
    for(ListNode *p = head; p != NULL; p = p -> link) {
        printf("%d -> ", p -> data);
    }
    printf("NULL \\n");
}

 

전체 코드는 아래와 같습니다.

ListNode *insert_first(ListNode *head, int value) {
    ListNode *p = (ListNode *)malloc(sizeof(ListNode));
    p -> data = value;
    p -> link = head;
    head = p;
    return head;
}

ListNode *insert(ListNode *head, ListNode *pre, element value) {
    ListNode *p = (ListNode *)malloc(sizeof(ListNode));
    p -> data = value;
    p -> link = pre -> link;
    pre -> link = p;
    return head;
}

ListNode *delete_first(ListNode *head) {
    ListNode *removed;
    if (head == NULL) return NULL;
    removed = head;
    head = removed->link;
    free(removed);
    return head;
}

ListNode *delete(ListNode *head, ListNode *pre) {
    ListNode *removed;
    removed = pre->link;
    pre->link = removed->link;
    free(removed);
    return head;
}

void print_list(ListNode *head) {
    for(ListNode *p = head; p != NULL; p = p -> link) {
        printf("%d -> ", p -> data);
    }
    printf("NULL \\n");
}