자료구조(data struture)란?
•
컴퓨터에서 여러 자료들을 조직적, 체계적으로 저장하는 방법을 말한다
•
보통 동일한 자료형을 여럿 저장하는 구조를 의미한다
•
자료구조에 따라 요소들 사이의 관계를 정의하는 규칙이 있다.
•
상황마다 효율적인 자료구조가 존재한다
◦
데이터에 접근하는 빈도가 높은 경우
◦
데이터에 접근하는 방법(예 : 삽입, 검색, 읽기, 지우기 등)
자료구조의 효율성
•
효율성은 주로 시간 복잡도(time complexity)를 말함
•
공간 복잡도(space complexity)를 포함하는 경우도 있음
•
따라서 주로 빅오(Big-O) 표기법을 사용
•
보통 효율성을 논할 때는 하드웨어 최적화를 고려 안 한 이론이 전부
◦
대용량의 데이터를 사용할 때는 그래도 맞는 경우가 많다
◦
적은 용량의 데이터는 그렇지 않을 수도 있다
C에서 자료구조를 배우는 이유
•
배열을 제외한 자료구조는 하드웨어 위에서 프로그래머가 만든 개념
•
다른 언어에서는 이런 자료구조들을 라이브러리로 제공하기에 프로그래머가 제대로 구현하며 배울 기회가 적다
•
자칫하면 추상적으로만 이해해서 ‘이건 마법처럼 도는구나’라고 믿고 넘어갈 수 있는 부분을 제대로 이해할 좋은 기회
자료구조의 시간 복잡도
검색 | 삽입 | 삭제 | 검색 | 삽입 | 삭제 | |
배열 | O(n) | O(n) | O(n) | O(n) | O(n) | O(n) |
스택 | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
큐 | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
연결리스트 | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
해시 테이블 | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |
•
참고 : 공간 복잡도는 다 O(n)
배열과 연결리스트
1. 배열(array)
•
메모리의 한 덩어리로 표현 가능한 가장 간단한 자료구조
•
여러 자료들을 그 메모리 한 덩어리 안에 줄줄이 세워놓은 구조
•
논리적 (저장) 순서와 물리적 (저장) 순서가 동일
•
각 자료는 색인(index)로 접근
◦
연속된 메모리주소를 가지고 있으니 각 요소의 실제 메모리 상의 위치를 쉽게 찾을 수 있다
•
배열의 삽입
◦
시간 복잡도: O(n)
▪
O(n)인 이유는 배열은 인덱스위치에 삽입만 한다면 O(1)이다. 하지만 index 위치에 삽입하기 위해서는 뒤에 있는 요소들을 밀어서 빈공간을 만들어야 하기 때문에 O(n)이라고 한다.
•
배열의 제거
◦
시간 복잡도: O(n)
▪
배열의 제거도 비슷하다 배열 인덱스 위치에 있는 값을 제거만 한다면 O(1)의 시간복잡도를 가진다. 하지만 제거하고 난후 그 빈 공간을 채우기 위해 뒤에 있는 요소들을 당겨와야 하기 때문에 O(n)이라고 할 수 있다.
•
배열의 검색
◦
시간 복잡도: O(n)
▪
만약 원하는 인덱스 위치에 값만 출력하고자 한다면 O(1)이라고 할 수 있다. 하지만 우리가 원하는 값과 일치하는 곳이 있는지를 찾는 거라면, 반복문을 실행해야하기 때문에 O(n)이라고 할 수 있다.
2. 연결 리스트(linked list)
•
배열과 연결리스트의 차이
◦
배열은 가변길이가 정해줘야 하는 반면, 연결리스트는 가변길이를 정해줄 필요 없이 필요하면 그 만큼 동적할당을 해서 사용할 수 있는 장점이 있다.
•
자료들이 메모리에 여기저기 산재해 있다
◦
연결 리스트의 각 자료를 노드(node)라고 부름
•
메모리상에 여기저기 공간에 자리잡고 있다. 배열이나 이런 자료구조들 처럼 연속된 주소를 가지고 있진 않다.
•
자료형이 어떻게 산재해 있을 수 있을까?
◦
동적 메모리 할당으로 필요에 따라 각 노드를 할당하기 때문이다
•
연결 리스트의 삽입
◦
이미 삽입할 위치를 알면 시간복잡도 : O(1)
•
연결 리스트의 제거
◦
이미 삭제할 위치를 알면 시간복잡도 : O(1)
•
연결 리스트의 검색
◦
O(n)
▪
처음 노드부터 찾아야 해서 O(n)만큼의 시간이 필요하다
◦
색인으로는 접근 불가능
◦
이렇게 찾은 뒤에 삽입을 하면 O(1)이 된다.
언제 사용하면 좋을까?
1. 배열
•
가변길이가 정해져 있는 경우에는 배열을 사용하는게 좋다.
◦
그 이유는 배열의 특징을 보면 연속된 메모리 주소를 가지는 자료구조이기 때문에 메모리에서 그 다음 주소를 찾을려고 검색을 할 필요가 없기때문에 더 빠르다고 볼 수 있다.
•
배열이 연결리스트보다 빠른 이유?
1.
우리 CPU는 캐시메모리라는게 있는데, CPU가 메모리에서 데이터를 가져올때, 엄밀히 말하면 D-RAM의 컨트롤러에서 받아오지만, 받아온 데이터를 캐시메모리에 잠시 저장을 하게 되는데, 이때! 저장하는 데이터가 연속된 주소로 읽어온 크기만큼 통으로 저장하게 된다. 이 때문에 O(시간 복잡도)와 상관없이 빠른 경우가 있다.
2.
연결리스트 같은 경우에는 연속된 메모리 주소가 아니기 때문에 메모리 주소의 시작위치를 찾아야 하는 반면, 배열은 연속된 주소를 가지기 때문에 바로 메모리위치를 찾을 수 있기 때문이다.
•
배열을 사용하면 좋은 예
◦
배열같은 경우는 큐의 삽입, 삭제를 O(1)로 만들기 위해서 사용하기 좋다.
▪
원형 버퍼(ring buffer)의 개념을 이용하면 가능하다. (front, back 변수 같은?)
2. 연결리스트
•
가변길이가 정해져 있지 않은 경우
◦
계속해서 데이터를 추가하고 삭제하는 경우에 사용하는게 좋다.
•
아주 큰 데이터를 담아야 하는 경우
◦
가변 길이가 만약 10000 또는 100000일 경우 배열은 연속된 주소를 가져야 하기 때문에 그 크기만큼의 메모리공간이 없을 가능성이 있다. 하지만 연결리스트는 연속된 주소가 아니고 할당 가능한 공간에 자리를 잡고 그 자리를 계속해서 포인터로 연결하기 때문에 메모리의 남은 공간에 대한 제약이 없다고 볼 수 있다.
•
연결리스트를 사용하면 좋은 예
◦
해시테이블에 충돌되는 해시 값이 있을 경우
▪
충돌되는 해시값이 있는 경우에 배열은 다음위치에 저장을 해야하는데, 연결리스트는 그 위치에 있는 리스트가 같은 해시값을 가지고 있는 노드를 연결해서 저장할 수 있다.
