배열
-
Array vs LinkedListComputer Science/DataStructure 2019. 12. 16. 15:53
둘다 선형 방식의 자료구조이다. 배열(Array): 인덱스를 가지고 있는 데이터의 모음. 리스트(List): 순서가 있는 데이터의 모음. 각 원소는 다음이 어떤 원소인지만 알고 있음. 배열은 인덱스를 가지고 있기 때문에 인덱스를 알고 있으면 원소에 직접 접근이 가능해 빠르게 조회할 수 있다.(O(1)) 대신 인덱스는 고정되어야 하고 만약 엘리먼트가 삭제되더라도 빈 공간으로 남겨둬야 한다. → 이는 메모리 낭비를 초래할 수 있고, 엘리먼트가 비었는지 확인하는 로직이 필요하다. 리스트는 인덱스가 없기 때문에 각각의 원소는 다음 원소만 알고 있기 때문에 순차적으로 접근해야 한다. (O(n)) 인덱스가 고정이 아니고 순서 정도의 의미만 지니기 때문에 추가, 삭제가 빠르다.(O(1)) → 하지만 추가 삭제를 위한..