[자료구조/알고리즘] 추상 자료형, 데이터 구조, 배열(array), 연결 리스트(linked list), 이중 연결 리스트(double linked list)
> 추상 자료형(ADT_Abstract Data Type)
클래스와 유사한 개념으로서 논리적 관계와 구현 시 관계의 연관성을 서로 분리하며, 물리적 요소와 논리적 요소를 서로 구분하는 작업인 절차적 추상화의 결과로 만들어진 것. 특정 데이터 유형에 필요한 연산이 무엇인지 정해 둔 명세로, 데이터 변수를 조작하기 위한 인터페이스와 실제 구현을 분리함으로써 메모리에서 실제 데이터 조작에 필요한 모든 세부사항을 감출 수 있다. 내가 컴퓨터의 내부 작동 원리에 대해 잘 모르지만, 마우스와 키보드로 컴퓨터를 작동할 수 있는 것 역시 '절차적 추상화' 덕분이다.
ex) list, dictionary, set, queue, stack 등
> 데이터 구조(자료구조, Data structure)
데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 모두 포함하는, 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 말한다. 추상 자료형을 구체화 한, 실제 구현에 해당한다고 생각하면 된다. 추상 자료형은 내가 보는 표면적인 구조라면, 데이터 구조는 그것이 실제 내부적으로 저장되고 조작되는 구조라고 볼 수 있다. 즉, 동일한 목적의 알고리즘도 서로 다른 데이터 구조를 이용한 여러 방법으로 구현될 수 있으며, 여기서 생겨나는 비효율을 줄이기 위해 자료구조를 공부해야 한다.
ex) 배열(array), 연결 리스트(linked list), 이중 연결 리스트(double linked list), 트리, 힙 등
1) 배열(array)
데이터형의 요소들이 동일한 크기로 순서를 갖고 나열되어 있는 집합. 연속적인 공간을 할당하여 만들며, 데이터를 순차적으로 기록하고 맨 마지막 항목 뒤에는 Null을 기록한다.
[장점]
① 프로그래밍 하기 쉬움
② 어떤 데이터든 index를 통한 접근 시간이 상수(O(1))
[단점]
① 연속적으로 이어진 공간에만 데이터 저장이 가능 -> 배열에 크기 변화를 주기가 어려움, 데이터가 추가될 것이라 예상한다면, 처음부터 너무 큰 크기의 메모리를 배열에 할당해주어야 함
② 항목의 제거 or 추가의 비효율성(연속성 유지를 위헤 중간을 빈 공간으로 버리거나, 하나씩 당기거나 밀어주어야 하기 때문)
2) 연결 리스트(linked list)
항목을 저장한 칸들을 일방향으로 쇠사슬처럼 연결한 구조. [데이터+포인터] - [데이터+포인터] - ... 의 형태를 띈다. 각 칸의 포인터는 다음 칸의 주소를 가리킨다.
[장점]
① 배열이 연속적 공간을 할당함으로써 발생하는 단점을 보완
② 메모리 활용이 효율적
③ 항목의 추가나 삭제가 용이
[단점]
① n번째 항목에 접근하려면 첫 칸부터 순서대로 접근해야 하기 떄문에, n번의 탐색이 필요함(O(n))
② 특정 n번째 항목에서 이전 항목으로의 역추적이 불가능함(포인터가 일방향으로 가르키기 때문)
3) 이중 연결 리스트(double linked list)
항목을 저장한 칸들을 양방향으로 쇠사슬처럼 연결한 구조. [포인터+데이터+포인터] - [포인터+데이터+포인터] - ... 의 형태를 띈다. 각 칸의 포인터는 다음 칸의 주소 혹은 이전 칸의 주소를 가리킨다.
[장점]
① 연결 리스트(linked list)의 일방향성으로 인한 단점 보완
② 연결 리스트가 가지는 장점은 그대로 가짐
[단점]
① n번째 항목에 상수시간에 접근하지는 못함
② 데이터 칸마다 2개의 포인터를 할당하기 때문에, 추가적인 메모리 소모가 있고 코드가 복잡할 수 있음
> 배열 vs 이중 리스트
언어마다 조금씩 차이는 있겠지만, 추상 자료형에 해당하는 리스트, 큐, 스택, 딕셔너리 등은 모두 특정 자료 구조(배열, 이중 리스트 등)를 이용해 내부적으로 구현이 되어 있다. 대부분 고정적이지만, 경우에 따라 데이터 접근 형태를 파악하여 데이터 구조를 전환하기도 한다. 파이썬을 예로 들면 대부분 내부 구조를 신경쓰지 않고 알고리즘을 짜겠지만, 시간 및 공간 복잡도를 낮추어야 하거나, 최적화가 필요한 경우엔 목적과 데이터에 맞는 자료구조를 직접 택해야 할 수 있다. 이때는 각 자료구조의 특성이나 장단점을 고려해 알맞은 것을 선택해야한다. 아래는 그 예시이다.
1) 배열 > 이중 리스트
- 데이터 중 임의의 값에 빠르게, 자주 접근해야 하는 경우
- 데이터의 추가나 삭제가 없을 것으로 예상되는 경우
2) 배열 < 이중 리스트
- 항목의 추가, 제거가 빈번할 것으로 예상되는 경우
- 데이터 중 임의의 값에 바로 접근하기보다 순서대로만 접근하는 경우
- 리스트 중간에서 추가, 제거가 이루어지는 경우
- 데이터의 추가나 삭제가 있을 것으로 예상되는 경우
| 연산 | 배열 | 연결 리스트 |
| 읽기 | O(1) | O(N) |
| 검색 | O(N) | O(N) |
| 삽입 | O(N) (끝에서 하면 O(1)) | O(N) (앞에서 하면 O(1)) |
| 삭제 | O(N) (끝에서 하면 O(1)) | O(N) (앞에서 하면 O(1)) |