[C++] 리스트

 

 

 

 

 

 

리스트

순서를 갖고 있는 자료구조

 

 

선형 리스트

리스트 크기 만큼의 메모리 공간을 선형적으로 할당받아 사용하는 배열

 

 

읽기

선형 리스트는 임의 접근이 가능하기 때문에 O(1)의 시간이 걸린다.

 

검색

하나하나 원소를 비교해가야 하므로 O(n)의 시간이 걸린다.

정렬되어 있다면 이진 검색을 사용할 수 있으며 이 경우 O(log n)이다.

 

삽입

원소를 어디에 삽입하냐에 따라 시간이 달라진다.

맨 끝에 데이터를 추가할 경우 O(1)이지만, 처음이나 중간이라면 모든 데이터를 이동해야 하기에 O(n)이 걸린다.

 

삭제

삽입과 마찬가지로 원소를 어디에서 삭제하냐에 따라 시간이 달라진다.

맨 끝의 데이터를 삭제할 경우 O(1)이지만, 처음이나 중간이라면 모든 데이터를 이동해야 하기에 O(n)이 걸린다.

 

 

이진 검색

검색할 범위를 절반으로 줄여가며 검색하는 방법으로 정렬된 선형 리스트에서만 사용할 수 있다.

 

 

연결 리스트

리스트의 요소를 메모리에 임의로 할당한다.

요소는 연결된 다른 요소의 주소를 데이터로 갖고 있으며, 주소 데이터를 통해 연결된 다른 요소를 찾을 수 있는 구조

 

 

 

읽기

연결 리스트는 임의 접근이 불가능해 요소 하나하나를 탐색해야 하므로 O(n)의 시간이 걸린다.

하지만 처음과 끝이라면 구현에 따라 O(1)이 될 수 있다.

 

검색

하나하나 원소를 비교해가야 하므로 O(n)의 시간이 걸린다. 선형 리스트와 다르게 이진 검색을 사용할 수 없다.

 

삽입

원소를 어디에 삽입하냐에 따라 시간이 달라진다.

앞이나 뒤에 데이터를 추가할 경우 O(1)이지만, 중간이라면 해당 위치까지 검색해야 하기 때문에 O(n)이 걸린다.

 

삭제

삽입과 마찬가지로 원소를 어디에서 삭제하냐에 따라 시간이 달라진다.

앞이나 뒤의 데이터를 삭제할 경우 O(1)이지만, 중간이라면 O(n)이 걸린다.

 

 

단일 연결 리스트 ( foward_list )

 

다음 원소의 주소값을 포함하고 있어, 다음 원소를 탐색할 수 있다.
이전 원소의 탐색은 불가능하다.

 

 

 

이중 연결 리스트 ( list )

 

이전 원소의 주소값과 다음 원소의 주소값이 포함되어 있어,
이전 원소와 다음 원소의 탐색이 가능하다.