쿠키의 개발 블로그

이 글에서는 연결리스트와 배열리스트의 차이, 그리고 성능 향상 사례를 대해 다룹니다. 연결리스트 vs 배열리스트 배열리스트(Array List) 연결리스트(Linked List) 구현 방법 - 배열을 이용하는 방식 - 여러 노드를 연결하는 방식 (노드: 데이터, 다음 노드 주소를 관리하는 객체) 조회 - 데이터가 연속된 공간에 저장 - 배열 0번째 주소 + (배열원소타입 크기 x 인덱스)를 계산하여 데이터 조회 - 시간복잡도: O(1) - 노드들은 불연속적인 공간에 저장 - 첫번째 노드부터 인덱스에 해당하는 노드에 도착할 때까지 순회 - 시간복잡도: 최악의 경우 O(n) 삽입 - 데이터를 삽입하려는 위치부터 모든 데이터를 한 칸 씩 미루고, 데이터를 삽입 - 배열은 크기가 정적으로 고정되어 있어, 배열이..