이 글은 https://blog.encrypted.gg/932?category=773649를 원본으로 하며 공부한 내용을 필기한 것임을 미리 밝힙니다.
(자료구조를 공부하는 데에 어느 정도의 시간이 필요할까 가늠하기 위해 연결리스트를 우선적으로 공부하기로 했다.)
1. 연결리스트란?
원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조로 원소들은 이 곳 저 곳에 흩어져있다.
ex. A B C D라는 사람이 있다 가정 A B C D를 기억하고 싶을 떄, A가 B B가 C C가 D를 기억하게 하면 나는 A만 기억해도 B,C,D를 찾을 수 있다.
2. 연결 리스트의 성질
-
k번째 원소를 확인/변경하기 위해 O(k)가 필요함
//O(k)란 k에 비례하는 시간 복잡도를 의미 -
임의의 위치에 원소를 추가/임의 위치에 원소 제거는 O(1)
(O(1)은 상수시간, 문제를 처리하는 데에 상수의 시간을 필요로 함)
//배열은 원소를 삽입하려면 다른 원소들을 모두 한칸씩 옮기고 빈자리를 만들어야 하지만 연결리스트는 새로 만들어서 삽입하려고 한 칸 전 후 칸과 연결하면 그만이다.
제거 역시 마찬가지, 배열은 없애고 나서 그 뒤의 배열들을 한칸씩 당겨야하지만 연결리스트는 제거하고 제거한 원소 전후의 원소끼리 연결하면 끝.
이게 연결리스트의 가장 큰 장점이다!
- 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움
(Cache hit rate 적중 횟수 / 총 접근 횟수, 아마 메모리 상에 연속해 있지 않으니 적중 확률이 낮으나 연속해 있지 않으므로 오히려 할당이 쉬운게 아닐까)
3. 연결 리스트의 종류
-
단일 연결 리스트 - 각 원소가 자신의 다음 원소 주소를 들고 있는 연결리스트
-
이중 연결 리스트 - 각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 들고 있다.
단일 연결 리스트에서는 주어진 원소의 이전 원소가 무엇인지를 알 수 없는데 이중 연결 리스트에서는 알 수 있다.
다만 원소가 가지고 있어야 하는 정보가 1개 추가되어 메모리를 더 쓴다는 단점이 있다. -
원형 연결 리스트 - 끝이 처음과 연결되어 있다.
단일 연결 리스트, 이중 연결 리스트 모두 가능.
4. 배열 VS 연결 리스트
둘 다 원소들간의 선후 관계가 일대일로 정의되어 선형 자료구조라고 한다.
둘 다 선형 자료구조라서 이 둘의 차이를 잘 알아야 적재적소에 잘 써먹을 수 있다.
- k번째 원소의 접근
배열은 O(1), 연결리스트는 O(k)
2.임의 위치에 원소 추가/제거
배열은 O(N), 연결리스트는 O(1)
(단, 추가하고 싶은 위치까지 찾아간 뒤에야 O(1)의 시간을 사용한 후 추가가능, 당연하지 추가하고 싶은 위치 전의 원소에 이 원소의 주소를 넣고, 다음 원소의 주소를 이 원소에 추가해야하니까)
(1,2의 나머지 이유는 앞에서 서술하였다.)
3.메모리 상의 배치
배열은 연속, 연결리스트는 불연속
(연결리스트는 불연속이므로 할당이 훨씬 쉽고, 이전 원소가 다음 원소의 주소를 들고 있다.)
4.추가적으로 필요한 공간
배열은 X, 연결리스트는 O(N)
배열은 저장할 정보만큼의 공간만 필요하지만 (굳이 따지면 길이 정보를 저장할 int 1개 더)
연결 리스트는 정보의 개수가 N개라고 하면 주소값이 4바이트인 32비트 컴퓨터는 4N 바이트, 64비트 컴퓨터는 8N 바이트 더 필요하다.
5. 기능과 구현
1.임의의 위치에 있는 원소를 확인/변경하는데 O(N)의 시간이 필요.
(순차적으로 방문해야하기 떄문에 k번쨰 원소를 보기 위해서는 O(k)의 시간이 필요하고, 전체에 N개의 원소가 있다고 하면 평균적으로 N/2의 시간이 걸릴테니 O(N)의 시간이 걸린다.
2.임의의 위치에 원소를 추가하는 연산은 추가하고 싶은 위치의 주소를 알면 O(1), 모른다면 원소를 찾아가는 시간이 더 걸림
- 원소를 지우는 연산 역시 O(1)
ex. 13 - 65 - 21- 17 - 42 라는 연결리스트가 있다고 가정했을 떄
65와 17을 연결해버리면 끝이다.
단,21이 들어있는 주소에서 21은 메모리 누수를 막기 위해 메모리에서 없애줄 필요가 있다.
(현재 드는 궁금증 : 할당은 동적할당처럼 하고 해제는 free 로 하는 것일까?)
결론 : 임의의 위치에 원소를 추가하거나 임의의 위치의 원소를 제거하는 연산을 많이 해야할 경우에 연결 리스트의 사용을 고려해보면 좋다.
6.C언어에서 리스트 직접 구현
(참고한 블로그 게시글에서는 C++로 구현하였기에 구현은 혼자 힘으로 해보고 친구가 테스트 케이스를 넣어 시험해주기로 함)
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* link;
};
int main()
{
int i, j, N, n = 0;
int x, y, z;
struct node* start = NULL;
struct node* address;
struct node* temp;
scanf("%d", &N);
for (i = 0; i < N; i++)
{
scanf("%d", &x);
if (x == 1)
{
scanf("%d", &y);
scanf("%d", &z);
}
else if (x == 2)
{
scanf("%d", &y);
}
if (x == 1)
{
n++;
struct node* ptr = (struct node*)malloc(sizeof(struct node));
ptr -> data = z;
if (y == 0)
{
ptr->link = start;
start = ptr;
}
else if (y != n - 1)
{
address = start;
for (j = 0; j < y - 1; j++)
{
address = address->link;
}
temp = address->link;
address->link = ptr;
ptr->link = temp;
}
else
{
address = start;
for (j = 0; j < y - 1; j++)
{
address = address->link;
}
address->link = ptr;
ptr->link = NULL;
}
}
if (x == 2)
{
n--;
if (y == 0)
{
address = start->link;
free(start);
start = address;
}
else if (y == n)
{
address = start;
for (j = 0; j < n - 1; j++)
{
address = address->link;
}
free(address -> link);
address->link = NULL;
}
else
{
address = start;
for (j = 0; j < y - 1; j++)
{
address = address->link;
}
temp = (address->link)->link;
free(address->link);
address->link = temp;
}
}
if (x == 3)
{
if (n == 0)
{
printf("이잉\n");
}
else
{
address = start;
for (j = 0; j < n - 1; j++)
{
printf("%d -> ", address->data);
address = address->link;
}
printf("%d\n", address->data);
}
}
}
return 0;
}여러번 디버깅하면서 느낀 점 :
조건을 나누는걸 최대한 지양하자!!!!
자료구조 맛보기로 이렇게 연결리스트를 타 블로그의 게시글로 공부해보았는데
C언어 자료구조는 마땅한 게시글이 안 보이고
책은 너무 오랜 시간이 걸릴 것 같아서 강의로 공부하기로 결정하였다.
이후 학부 강의를 들으며 더 꼼꼼히 공부해보고 싶다.
