날짜 : 2023-11-13 16:15
주제 :
개요
연결리스트
- 배열, 스택, 큐는 메모리에서 '연속된 저장 방법'에 기초 되어 '정형화' 되어 있음.
- 연결리스트는 '연속된 저장방법', '정형화' 되어있는 제약을 깸
- 하지만 어려움 왜? 포인터를 써야하기 때문.
연결리스트는 자료들이 메모리에 산재해 있음.
연결 리스트의 각 자료를 노드라고 부름.
자료형이 어떻게 산재해 있을 수 있나?
- 동적 메모리 할당으로 필요에 따라 각 노드를 할당함.
어떻게 서로 연결하나?
- 노드 사이의 선 후 관계를 별도로 지정한다.
- 어떻게? : 다음에 오는 노드의 메모리 주소를 기억
- 어디에? : 노드에 있는 포인터 변수에
- 제일 마지막 노드는 올 노드가 없으니 널 포인터.
연결리스트는...
- 메모리 관리 능력
- 이중 포인터 사용 능력
삽입과 제거
- 노드를 삽입할 '위치' 즉, 끼워 넣을 전과 후의 노드 주소를 알면 그 사이에 노드를 끼워 넣을 수 있다.
- O(1)
검색
- O(n)
- 제일 첫 노드부터 값을 찾을 때까지 찾는다.
- 보통, 이 노드를 Head라 부름. - 색인으로 접근 불가능.
연결 리스트 전체를 출력하는 코드 예
typedef struct node {
int value;
node_t* next;
} node_t;void print_node(const node_t* head)
{
node_t* p;
p = head;
while (p != NULL) {
/*여기서 출력*/
p = p->next;
}
}헤드 노드
- 연결 리스트의 첫번째 노드를 가리키는 포인터
- 처음 시작할 때 값은 NULL
- 아직 노드가 없으므로..
- 여기다 새로운 노드를동적할당해서 대입할 것임.
메모리를 동적 할당 한다고? 그럼 반드시 해야 할 일.
free()
void destroy(node_t* head){
node_t* p = head;
while (p != NULL) {
node_t* next = p->next;
free(p);
p = next;
}
}/*메인함수*/
node_t* head = NULL;
/*코드*/
destroy(head);
head = NULL;삽입하기 코드 예
void insert_front(node_t** phead, int n)
{
node_t* new_node;
new_node = malloc(sizeof(node_t));
new_node->value = n;
new_node->next = *phead;
*phead = new_node;
}/*메인함수*/
node_t* head = NULL;
insert_front(&head, 3);
insert_front(&head, 5);
insert_front(&head, 2);
insert_front(&head, 0);
destroy(head);
head = NULL;왜 insert_front() 에 이중포인터를 넣는가?
- 그냥 포인터 일 때는 메인 함수의 head와 새로운 노드를 연결 할 수 없음.
- 함수 안에만 있는 사본 포인터에 새로운 노드가 연결됨 (값에 의한 전달)
- 함수가 끝나면? head는 그대로 phead는 주소를 잃어버리고 메모리 누수가 됨.
이중 포인터일 때는 매개 변수 phead를 통해 메인함수 head와 연결 가능.
오름차순으로 삽입하는 코드
void insert_sorted(node_t** phead, int n)
{
node_t** pp;
node_t* new_node;
new_node = malloc(sizeof(node_t));
new_node->value = n;
pp = phead;
while (*pp != NULL) {
if ((*pp)->value >= n){
break;
}
pp = &(*pp)->next;
}
new_node->next = *pp;
*pp = new_node;
}int main(void)
{
node_t* head = NULL;
insert_front(&head, 3);
insert_front(&head, 5);
insert_front(&head, 2);
insert_front(&head, 0);
destroy(head);
head = NULL;
}삭제
void remove(node_t** phead, int n)
{
node_t** pp;
pp = phead;
while (*pp != NULL) {
if ((*pp)->value == n) {
node_t* tmp = *pp;
*pp = (*pp)->next;
free(tmp);
break;
}
pp = &(*pp)->next;
}
}
int main(void)
{
node_t* head = NULL;
remove(&head, 2);
remove(&head, 5);
destroy(head);
head = NULL;
}연결 리스트의 용도
- 스택/큐와 같은 특성(삽입/삭제 방향) 때문에 쓰는 자료구조는 아님
- 오히려 길이를 자유롭게 늘리거나 줄일 수 있기에 배열의 한계를 넘으려고 사용하던 자료구조
- 즉, 최대 길이를 미리 특정할 수 없고 삽입/ 삭제가 빈번할 경우 사용.
- 오늘날 어플리케이션 프로그램에서 사용 빈도는 많이이 줄음
- 기본적으로 동적 할당 배열을 더 흔히 사용
- C#에서 List도 연결 리스트가 아니라 동적 할당 배열임.
- 최신 하드웨어의 특징 상 배열이 보장하는 훌륭한 메모리 지역성(인접한 메모리를 사용) 이 성능에 유리한 경우가 많기 때문. - 하지만 커널 모드 프로그래밍(예:driver)에서는 여전히 많이 사용
- 메모리 지역성을 해치지 않으면서도 충분히 큰 메모리(예:4kb)를 미리 할당
- 필요에 따라 그 메모리를 쪼개 연결 리스트의 노드로 사용 (예: 메모리 풀) - 참고로 배열 다음으로 많이 사용하는 자료형은 '해시 맵'
참고하면 좋은 것들
- 단일 연결 리스트(singly-linked list)
- 우리가 살펴 본 연결 리스트의 형태
- 다음 노드를 가리키는 포인터만 저장 - 그 전의 노드를 가리키는 포인터도 저장하는 이중 연결 리스트도 있음.
- 이중 연결 리스트는 보통 head외에 tail 포인터 변수도 가지고 있음.
