배열리스트
-
[ 선형 자료구조 ] 배열 & 리스트Computer Science/자료 구조 2023. 1. 6. 16:01
1. 배열 1) 개념 배열은 연관된 데이터를 그룹핑해 관리하는 방식의 자료구조이다. 연속적인 메모리 블록에 데이터를 저장하며, 각 항목을 요소(element)라 한다. 배열은 생성될 때 크기가 고정되며, 해당 위치를 결정하는 인덱스를 가진다. 2) 배열의 특징 (1) 장점 각 항목이 고정적인 인덱스를 가지며, 이를 통해서 각 항목의 요소로의 접근이 O(1)의 빠른 시간복잡도를 가진다. 따라서 잦은 접근이 필요한 데이터를 저장하기에 알맞다. 배열의 경우 데이터의 크기가 고정적이고 잦은 접근이 필요한 경우, 혹은 인덱스가 중요한 경우 이점을 가진다. (1) 단점 생성과 함께 사이즈가 고정되기 때문에 요소의 추가/삭제가 자유롭지 못하다. 항목의 데이터를 삭제해도 인덱스 값은 고정되며 메모리상에서 지속적으로 자..
-
[ 자료구조 ] linked list의 삽입/삭제는 정말 array list보다 빠른가?문득 든 의문점 2023. 1. 5. 22:19
의문점 연결 리스트의 경우 삽입/삭제 자체는 O(1)의 시간 복잡도를 가지지만, 대상이 되는 인덱스 까지 찾아가는 과정을 고려한다면 O(n)의 시간 복잡도가 추가된다고 볼 수 있는데 이를 단순히 O(n + 1)이라 가정한다면 O(n)의 시간 복잡도를 가지는 배열 리스트보다 빠르다고 할 수 없지 않는가? 결론 배열 리스트의 경우 특정 인덱스에 요소를 삽입 / 삭제할 경우 해당 인덱스 이후 모든 요소의 위치를 이동시켜야 한다. 따라서 일정하게 O(n)의 시간 복잡도를 갖는다. 하지만 연결 리스트의 경우 head 부분에 가까워질수록 시간복잡도는 O(1)에 가까워진다. 즉, 삽입/삭제의 대상이 될 인덱스의 위치에 따라 O(1) ~ O(n)의 시간 복잡도를 갖는다. 결론적으로 연결리스트는 배열 리스트보다 빠르거나..