데이터 구조, 선형 데이터 구조(array, linked list)
선형 데이터 구조(array, linked list)
선형 데이터 구조란 요소가 일렬로 나열되어 있는 데이터 구조이다.
array
array, 배열은 같은 타입으로 이루어져 있어, 모든 원소는 같은 크기의 메모리로 이루어져 있고 단일 메모리 청크에 데이터들이 모아져 있다.
데이터의 중복이 가능하며 순서가 있다는 것이 특징이다.
장점:
- 순서가 있기에 접근하는 시간이 굉장히 짧다.
- 구조가 단순하다.
- 배열의 원소는 서로 인접해있기에 하나의 원소에 접근 할때 주변 원소도 캐시로 가져온다. (접근 시간이 짧아진다.)
단점:
- 중간의 값을 삭제하거나 삽입할 때 모든 원소들의 위치를 옮겨줘야 한다.
- 정적 배열은 크기를 미리 정해줘야 하기 때문에 불필요한 크기의 배열을 선언하게 될 수도 있다.
- 동적 배열은 할당과 해제를 수동으로 처리 해야 한다. 번거롭다.
삽입, 삭제: O(n) 접근: O(1)
linked list
linked list는 데이터가 들어있는 노드를 포인터로 연결해서 공간적인 효율성을 극대화 시킨 구조이다.
- single linked list: 노드가 next포인터만 가져 뒤로만 접근 가능
- doubly linked list: 노드가 next 포인터와 prev 포인터를 가져 앞뒤로 접근 가능
- circular linked list: doubly linked list와 같지만 마지막 노드의 next포인터가 헤드 노드를 가리켜 계속 순환한다.
장점:
- 포인터를 이용해, 삽입과 삭제를 수행할 때 매우 빠르다.
단점:
- 특정 원소에 접근하려면 헤드 노드부터 차례대로 접근해야 하기에 특정 원소에 접근할 때에 매우 느리다.
- 지역 캐시성을 기대할 수 없기에 모든 원소를 차례대로 접근하는 것은 배열보다 느리다. (이론적으로 시간 복잡도는 같다)
삽입, 삭제: O(1) 접근: O(n)
마무리: array는 특정 원소에 접근 할 때 빠르고, list는 데이터 추가, 삭제할 때에 빠르다는 것이 중요 포인트인 것 같다. c++에는 array, vector, foward_list, list, deque등의 배열과 연결 리스트 기반의 컨테이너를 제공한다.
This post is licensed under CC BY 4.0 by the author.