연결 리스트 편집하기
IT위키
편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
1번째 줄: | 1번째 줄: | ||
[[분류:자료 구조]] | [[분류:자료 구조]] | ||
;Linked List | ;Linked List | ||
;자료를 임의의 기억공간에 저장시키고, 포인터를 이용하여 상호 연결시킨 | ;자료를 임의의 기억공간에 저장시키고, 포인터를 이용하여 상호 연결시킨 자료 구조 | ||
* 실무적으로 아주 많이 쓰이는 자료구조 | * 실무적으로 아주 많이 쓰이는 자료구조 | ||
* 블록 체인도 이 연결 리스트로 이루어져 있다. | * 블록 체인도 이 연결 리스트로 이루어져 있다. | ||
19번째 줄: | 19번째 줄: | ||
* 포인터를 위한 추가 공간 필요 | * 포인터를 위한 추가 공간 필요 | ||
|} | |} | ||
== 동작 == | == 동작 == | ||
41번째 줄: | 30번째 줄: | ||
* 임시 노드를 생성한다. | * 임시 노드를 생성한다. | ||
* 삽입할 위치 앞 노드와 뒷 노드를 취한다. | * 삽입할 위치 앞 노드와 뒷 노드를 취한다. | ||
** 앞 노드의 링크를 먼저 바꿔버리면 뒷 노드를 잃어버리므로 | ** 앞 노드의 링크를 먼저 바꿔버리면 뒷 노드를 잃어버리므로 주으 | ||
* 앞 노드의 링크를 임시 노드로 하고, 임시 노드의 링크를 뒷 노드로 한다. | * 앞 노드의 링크를 임시 노드로 하고, 임시 노드의 링크를 뒷 노드로 한다. | ||
54번째 줄: | 43번째 줄: | ||
** 대상 노드의 메모리를 해제한다. | ** 대상 노드의 메모리를 해제한다. | ||
== | == 이중 연결 리스트 == | ||
;Double | ;Double Linked List | ||
항상 다음 노드만을 바라보고 있는 연결 리스트와 달리, 이전 노드와 다음 노드의 링크를 모두 가지고 있는 [[연결 리스트]] | 항상 다음 노드만을 바라보고 있는 연결 리스트와 달리, 이전 노드와 다음 노드의 링크를 모두 가지고 있는 [[연결 리스트]] | ||
* 실무적으론 '이중 연결 리스트'라는 말보단 '링크드 리스트'라는 말을 더 많이 쓴다. | * 실무적으론 '이중 연결 리스트'라는 말보단 '링크드 리스트'라는 말을 더 많이 쓴다. | ||
* 이중 연결 리스트와 구분하기 위해 그냥 연결 리스트는 '단일 연결 리스트(Single Linked List)'라고도 부른다. | * 이중 연결 리스트와 구분하기 위해 그냥 연결 리스트는 '단일 연결 리스트(Single Linked List)'라고도 부른다. | ||
== 장단점 == | |||
; 단일 연결 리스트 대비 | ; 단일 연결 리스트 대비 | ||
* 장점: 연속적인 탐색&액세스가 이루어져야 하는 경우 탐색 시간 절감 | * 장점: 연속적인 탐색&액세스가 이루어져야 하는 경우 탐색 시간 절감 |