[CS50] 자료구조: 연결 리스트 - 코딩
❄️ David Malan 교수의 모두를 위한 컴퓨터 과학(CS50 2019)을 바탕으로 정리한 내용입니다.
앞서 정의한 구조체를 활용해서 실제로 연결 리스트를 구현해보도록 하겠습니다.
#include <stdio.h>
#include <stdlib.h>
//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
typedef struct node
{
//node 안에서 정수형 값이 저장되는 변수를 name으로 지정합니다.
int number;
//다음 node의 주소를 가리키는 포인터를 *next로 지정합니다.
struct node *next;
}
node;
int main(void)
{
// list라는 이름의 node 포인터를 정의합니다. 연결 리스트의 가장 첫 번째 node를 가리킬 것입니다.
// 이 포인터는 현재 아무 것도 가리키고 있지 않기 때문에 NULL 로 초기화합니다.
node *list = NULL;
// 새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킵니다.
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
// n의 number 필드에 1의 값을 저장합니다. “n->number” n의 number의 값을 1로 저장합니다.
n->number = 1;
n->next = NULL; // n 다음에 정의된 node가 없으므로 NULL로 초기화합니다.
// ✅ 이제 첫번째 node를 정의했기 떄문에 list 포인터를 n 포인터로 바꿔 줍니다.
list = n;
// 이제 list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당합니다.
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
// n의 number와 next의 값을 각각 저장합니다.
n->number = 2;
n->next = NULL;
// ✅ list가 가리키는 노드(=첫 번째 노드)의 next를 n 포인터로 지정합니다.
list->next = n;
// 다시 한 번 n 포인터에 새로운 메모리를 할당하고 number과 next의 값을 저장합니다.
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 3;
n->next = NULL;
// ✅ (list->next)가 가리키는 노드(=두 번째 노드)의 next를 n 포인터로 지정합니다.
list->next->next = n;
// 이제 list에 연결된 node를 처음부터 방문하면서 각 number 값을 출력합니다.
// 마지막 node의 next에는 NULL이 저장되어 있을 것이기 때문에 이 것이 for 루프의 종료 조건이 됩니다.
for (node *tmp = list; tmp != NULL; tmp = tmp->next)
{
printf("%i\n", tmp->number);
}
// 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free 해줍니다.
while (list != NULL)
{
node *tmp = list->next;
free(list);
list = tmp;
}
}
n->number는 (*n).numer”와 동일한 의미입니다.
즉, n이 가리키는 node의 number 필드를 의미하는 것입니다.
간단하게 화살표 표시 ->로 쓸 수 있습니다.
위 코드는 아래 이미지를 의미합니다.
배열과 연결 리스트 비교하기
배열과 비교해서 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있습니다.
하지만 이런 유동적인 구조는 그 대가가 따릅니다.
구조가 정적인 배열과 달리 연결 리스트에서는 임의 접근이 불가능합니다.
연결 리스트에 값을 추가하거나 검색하는 경우를 생각해 봅시다.
이를 위해서는 해당하는 위치까지 연결 리스트의 각 node들을 따라 이동해야 합니다.
따라서 연결 리스트의 크기가 n 일때 그 실행 시간은 O(n)이 됩니다.
배열의 경우 임의 접근이 가능하기 때문에 (정렬 되어 있는 경우) 이진 검색을 이용하면 O(log n)의 실행 시간이 소요 되는 것에 비해서 다소 불리합니다.
이처럼 여러 데이터 구조는 각각 장단점이 존재합니다.
프로그래밍을 할 때 목적에 부합하는 가장 효율적인 데이터 구조를 고민해서 사용하는 것이 중요합니다.
생각해보기
연결 리스트의 중간에 node를 추가하거나 삭제하는 코드는 어떻게 작성할 수 있을까요?
- 추가 하려는 노드가 그 다음 노드를 가르키도록 설정 한 뒤 그 전 노드는 추가한 노드를 가르키도록 변경합니다.
- 주의해야 하는 것은 연결이 끊어지지 않게 해야 합니다. 연결이 끊어지면 끊어진 메모리를 다시는 찾을 수 없기 때문입니다.
- 삭제 하려는 노드의 이전 노드는 삭제 하려는 노드의 다음 주소를 가르키도록 수정 한 후 삭제 하려는 노드를 삭제합니다.
배열이 정렬되어 있지 않은 경우의 검색 소요 시간을 연결 리스트의 검색 시간과 비교해보세요.
- 배열이 정렬되어 있는 경우 검색 소요 시간은 O(log n)입니다.
- 배열이 정렬되어 있지 않은 경우 검색 소요 시간은 O(n)입니다.
- 연결리스트의 경우 정렬이 되어있든 정렬이 되어 있지 않든 동일하게 리스트를 타고 모두 확인을 해야 하기 때문에 O(n)입니다.
💛 개인 공부 기록용 블로그입니다. 👻