[자료구조] 연결 리스트(Linked List) 1. 정의 포인터를 사용하여 여러 개의 노드를 연결하는 자료 구조 배열의 단점(데이터 추가, 삭제시 shift 비용 발생)을 해결 각각의 노드들은 다음 노드를 가리키는 포인터, 자신의 값을 가지고 있는 데이터를 가리키는 포인터 2개로 구성 마지막 노드의 다음 노드는 없으므로 null을 가리키게 된다. head라는 포인터는 첫번째 노드의 주소를 가지고 있다. 힙에서는 연결 리스트의 head만 알고 있기 때문에 head.next를 이용하여 연결리스트를 탐색한다. 1.1 배열과 비교 배열 논리적 저장 순서와 물리적 저장 순서가 일치 찾고자 하는 원소의 인덱스를 알고 있으면 O(1)으로 원소에 접근 가능 → Random Access 가능 삭제와 삽입시 빈 공간이 ..
