기본 자료구조와 확장형 자료구조
-
자료구조는 데이터를 주기억 장치에 저장하는 것에 중점을 두고 만들어진 방법
-
데이터를 주기억 정치에 저장하는 것이 가장 큰 문제였음
- 데이터를 어덯게 주기억 장치에 저장해야 주기억 장치를 효율적으로 사용하고 저장된 데이터를 빨리 찾을 수 있을 까의 문제였음
- 주기억장치에 어떤 데이터를 저장할지 연구하여 정의된 것이 자료구조
-
지금까지 정의된 자료구조에는 배열, 연결 리스트, 스택, 큐, 트리, 그래프가 있다.
-
정의된 자료구조들은 함께 저장하는 방식에 따라 선형 자료구조와 비선형 자료구조로 나누어진다.
선형 자료구조
- 배열, 연결 리스트, 스택, 큐는 순서가 정해져 있는 자료구조
- 데이터를 정해진 자료형으로 순서대로 저장하는 것을 말하며, 저장된 여러 개의 데이터 중에서 특정 데이터에 순차적으로 접근할 수 있고, 접근 방법을 제시
비선형 자료구조
- 트리, 그래프는 순서가 정해지지 않은 자료구조
- 데이터를 정해진 자료형으로 순서와 상관없이 저장한다
- 기본 자료구조를 하나가 아닌 다양하게 적용하여 표현한다.
- 저장된 여러 개의 데이터 중에 특정 데이터에 접근하려면 저장된 규칙을 잘 이해하고 알아야 접근할 수 있음
-
기본 자료구조는 실제 주기억장치에 저장되는 방법을 말함
-
스택, 큐, 트리, 그래프는 추상적 자료구조로, 기본 자료구조에 추상적으로 특정한 규칙을 포함시킨 자료구조
-
특정한 규칙을 가지고 저장하였으므로, 저장된 데이터를 찾아올 때도 특정한 규칙에 맞추어 찾아올 수 있다.
-
기본 자료구조에 특정한 규칙을 포함시켰다는 것은 다음과 같이 설명할 수 있다.
-
스택, 큐, 트리, 그래프를 실제 구현할 때는 다음과 같이 각각의 자료 규칙에 맞게 기본 자료구조로 저장하는 것을 말함
-
기본 자료구조를 바탕으로 특정한 규칙을 프로그래밍으로 구현 가능
배열로 구현한 스택 / 연결 리스트로 구현한 스택
배열로 구현한 큐 / 연결 리스트로 구현한 큐
배열과 연결 리스트로 구현한 트리
배열과 연결 리스트로 구현한 그래프
- 배열로 구현한 스택은 스택 자료구조가 갖는 특정한 규칙으로 데이터를 저장하는데, 이때 배열 기본 자료구조로 저장하는 것을 말함
- 특정한 규칙이라는 것은 그 규칙에 맞게 저장하도록 프로그래밍하는 것
- 특정한 규칙을 알고리즘이라 표현 -> 자료구조를 학습하면 알고리즘과 자연스럽게 맞물린다
데이터를 저장하는 것에 중점을 둔 규칙은 자료구조, 일반 문제를 해결하는 것에 중점을 둔 규칙은 알고리즘
기본 자료구조
- 배열과 연결리스트 (C 언어에서 제공하는 자료 구조)
배열
- Array(배열)은 번호와 번호에 대응하는 데이터들로 이루어진 자료구조
- 데이터를 순차적으로 저장하며, 개념이 쉽고, 사용하기 편하지만 메모리 사용 효율성이 낮다
- 배열의 가장 큰 장점은 개념이 단순하고 쉬워 사용하기 쉽고, 저장된 데이터에 빨리 접근할 수 있다는 점
- 변수도 데이터형으로 변형되어 주기억장치에 저장되는데, 변수는 변수 이름 데이터가 저장되는 공간 이외에 주소 저장 공간까지 할당
- 이 주소 공간에는 데이터가 저장된 주소가 저장된다
- 하지만 우리가 저장하고자 하는 데이터는 자기 자신이 저장된 위치를 알지 못하며 알필요가 없고 우리는 반드시 변수로 접근해야 함
- 하나의 변수에 여러 개의 데이터를 배열 자료구조 방식으로 저장하면, 데이터 개수만큼 주기억장치 공간이 확보된 상태에서 데이터를 연달아 저장하게 된다.
- 이는 첫 번째 데이터가 저장된 주소의 다음 주소에 두 번째 데이터가 저장된다는 의미, 그 다음 데이터는 이전 데이터가 저장된 주소의 다움 주소에 저장된다는 의미
- 데이터가 저장된 위치인 주소를 살펴보면, 변수 이름 옆에 저장된 주소는 첫 번째 데이터가 저장된 주소이므로 첫 번째 데이터가 저장된 위치의 주소는 변수로 접근했을 때 주소 변동이 없다.
- 하지만 두 번째 데이터는 첫 번째 데이터가 저장된 주소의 다음 주소이므로 1 증가된 주소인 것을 알 수 있다. 세 번째 데이터는 첫 번째 데이터가 저장된 주소의 2 증가된 주소에 저장되는 것을 알 수 있다
- 배열 자료구조는 주기억장치에 데이터가 일정 공간 확보된 상태에서 주소값이 일정하게 변화되는 형태로 연달아 저장되는 구조
- 배열 자료구조를 이용하여 데이터를 저장하면, 저장된 데이터를 찾을 때 인덱스 값으로 바로 위치에 접근할 수 있기 때문에 빨리 찾을 수 있다
- 하지만 데이터 삽입 또는 삭제 시 효율적이지 않음
- 주기억장치 공간을 미리 확보하지 않으면 새로운 데이터를 삽입하기 위하여 공간을 다시 확보해야 하며, 삭제되었을 때도 사용하지 않는 공간이 지속적으로 할당될 수 있어 주 기억장치의 효율성이 떨어질 수 있다.
- 또한 새로운 데이터를 두번째에 삽입하기 위해서는 두 번째 주소 위치를 확보하기 위하여 데이터 2와 데이터 3의 위치를 모두 변환시켜야 한다.
- 또 두 번째 데이터를 삭제하고자 하면, 삽입과 마찬가지로 다음 위치에 저장된 모든 데이터 위치를 변화시켜야 한다.
- 이처럼 배열 자료구조는 저장된 데이터를 찾기 쉽지만, 삽입 또는 삭제 연산의 효율성이 떨어지는 것을 알 수 있다.
파이썬의 리스트형은 파이썬에서만 제공하는 특 자료구조로 실제 주기억장치에 배열로 저장되는지 알 수 없음
하지만 저장된 데이터 접근을 인덱스로 사용하는 방법이 배열과 유사
a = [8, 4, 9]
a[0] = 8
a[1] = 4
a[2] = 9
a[0] + a[1] = 12
a[1] / 2 = 4
a[2] * 3 = 27
a.append(10) # 10삽입
a.[1] = 5 # 1번 인덱스의 데이터를 5로 수정
del a[2] # 세번째 데이터 삭제연결 리스트
- 연결 리스트(Linked List)는 영문 그대로 번역하면 연결된 리스트를 말한다.
- 리스트들이 연결되어 있다는 의미를 용어에서도 알 수 있듯이, 리스트가 한 줄로 연결된 방식의 자료구조
- 리스트는 데이터 저장 공간과 주소 저장 공간으로 구성되는데, 이것을 C프로그래밍 언어에서는 노드라고 한다
- 이 때 주소 저장 공간에는 다음에 저장되는 데이터가 저장되는 주소를 저장한다.
- C 프로그래밍 언어에서 이 주소 저장 공간을 포인터라고 명명하여, 연결 리스트를 공부하다보면 노드와 포인터라는 단어를 많이 사용
- 연결 리스트는 개념이 배열보다 복잡, C 프로그래밍 언어를 사용하여 구현할 때 포인터를 함께 정의해야 하기에 배열보다 구현이 까다롭다
- 연결 리스트는 메모리 사용 효율성이 높아 많은 데이터를 저장할 때 유리
- 삽입, 삭제 연산이 효율적인 장점을 가지고 있지만, 데이터 접근이 느린 단점을 보유
- 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등으로 구현이 가능
- 연결 리스트 자료구조로 저장되는 데이터는 변수처럼 각각 다른 데이터가 저장된 주소를 저장할 공간을 함께 할당 받아 저장
- 주기억장치에서 하나의 변수 이름에 저장될 때도 데이터들이 주기억장치의 여러 주소 공간에 독립적으로 저장, 각각 연결되어 있다는 것을 저장된 주소값으로 정의
typedef struct Node{
int data;
struct Node* next;
} Node;- 데이터의 주소를 저장하는 위치를 포인터로 정의하기 때문에 항상 데이터와 포인터가 함께 정의된다.
- C로 구현한 연결 리스트에서 노드(Node)를 정의한 코드를 살펴보면, 정수형 데이터와 별을 표시하여 next라는 값은 다음 데이터 주소를 저장한 공간으로 정의
- 데이터들을 연결 리스트로 저장했을 때 데이터에 접근하는 방식과 데이터 삽입, 삭제 연산을 볼때, 데이터 100개가 연결 리스트로 저장되어 있고, 90번째 데이터에 접근하여 찾아오고 싶을 때는?
- 첫 번째 데이터부터 차례대로 89번째 까지 찾아 들어가야 한다
- 배열은 인덱스값 자체가 저장된 주소의 위치를 의미하므로 바로 찾을 수 있지만, 연결 리스트는 그렇지 않다
- 연결리스트는 데이터 접근 효율성이 떨어짐
- 지정된 곳에 새로운 데이터를 삽입하고자 하면, 연결 리스트는 지정된 위치의 이전 데이터와 함께 저장된 주소를 새로운 데이터가 저장된 주소로 바꾸고, 새로 저장되는 데이터와 함께 저장되는 주소는 이전 데이터와 저장되어 있던 주소를 저장하면 다음 데이터 주소가 저장되므로 연결 된다
- 모든 리스트의 주소를 변경할 필요가 없어 배열보다 삽입 연산이 효율적
- 삭제도 삭제델 위치의 이전 데이터가 가지고 있는 주소를 삭제되는 데이터가 가지고 있었던 주소로 바꾸어 주기만 하면 된다
- 삭제 연산또한 배열처럼 모든 데이터의 주소를 바꿀 필요가 없어 효율적
- 메모리 사용 효율성을 살펴볼 때, 모든 데이터의 경우 따로 저장되기 때문에 많은 데이터를 저장할 때도 주기억장치의 작은 공간들만 있으면 저장할 수 있어 메모리 효율성이 높다
- 연결리스트의 경우 파이썬의 딕셔너리 자료형을 이용해 구현 가능
a = {'h' : [8, t], 't' : [4, 'u'], 'u' : [9, null]}
a['h'][0] = 8
a['h'][1] = 't' # 다음 데이터의 키
a['t'][0] = 4
a['t'][1] = 'u' # 다음 데이터의 키
a['u'][0] = 4
a['u'][1] = null # 다음 데이터의 키