Dan-k
2020. 1. 18. 17:35
반응형
연결리스트
연결 리스트의 필요성
-
배열을 사용하는 경우 메모리 공간이 불필요하게 낭비될 수 있음
-
이때 연결 리스트를 사용하여 메모리 낭비 현상 방지 가능
배열 기반 리스트의 특징
-
배열로 만들었으므로 특정한 위치의 원소에 즉시 접근할 수 있다는 장점이 있음
-
데이터가 들어갈 공간을 미리 메모리에 할당해야 한다는 단점
-
원하는 위치로의 삽입이나 삭제가 비효율적
연결 리스트
-
구조체와 포인터를 함께 사용하여 구현
-
중간지점에 노드를 추가하거나 삭제할 수 있어야 함
-
필요할 때마다 메모리 공간을 할당받음
단일 연결 리스트
-
일반적으로 연결리스트의 시작노드를 Head라고 함
-
끝 노드의 next에는 null이 들어갈 수 있도록
연결 리스트 삽입
연결 리스트 삭제
연결 리스트의 특징
-
삽입과 삭제가 배열에 비해서 간단하다는 장점이 있음
-
배열과 다르게 특정 인덱스로 즉시 접근하지 못함 (원소를 차례대로 검색해야 함)
-
추가적인 포인터 변수가 사용되므로 메모리 공간이 낭비
양방향 연결 리스트
-
양방향 연결 리스트는 Head와 Tail을 모두 가짐
연결 리스트 삽입
연결 리스트 삭제
728x90
반응형
LIST