CS/자료구조

[자료 구조] 연결리스트, 배열, 벡터

💡 연결 리스트 (Linked List) 연결 리스트는 여러 개의 노드들이 순차적으로 연결된 효율적인 형태를 갖는 자료구조 첫번째 노드 = head, 마지막 노드 = tail 각 노드는 데이터와 다음 노드를 가리키는 포인터로 ****이루어져 있음 배열과는 다르게 메모리를 연속적으로 사용하지 않는다. 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이함 Tree 구조의 근간이 되는 자료구조이며, Tree에서 사용되었을 때 그 유용성이 드러난다. ✅ 연결 리스트의 시간 복잡도 탐색 : O(n) 삽입 / 삭제 : 삽입과 삭제 자체는 O(1) 연결 리스트의 처음 삽입/삭제 : O(1) 연결 리스트 중간 삽입/삭제 : O(n) (탐색 시간 소요) ..