Vertex 인스턴스 생성하는 방법과 List를 이용하는 방법의 차이

Question

안녕하세요! new Vertex();를 해서 하나씩 정점을 만들어야 한다는 단점 때문에 List를 사용한다는 부분에서 궁금한 점이 생겨서 질문 드립니다. List를 이용할 때도 new List<int> { }를 계속 해주는데 리스트의 배열은 뭐가 다르길래 인스턴스 생성 부담을 줄이게 되는 건가요? 말그대로 배열이라서 메모리를 아낄 수 있는 건가요? 얘도 계속 new를 해주는데 왜 인스턴스 생성해주는 것보다 부담이 덜한건지 궁금합니다.

Rookiss · Answer

정점이 10000개인데 자기들끼리 하나도 연결이 안 된 경우를 예를 들어봅시다. 배열 버전에선 10000칸 짜리 배열을 만들어서 모두 다 연결 안됐다고 일일히 표시(0이라거나, false라거나..)해야 하지만, List 버전은 애당초 연결된 노드 번호를 바로 기입하는 개념이니 빈 강통 List만 만들어도 동일한 의미가 전달됩니다. 배열 버전(행렬 버전)으로 그래프를 표기할 경우, 데이터가 많아지면 메모리적으로 부담이 되지만, 반대로 서칭이 빨리지게 됩니다. (4번 노드와 10번 노드가 연결 되었나? -> adj[4, 10]과 같이 바로 체크 가능. 리스트 버전으로 그래프를 표기하면 꼭! 필요한 연결 데이터만 기입할 수 있지만 반대로 연결 여부를 서칭하는게 느려질 수도 있습니다.