연결리스트

자료구조

원소 저장 시 다음 원소가 있는 위치를 포함하여 저장하는 자료구조

 

특성

1. K번째 원소를 확인/변경하기 위해 O(n)이 필요함 (다음 원소가 무엇인지 하나 하나 확인 필요)

2. 임의의 위치에 원소를 추가/제거 O(1) : 연결리스트의 장점

 

종류

단일 연결 리스트

각 원소가 다음 원소의 주소를 가지고 있는 리스트

 

이중 연결 리스트

각 원소가 이전 원소와 다음 원소의 주소를 가지고 있는 리스트 (단일 연결 리스트보다 메모리를 많이 씀)

 

원형 연결 리스트

끝과 처음이 연결되어 있음 

각 원소가 이전 원소 다음 원소의 주소를 둘다 가지거나 하나만 가져도 상관없음

 

연산별 시간 복잡도

임의의 위치에 있는 원소를 확인/변경 : O(n)

첫번째 원소의 주소만 알고 있기 때문에 n번째 원소를 보기 위해선 순차적으로 다음 원소를 따라 가야함

 

임의의 위치에 원소를 추가 : O(1)

배열과 다르게 뒤에 있는 원소를 하나씩 밀 필요 없이, 주소값만 변경해주면 된다

단, 추가하고 싶은 위치의 주소를 알고 있어야 함

 

임의 위치의 원소를 제거 : O(1)

앞 원소의 다음 원소 주소를 변경해주면 된다

 

원소를 찾는 연산보다는 원소를 추가/제거하는 연산이 많을 경우 연결리스트가 용이하다 

예 : 메모장

 

배열과 연결리스트 비교 (선형 자료구조)

출처: 바킹독의 실전 알고리즘 0x04강 연결리스트