연결 리스트: 시연

들어가기 전에

이번 강의에서는 학생들과 함께 연결 리스트를 직접 시연해보도록 하겠습니다. 또 연결 리스트와 배열을 비교해보고 그 장단점을 생각해 보겠습니다.

 

학습 목표

연결 리스트와 배열의 장단점을 설명할 수 있습니다.

 

핵심 단어

• 연결 리스트
• 배열

배열과 비교해서 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있습니다.

하지만 이런 유동적인 구조는 그 대가가 따릅니다. 구조가 정적인 배열과 달리 연결 리스트에서는 임의 접근이 불가능합니다. 

 

연결 리스트에 값을 추가하거나 검색하는 경우를 생각해 봅시다.

이를 위해서는 해당하는 위치까지 연결 리스트의 각 node들을 따라 이동해야 합니다.

따라서 연결 리스트의 크기가 n 일때 그 실행 시간은 O(n)이 됩니다.

배열의 경우 임의 접근이 가능하기 때문에 (정렬 되어 있는 경우) 이진 검색을 이용하면 O(log n)의 실행 시간이 소요 되는 것에 비해서 다소 불리합니다.  

 

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

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

 

 

생각해보기

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

 

나의 생각 : 배열을 선형 검색을 하면 연결 리스트와 검색 시간이 같다. O(n)

 

출처 : https://www.boostcourse.org/cs112/lecture/119040?isDesc=false 네이버커넥트재단