Array와 Linked List의 차이

eomprgrm·2023년 4월 18일

1. 배열 (Array)

배열은 컴퓨터 과학에서 가장 기초적인 자료구조이다. 일련의 데이터 요소를 순서대로 저장하는 선형 자료구조로, 동일한 자료형의 요소들이 연속된 메모리 공간에 저장된다. 배열은 인덱스를 사용하여 각 요소에 접근할 수 있고 각 요소는 고유한 인덱스 값을 가지고 있다. 배열의 특징은 다음과 같다.

각 요소는 0부터 시작하는 인덱스를 가지고 있으며, 이를 통해 빠른 랜덤 접근이 가능하다. 인덱스를 이용하여 특정 위치의 요소에 O(1)의 시간 복잡도로 접근할 수 있다.
배열은 생성할 때 미리 크기를 지정해야 하며 이 크기는 고정되어있다. 배열의 크기를 변경하려면 새로운 배열을 생성하고 기존의 데이터를 복사해야 한다.
배열은 연속된 공간에 데이터를 저장하므로, 인접한 요소들은 메모리상에 인접해 있다. 이로 인해 캐시 지역성이 높아 빠른 접근이 가능하다.
배열은 크기가 고정되어 있어 불필요한 공간이 할당될 수 있다. 배열의 크기가 큰 경우 메모리를 낭비할 수 있다.
배열의 중간에 데이터를 삽입하거나 삭제하는 경우 해당 위치 이후의 모든 요소를 이동시켜야 하므로 비효율적일 수 있다.
배열은 여러 차원으로 확장이 가능하며 다차원 배열을 통해 행렬 등의 다양한 데이터를 표현할 수 있다.

2. 연결 리스트 (Linked List)

연결 리스트는 배열과 다르게 연속된 메모리 공간에 저장되어 있지 않다. 각자의 데이터가 메모리 상에 고유한 노드로 존재하며, 자신의 앞, 뒤 데이터 주소를 기억하고 있다. 배열과 마찬가지로 동일한 자료형의 묶음을 저장하기 위해 사용되는 자료구조이다. 배열의 단점이었던 추가/삭제 연산에서의 성능을 보완한다. 데이터 저장 시 메모리에 순서대로 저장하는 것이 아니라 임의의 공간에 넣고 기존 데이터에 부가 정보로 다음 데이터의 주소를 저장한다. 추가/삭제 연산의 시간 복잡도는 O(1)이다. 그러나 검색 연산의 시간복잡도는 배열보다 느린 O(N)이다.