개념 연결 리스트는 각 노드가 선형적으로 연결되어 있는 자료 구조이다. 특징 - 연결 리스트는 맨 처음 삽입한 노드의 주소를 가지고 있다. - 각각의 노드는 데이터와 다음 노드의 주소를 가지고 있다. - 데이터가 추가될 때마다 새로 노드를 할당하기 때문에 노드끼리의 메모리는 불연속적이다. - 요소의 삽입와 삭제는 O(1) 이며, 특정 원소 접근은 O(n) 이다. 장점 1. 동적인 크기의 데이터를 다루기에 좋다. 데이터를 삽입할 때마다 메모리를 추가로 할당하기 때문이다. - 일반 배열은 크기를 늘릴 수 없음 - 동적 배열(vector, ArrayList 등)은 크기가 늘어날 때 재할당과 복사로 오버헤드 발생 O(N) 2. 각 요소 사이에 데이터를 추가하더라도 O(1) 로 굉장히 빠르다. - 일반 배열과 동..