배열과 연결 리스트
1. 배열
특징
메모리에 데이터가 연속적으로 저장되는 자료구조
고정된 크기의 메모리를 미리 할당받는다.
순서가 존재하며 데이터를 참조할 때 인덱스를 사용한다. (0번부터 시작)
시간복잡도
원소 접근: O(1)
원소 삽입, 삭제: O(N)
배열의 시작 주소와 offset만 알면 offset 덧셈을 통해 원하는 인덱스에 한 번에 접근할 수 있다 -> O(1)
삽입을 할 경우, 삽입에 필요한 공간을 마련하기 위해 원소들을 한 칸씩 뒤로 밀 수 있다 -> 최악의 경우 O(N)
삭제를 할 경우, 데이터의 연속성을 보장하기 위해 원소들을 한 칸씩 앞으로 밀 수 있다 -> 최악의 경우 O(N)
2. 연결 리스트
특징
데이터가 비연속적으로 저장되며 순서를 가지는 자료구조
각 노드는 데이터 값과 다음 노드의 주소를 가지며 연결된다.
첫번째 노드는 Head를 통해, 마지막 노드는 Tail을 통해 참조할 수 있다.
시간복잡도
원소 접근, 삽입, 삭제: O(N)
데이터의 순서를 알아도 Head에서부터 하나씩 주소를 참조하며 데이터에 접근해야 한다 -> 최악의 경우 O(N)
삽입의 경우, 이전 원소에 접근한 후 새로운 노드를 만들고 주소를 참조하면 된다 -> 최악의 경우 O(N)
삭제의 경우, 이전 원소에 접근한 후 주소 참조를 바꿔주면 된다 -> 최악의 경우 O(N)
3. 배열 VS 연결 리스트
크기가 가변적이면 연결 리스트를 사용하는 것이 편하다.
원소 접근이 잦을 경우, 배열을 사용하는 것이 효율적이다.
원소 삽입 및 삭제가 잦을 경우, 연결 리스트를 사용하는 것이 효율적이다. (정렬을 하지 않기 때문에 일반적으로 더 빠름)