.gif)
자료구조
추상적인 데이터 유형은 어떤 데이터 유형에 지원되는 연산이 '무엇인지'만을 알려준다.
고로 그 연산이 '어떠한' 방식으로 수행되는지는 알수 없는데
데이터 구조는 컴퓨터의 메모리 속에서 데이터가 실제로 구조화되는 방식과 그 데이터에 접근 하는 방식을 알려준다.
데이터구조는 추상 데이터 유형을 실제 데이터 처리 모듈로 구현하는데 필요한 방식이다.
배열
배열은 많은 수의 항목을 메모리에 저장할 때 사용할 수 있는 방법중에서
가장 단순하고 기본적인 것이다.
배열은 메모리에 연속적인 공간을 할당하여 만든다.
배열속에 저장하려는 항목은 그 메모리 공간 속에 순차적으로 기록합니다.
배열에 저장된 각 개체는 메모리에서 동일한 용량을 차지한다.
배열은 스택을 구현하는데 특히 유용하지만 리스트나 큐를 구현하는데 사용할수 있다.
**단점**이라면 배열은 연속적으로 이어진 메모리 공간에만 데이터를 저장할수있다.
크기가 큰 배열을 사용하려면 많은 메모리 공간이 연속적으로 비어있어야하는것인데,
배열의 크기를 늘리려면
기존에 할당된 메모리에서 바로 이어지는 자리에 여분의 공간이 있어한다.
그리고 배열의 중간의 항목을 제거하는 것 역시 까다로운 편이다.
링크드 리스트
링크드 리스트로는 스택, 리스트, 큐를 구현할 수있다.
각 칸이 메로이의 어느 위치에든 저장될 수 있으므로, 실행 도중에 리스트의 크기를 증가시켜야 하더라도 문제가 되지 않는다.
언제나 남아 있는 메모리 공간크기만큼의 리스트를 만들수 있습니다.
또한 항목을 리스트 중간에 추가하거나 리스트의 항목을 제거하는 것도 한칸의 포인터만 수정하면 되기 때문에 배열에 비해 훨씬 간단합니다.
연결리스트의 단점이 있는데, 가장 큰 단점은,
배열과 달리 n번째 항목을 상수 시간에 가져오지 못한다는 점이다.
첫 칸부터 탐색을 시작해 연결된 주소에 따라 다음 칸을 확인하고,
이어서 다음 칸을 구하는 식으로 n번째 항목에 도달할 때까지 탐색을 진행할수 밖에 없다.
또한 한칸의 주소만으로는 삭제나 수정이 어렵다.
이중 링크드 리스트도 있는데 앞서 말한 삭제나 수정을 할수있게끔 기능을 확장시킨 것이라고 보면되고 기존 링크드 리스트의 장점을 가지고 있다.
하지만 상수시간 접근은 여전히 할수가 없다는 단점을 가지고있다.
트리
트리는 링크드 리스트와 마찬가지로, 메모리 칸을 이용해 정보를 저장한다.
따라서 트리도 연속적인 물리적 메모리가 필요하지는않다.
트리의 칸도 저장 대상 외에 다른 칸을 향한 포인터를 가진다.
트리가 연결 리스트와 다른점은, 셀과 셀의 포인터가 한 줄의 사슬로 연결되지 않고
나무 형태의 구조로 연결된다는 점이다.
트리는 [파일-디렉토리], 회사 내부 구조 등의 계층적 데이터를 나타낼때 적합하다.
트리를 다루는 용어법에서는 각 칸을 노드, 한칸에서 다른 칸으로 가르키는 포인터를 엣지라고 부른다.
트리의 최상위 노드는 루트라고 부른다. 루트는 부모 노드를 가지고 있지 않으며,
다른 노드들은 모두 정확하게 하나의 부모 노드를 가진다.
동일한 노드를 부모로 하는 노드는 자매 노드이며,
루트 노드까지 연결한 경로는 노드의 조상들이 된다.
