강동영의 일상
[자료구조] 연결리스트 1 본문
이번 글에서는 연결리스트에 대해서 배워보도록 하겠습니다.
연결리스트를 설명하기 전에 용어부터 살펴보겠습니다.
리스트란?
A, B, C, ... 처럼 순서를 가진 항목들의 모임입니다.
항목이란?
데이터 필드를 말합니다.
즉, 리스트의 원소들을 저장하는 곳입니다.
리스트는 대표적인 선형 자료구조로 노드들이 일렬로 연결된 구조입니다.
연결리스트에서는 리스트의 항목들을 노드라는 곳에 저장합니다.
노드란?
항목(데이터)과 링크의 쌍으로 표현합니다.
링크란?
다음 노드에 대한 주소입니다.
다음 노드가 있는 곳의 주소를 포인터로 표현합니다.
그렇기에 노드들은 데이터와 다른 노드에 대한 포인터를 가집니다.
이렇게 만들어진 연결리스트는 아래의 조건에 따라서 유형이 나뉠 수 있습니다.
링크의 갯수에 따라서
단일 연결리스트와 이중 연결리스트 등으로 나타낼 수 있습니다.
단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고,
각 노드의 포인터는 다음 노드를 가리킵니다.
이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만,
포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킵니다.
링크가 순환하는 구조인가에 따라
선형 연결리스트와 원형 연결리스트 등으로 나눌 수 있습니다.
선형 연결리스트는 단일 연결리스트, 이중 연결리스트와 같은 선형 구조인 연결리스트를 말합니다.
원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조입니다.
배열을 이용한 구현에는 인덱스를 이용하여 접근합니다.
배열은 크기가 고정되어 있어서 원소의 갯수를 모를 때 메모리 낭비가 발생할 수 있습니다.
때에 따라서 메모리가 모자라는 경우도 생깁니다.
연결리스트를 이용한 구현에서는 위의 사진과 같이 20 -> 30 -> 40 뒤에 노드들을 이어서 동적으로 연결할 수 있습니다.
연결리스트와 배열을 비교해 보겠습니다.
| 연결리스트 | 배열 |
| 가변적인 크기로 메모리 낭비가 적음 | 고정된 크기의 데이터를 저장할 때 적합함 그렇지 않을 경우 메모리 낭비가 많을 수 있음 |
| 삽입과 삭제가 효율적임 | 삽입과 삭제시에 데이터의 이동이 발생함 |
| 임의의 위치에 대한 접근이 안 됨 - 순차적인 탐색만 가능함 |
임의의 위치에 인덱스를 통한 접근이 쉬움 |
| 순차적으로 데이터에 접근할 경우 느림 | 순차적인 접근시 매우 빠름 (순차적인 메모리 공간이 할당되기 때문임) |
연결리스트는 크기가 제한되지 않고,
중간에서 쉽게 삽입하거나 삭제할 수 있는 유연한 리스트를 구현할 수 있습니다.
하지만 구현이 복잡하고,
임의의 항목(i번째 항목)을 추출하려고 할 때는 배열을 사용하는 방법보다 시간이 오래 걸립니다.
즉, 리스트는 배열로 구현할 수 있으나,
삽입과 삭제가 자주 일어날 경우에 연결리스트를 사용하는 것이 효율적이라는 것입니다.
항목과 링크를 가진 노드의 C 표현
typedef int item // typedef로 항목을 추상화
typedef struct ListNode {
item data;
struct ListNode* link; // ListNode 구조체를 가리키는 포인터 변수
} ListNode;위의 코드에서 item은 항목을 저장할 수 있게 해줍니다.
link는 ListNode 구조체를 가리키는 포인터 변수입니다.
우리는 구조체 변수를 포인터를 통해서 접근해야 합니다.
ListNode node = { 10, NULL }; // 이 구조체가 있을 때,
ListNode *list = &node; // 구조체를 가리키는 포인터 변수 list가 node의 주소값을 가지고 있습니다.
즉, node를 참조하고 있다는 것입니다.
data에 접근하는 방법은 두 가지가 있습니다.
1. (*list).data
list라고 하는 포인터 변수가 참조하고 있는 구조체(노드)의 원소에 접근해야 합니다.
그렇기에 도트 연산자(.)을 사용합니다.
2. list->data
포인터 변수 list를 통해 구조체 변수 내부의 멤버에 접근하는 표현입니다.
그렇기에 화살표 연산자(->)를 사용합니다.
아래는 data에 접근하는 두 가지 방법을 보여주기 위한 예시 코드입니다.
#include <stdio.h>
typedef int item;
typedef struct ListNode {
item data;
struct ListNode* link;
} ListNode;
int main() {
ListNode node = { 10, NULL };
ListNode* list = &node;
printf("node.data = %d\n", node.data); // 노드 객체의 데이터
printf("(*list).data = %d\n", (*list).data); // list라는 포인터 변수가 참고하는 객체의 데이터
printf("list->data = %d\n", list->data);
return 0;
}
아래의 코드는 다른 예시입니다.
#include <stdio.h>
#include <stdlib.h>
typedef int item;
typedef struct ListNode {
item data;
struct ListNode* link;
} ListNode;
int main() {
ListNode* p1;
ListNode* p2;
p1 = (ListNode*)malloc(sizeof(ListNode));
p1->data = 10;
p2 = (ListNode*)malloc(sizeof(ListNode));
p2->data = 20;
p2->link = NULL;
p1->link = p2;
printf("p1->data = %d\n", p1->data);
printf("p1->link->data = %d\n", p1->link->data);
printf("p2->data = %d\n", p2->data);
return 0;
}p1은 ListNode 객체를 가리키는 포인터 변수입니다.
malloc을 이용해서 동적으로 ListNode 객체를 만들었습니다.
객체가 생성된 후, 구조체의 데이터에 접근한 후 10을 넣었습니다.
p2도 같은 방법으로 동적 메모리를 만들고 동적 메모리의 데이터 필드에 20을 넣었습니다.
그리고 p2의 link에는 NULL을 넣었습니다.
값이 할당되지 않던 p1의 link에 p2를 넣었습니다.
p1과 p2는 모두 포인터 변수입니다.
그렇기에 p1의 link와 p2는 같은 메모리 영역을 가리키게 됩니다.
이러한 과정을 통해서 두 노드 간에 연결이 형성되었습니다.
그래서 p1->link의 값과 p2의 값은 같습니다.
따라서 아래와 같은 실행 결과가 나옵니다.
'coding' 카테고리의 다른 글
| [자료구조] 연결리스트 2 (0) | 2023.08.05 |
|---|---|
| [자료구조] 이진탐색트리의 탐색, 삽입, 삭제 (0) | 2023.07.25 |
| [자료구조] 이진트리와 이진탐색트리 (0) | 2023.07.18 |
| [자료구조] 트리 (0) | 2023.07.18 |
| [쉽게 풀어쓴 C언어 Express] 9일 차 (0) | 2023.01.03 |
