[자료구조] 연결 리스트: 시연

이번 강의에서는 이전에 살펴본 연결 리스트에 대한 시연과, 연결 리스트와 배열의 장단점을 비교하는 것을 다룬다.

연결리스트 시연은 강의 영상에서 볼 수 있다.
🔗모두를 위한 컴퓨터 과학 (CS50 2019) > 5) 연결 리스트: 시연 : 부스트코스]

배열과 비교해서 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있다.
하지만, 이런 유동적인 구조는 그 대가가 따른다. 구조가 정적인 배열과 달리 연결 리스트에서는 임의 접근이 불가능하다.

연결 리스트에 값을 추가하거나 검색하는 경우를 생각해보자

이를 위해서는 해당하는 위치까지 연결 리스트의 각 node들을 따라 이동해야 한다.
따라서 연결 리스트의 크기가 n일때 그 실행 시간은 O(n)이 된다.
배열의 경우 임의 접근이 가능하기 때문에 (정렬 되어 있는 경우) 이진 검색을 이용하면 O(n)의 실행 시간이 소요 되는 것에 비해서 다소 불리하다.

이처럼 여러 데이터 구조는 각각 장단점이 존재한다.

프로그래밍을 할 때 목적에 부합하는 가장 효율적인 데이터 구조를 고민해서 사용하는 것이 중요하다.

생각해보기

배열이 정렬되어 있지 않은 경우의 검색 소요 시간을 연결 리스트의 검색 시간과 비교해보자.

정답

배열이 정렬되어 있지 않은 경우, 검색을 위해 배열의 모든 요소를 순차적으로 확인해야 하므로 최악의 경우 실행 시간은 O(n)이 된다. 이는 연결 리스트의 검색 시간과 동일하다.
따라서, 배열이 정렬되지 않은 경우에는 연결 리스트와 비교하여 검색 속도 면에서 변다른 이점이 없다. 그러나 배열의 경우 인덱스를 통한 임의 접근이 가능하다는 점에서 추가적인 장점이 있을 수 있다.