STL상에서 std::forward_list, std::list로 구현되어 있다.
선형리스트와 다르게 임의접근이 불가능하다.
읽기
연결리스트는 임의 접근이 불가능해 요소 하나하나를 탐색해야 되므로 읽는 시간이 오래걸린다.
검색
읽기와 마찬가지로 원소를 하나하나 비교하기에 시간이 걸린다.
선형 리스트와 다르게 이진 검색도 불가능
삽입
원소의 삽입 위치에 따라 시간이 달라진다.
앞이나 뒤에서 가까우면 짫고 중간이면 해당 위치까지 검색해야한다.
삭제
삽입과 마찬가지로 삭제 위치에 따라 시간이 달라진다.
이유역시 삽입과 똑같이 앞이나 뒤에서 가까우면 짫고 둥간이면 해당 위치까지 검색해서 길어진다.
std::forward_list
std::forward_list는 다음 원소로 만 이동할 수 있는 단일 연결 리스트이다.
std::list
std::list는 이전 원소로도 이동이 가능한 이중 연결 리스트이다.
'코딩 > 자료구조' 카테고리의 다른 글
| [자료구조] 큐(queue) (0) | 2022.07.04 |
|---|---|
| [자료구조] 스택(Stack) (0) | 2022.07.04 |
| [자료구조] 시간 복잡도 와 공간 복잡도 (0) | 2022.06.07 |
| [자료구조] STL (0) | 2022.06.07 |
| 자료구조 (0) | 2022.06.07 |