연결 리스트
연결 리스트란 데이터를 감싼 노드(저장공간)를 포인터로 연결하여 공간적인 효율성을 극대화 시킨 자료구조를 의미한다.
위 그림은 이중 연결 리스트를 간략화 한 것인데, prev 포인터와 next 포인터로 앞, 뒤의 노드들을 연결시킨다. 또한 연결 리스트의 종류에는 싱글 연결리스트, 이중 연결 리스트, 원형 이중 연결 리스트가 있다.
싱글 연결 리스트 : next 포인터만 가짐.
이중 연결 리스트 : next 포인터와 prev 포인터 둘 다 가짐.
원형 이중 연결 리스트 : 이중 연결 리스트와 마찬가지로 next 포인터와 prev 포인터 둘 다 가지며, 마지막 노드의 next 포인터가 처음 노드를 가리킨다.
배열
배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터들을 모아놓은 집합이다.
배열은 순서가 있으며, 중복을 허용한다.
랜덤 접근과 순차적 접근
데이터에 접근하는 방식으로는 랜덤 접근과 순차적 접근이 있다.
○ 랜덤 접근 : 임의의 인덱스에 해당하는 데이터 접근 방식이며 시간 복잡도는 O(1)이다.
○ 순차적 접근 : 데이터를 저장된 순서대로 검색하는 접근 방식이며 시간 복잡도는 O(n)이다.
연결 리스트와 배열의 비교
● 배열은 상자들을 순서대로 나열한 데이터 구조이며, 찾으려는 요소가 몇 번째 상자인지만 알면 해당 상자의 요소를 꺼낼 수 있다.
● 연결 리스트는 상자를 선으로 연결한 데이터 구조이며, 상자 안의 요소를 알아내기 위해서는 상자의 내부를 하나씩 확인해봐야 한다.
- 결론 1 : 따라서 연결 리스트는 랜덤 접근이 불가능하고, 배열은 랜덤 접근이 가능하다.
--> ∵ 배열은 그저 상자 위의 요소를 탐색하면 되는 반면에, 연결 리스트는 연결선을 기반으로 상자들을 하나하나 다 열어봐야 하기 때문에
-결론 2 : 탐색은 배열이 빠르고, 데이터의 추가 및 삭제는 연결 리스트가 더 빠르다.
--> ∵ 배열은 모든 상자들을 앞으로 옮겨야만 데이터의 추가가 가능하지만, 연결 리스트는 연결선을 바꿔주는 것만으로도 데이터의 추가 및 삭제가 가능하기 때문에
[출처] 면접을 위한 CS 전공지식 노트 (주홍철)