LINKED LIST
DEV ·1. 배열과 연결리스트의 장단점 비교
1-1. 배열
- 장점 : 랜덤 엑세스가 빠르다.
- 단점 : 메모리 사용이 비효율적이다. 배열 내 데이터 이동 및 재구성이 어렵다.
1-2. 연결리스트
- 장점 : 동적 메모리 사용이 가능하다. 메모리 사용이 효율적이다. 대용량 데이터 처리에 적합하다.
- 단점 : 특정 위치 데이터 검색 시 느리다. 메모리의 추가적인 사용이 필요하다.
2. 노드
연결리스트는 ‘노드’라는 객체로 이루어져 있다.
노드는 저장할 공간과 다음 주소를 가리킬 공간으로 나뉘게 된다.
입력 정보를 위의 DATA 영역에 담고 노드가 추가될 때 NEXT ADDRESS를 이용해 다음 노드와 연결하게 된다.
각 노드는 연속된 공간이 아닌 메모리의 여러 부분에 분포되어 있다.
노드마다 NEXT ADDRESS를 저장해 다음 노드로 갈 수 있다.
마지막 노드는 다음 주소가 NULL로 표시된다.
3. 연결리스트 구현
‘초기화(init)’, ‘삽입(insert)’, ‘삭제(remove)’를 진행할 수 있는 함수가 필요하다.
3-1. 초기화
처음에 노드를 생성하는 과정을 말한다.
노드에 접근하기 위해서 맨 처음 노드 주소를 가리킬 노드가 필요하다.(HEAD)
3-2. 삽입
A. 앞에 삽입하는 경우
HEAD의 뒤에서 처리가 이루어지게 된다.
’새로운 노드의 NEXT → 현재 HEAD의 NEXT’
’HEAD의 NEXT → 새로운 노드의 DATA’
의 형태로 이루어지게 되며 아래의 그림과 같은 방식이 된다.
B. 뒤에 삽입하는 경우
앞의 과정과 반대로, HEAD대신 TAIL을 사용한다.
’새로운 노드의 NEXT → NULL’,
’TAIL의 NEXT의 NEXT’ → ‘새로운 노드의 DATA’,
’TAIL의 NEXT → 새로운 노드의 DATA’
의 형태로 이루어지며, 아래의 그림과 같이 된다.
C. 원하는 위치에 삽입하는 경우
특정 위치에 삽입할 경우(여기서는 FIRST와 SECOND사이), 삽입할 위치를 찾는 노드(LOCATION)가 먼저 필요하다.
이전에는 HEAD, TAIL과 같은 위치가 있는 노드가 있었지만, 지금은 없는 경우이므로 직접적인 설정이 필요하다.
’LOCATION의 NEXT → FIRST의 DATA’,
’새로운 노드의 NEXT → SECOND의 DATA’,
’FIRST의 NEXT → 새로운 노드의 DATA’
의 형태로 이루어진다.
3-3. 삭제
원하는 위치에 삽입하는 경우와 비슷하다.
그러나, 삭제할 노드(DELETE)의 전 ∙ 후를 연결해야 하기에 새로운 노드(PRE)가 필요하다.
’LOCATION의 NEXT → DELETE의 DATA’,
’PRE의 NEXT의 NEXT → DELETE의 NEXT’,
’DELETE를 삭제’
의 순서로 이루어지며 아래 그림의 형태와 같다.
링크
- 연결리스트 안내
https://sycho-lego.tistory.com/17