연결 리스트 편집하기

[[분류:자료 구조]]
;Linked List
;자료를 임의의 기억공간에 저장시키고, 포인터를 이용하여 상호 연결시킨 선형 자료 구조
* 실무적으로 아주 많이 쓰이는 자료구조
* 블록 체인도 이 연결 리스트로 이루어져 있다.
* 실무적으론 '연결 리스트'라는 말보단 '링크드 리스트'라는 말을 더 많이 쓴다.

== 장단점 ==
{| class="wikitable"
|-
! 장점 
||
* 자료의 삽입 및 삭제가 용이
* 기억장소의 이용 효율이 높음
|-
! 단점 
||
* Access Time이 느림
* 포인터를 위한 추가 공간 필요
|}

== 구조 ==
각각의 노드는 2가지 값을 가진다.
* 데이터
* 링크
<syntaxhighlight lang="c" line='line'>
struct Node {
	int data;
	Node * next;
};
</syntaxhighlight >

== 동작 ==
=== 읽기 ===
[[파일:연결 리스트.png]]
* 헤드부터 순차적으로 읽는다.
* Access Time이 느린 이유

=== 삽입 ===
[[파일:연결 리스트 삽입.png]]
* 임시 노드를 생성한다.
* 삽입할 위치 앞 노드와 뒷 노드를 취한다.
** 앞 노드의 링크를 먼저 바꿔버리면 뒷 노드를 잃어버리므로 주의
* 앞 노드의 링크를 임시 노드로 하고, 임시 노드의 링크를 뒷 노드로 한다.

=== 삭제 ===
[[파일:연결 리스트 삭제.png]]
* '''삭제 순서가 잘못되면 자료를 잃어버리는 상황이 발생되므로 주의'''
* 삭제될 노드가 첫 노드일 경우
** 첫 노드를 가리키는 포인터를 변경 해 준 후 삭제해야 한다.
* 그 외의 경우
** 대상 노드의 포인터를 취한다.
** 대상 노드 앞 노드의 링크를 뒷 노드로 연결시킨다.
** 대상 노드의 메모리를 해제한다.

== [[이중 연결 리스트]] ==
;Double Linked List; Multi Linked List
항상 다음 노드만을 바라보고 있는 연결 리스트와 달리, 이전 노드와 다음 노드의 링크를 모두 가지고 있는 [[연결 리스트]]
* 실무적으론 '이중 연결 리스트'라는 말보단 '링크드 리스트'라는 말을 더 많이 쓴다.
* 이중 연결 리스트와 구분하기 위해 그냥 연결 리스트는 '단일 연결 리스트(Single Linked List)'라고도 부른다.

=== 장단점 ===
; 단일 연결 리스트 대비
* 장점: 연속적인 탐색&액세스가 이루어져야 하는 경우 탐색 시간 절감
* 단점: 포인터를 위한 공간이 2배로 사용됨

[[파일:이중 연결 리스트.jpeg]]