연결 리스트: Difference between revisions
From CS Wiki
No edit summary |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
[[분류:자료 구조]] | [[분류:자료 구조]] | ||
;Linked List | ;Linked List | ||
;자료를 임의의 기억공간에 저장시키고, 포인터를 이용하여 상호 연결시킨 자료 구조 | ;자료를 임의의 기억공간에 저장시키고, 포인터를 이용하여 상호 연결시킨 선형 자료 구조 | ||
* 실무적으로 아주 많이 쓰이는 자료구조 | * 실무적으로 아주 많이 쓰이는 자료구조 | ||
* 블록 체인도 이 연결 리스트로 이루어져 있다. | * 블록 체인도 이 연결 리스트로 이루어져 있다. | ||
| Line 19: | Line 19: | ||
* 포인터를 위한 추가 공간 필요 | * 포인터를 위한 추가 공간 필요 | ||
|} | |} | ||
== 구조 == | |||
각각의 노드는 2가지 값을 가진다. | |||
* 데이터 | |||
* 링크 | |||
<syntaxhighlight lang="c" line='line'> | |||
struct Node { | |||
int data; | |||
Node * next; | |||
}; | |||
</syntaxhighlight > | |||
== 동작 == | == 동작 == | ||
| Line 30: | Line 41: | ||
* 임시 노드를 생성한다. | * 임시 노드를 생성한다. | ||
* 삽입할 위치 앞 노드와 뒷 노드를 취한다. | * 삽입할 위치 앞 노드와 뒷 노드를 취한다. | ||
** 앞 노드의 링크를 먼저 바꿔버리면 뒷 노드를 잃어버리므로 | ** 앞 노드의 링크를 먼저 바꿔버리면 뒷 노드를 잃어버리므로 주의 | ||
* 앞 노드의 링크를 임시 노드로 하고, 임시 노드의 링크를 뒷 노드로 한다. | * 앞 노드의 링크를 임시 노드로 하고, 임시 노드의 링크를 뒷 노드로 한다. | ||
Latest revision as of 22:18, 27 December 2019
- Linked List
- 자료를 임의의 기억공간에 저장시키고, 포인터를 이용하여 상호 연결시킨 선형 자료 구조
- 실무적으로 아주 많이 쓰이는 자료구조
- 블록 체인도 이 연결 리스트로 이루어져 있다.
- 실무적으론 '연결 리스트'라는 말보단 '링크드 리스트'라는 말을 더 많이 쓴다.
장단점[edit | edit source]
| 장점 |
|
|---|---|
| 단점 |
|
구조[edit | edit source]
각각의 노드는 2가지 값을 가진다.
- 데이터
- 링크
struct Node {
int data;
Node * next;
};
동작[edit | edit source]
읽기[edit | edit source]
- 헤드부터 순차적으로 읽는다.
- Access Time이 느린 이유
삽입[edit | edit source]
- 임시 노드를 생성한다.
- 삽입할 위치 앞 노드와 뒷 노드를 취한다.
- 앞 노드의 링크를 먼저 바꿔버리면 뒷 노드를 잃어버리므로 주의
- 앞 노드의 링크를 임시 노드로 하고, 임시 노드의 링크를 뒷 노드로 한다.
삭제[edit | edit source]
- 삭제 순서가 잘못되면 자료를 잃어버리는 상황이 발생되므로 주의
- 삭제될 노드가 첫 노드일 경우
- 첫 노드를 가리키는 포인터를 변경 해 준 후 삭제해야 한다.
- 그 외의 경우
- 대상 노드의 포인터를 취한다.
- 대상 노드 앞 노드의 링크를 뒷 노드로 연결시킨다.
- 대상 노드의 메모리를 해제한다.
이중 연결 리스트[edit | edit source]
- Double Linked List; Multi Linked List
항상 다음 노드만을 바라보고 있는 연결 리스트와 달리, 이전 노드와 다음 노드의 링크를 모두 가지고 있는 연결 리스트
- 실무적으론 '이중 연결 리스트'라는 말보단 '링크드 리스트'라는 말을 더 많이 쓴다.
- 이중 연결 리스트와 구분하기 위해 그냥 연결 리스트는 '단일 연결 리스트(Single Linked List)'라고도 부른다.
장단점[edit | edit source]
- 단일 연결 리스트 대비
- 장점: 연속적인 탐색&액세스가 이루어져야 하는 경우 탐색 시간 절감
- 단점: 포인터를 위한 공간이 2배로 사용됨
