연결 리스트 (Linked List)
태그 :
- 개념
- 자료들을 임의의 기억공간에 저장시키고, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조 각 노드는 다음 노드를 가리키는 링크(Link, Pointer) 정보를 가지고 마지막 노드는 포인터 정보를 Null 값을 가짐.
I. 연결 리스트 (Linked List)의 개요
가. 연결 리스트의 정의
- 자료들을 임의의 기억공간에 저장시키고, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조
- 각 노드는 다음 노드를 가리키는 링크(Link, Pointer) 정보를 가지고 마지막 노드는 포인터 정보를 Null 값을 가짐.
|
나. 연결리스트의 장∙단점
(1) 장점
- 자료의 삽입 및 삭제가 용이
- 기억장소의 이용 효율이 좋음.
(2) 단점
- Access Time이 느림
- 포인터를 위한 추가 공간이 필요
Ⅱ. 연결 리스트 (Linked List)의 구현 방법
가. 연결 리스트의 삽입 구현
“cat”과 “sat”사이에 “mat”을 삽입한다면~ (1) 기억장소로부터 노드를 얻는다. (주소값: paddr) |
(2) 노드에 “mat” 데이터를 저장한다. |
(3) paddr 노드의 링크값에 “cat”노드의 링크값을 저장한다. |
(4) “cat” 노드의 링크값에 paddr을 저장한다. |
void insert(list_ptr *ptr,list_ptr node) { list_ptr temp; temp=(list_ptr)malloc(sizeof(list_node)); if(!temp ) { fprintf(stderr,”The momory is full\n”); exit(1); } temp->data=”mat”; if(*ptr) { temp->link = node->link; node->link = temp; } else { temp->link = NULL; *ptr = temp; } } |
나. 연결 리스트의 삭제 구현
- ptr: 리스트 첫 노드를 가리키는 포인터 변수 - node: 삭제될 노드를 가리키는 변수 - trail: 삭제될 노드의 바로 앞 노드를 가리키는 변수
* 삭제될 노드가 첫 노드일 경우와 그렇지 않은 경우로 나눔 |
(1) 삭제될 노드가 리스트의 첫 노드일 때 – 리스트 시작인 ptr 값이 바뀐다. |
|
(2) 그 외의 경우 리스트의 시작인 ptr 값이 안 바뀐다. |
|
void delete(list_ptr *ptr, list_ptr trail, list_ptr node){ if(trail) /* 노드가 여러 개 있는 경우 */ trail->link = node->link; else /* 노드가 한 개 밖에 없는 경우 */ *ptr = (*ptr)->link; free(node); } |
Ⅲ. 연결 리스트 (Linked List)의 종류
구분 |
내용 |
단순 연결 리스트 (Single Linked List) |
|
이중 연결 리스트 (Double Linked List) |
|
환형 연결 리스트 (Circular Linked List) |